題目

小林是個程式媛，不可避免地康娜對這種人類的“魔法”產生了濃厚的興趣，于是小林開始教她OI，

今天康娜學習了一種叫做線段樹的神奇魔法，這種魔法可以維護一段區間的資訊，是非常厲害的東西，康娜試著寫了一棵維護區間和的線段樹，由于她不會打標記，因此所有的區間加操作她都是暴力修改的，具體的代碼如下：

struct Segment_Tree{
#define lson (o<<1)
#define rson (o<<1|1)
    int sumv[N<<2],minv[N<<2];
    inline void pushup(int o){sumv[o]=sumv[lson]+sumv[rson];}
    inline void build(int o,int l,int r){
        if(l==r){sumv[o]=a[l];return;}
        int mid=(l+r)>>1;
        build(lson,l,mid);build(rson,mid+1,r);
        pushup(o);
    }
    inline void change(int o,int l,int r,int q,int v){
        if(l==r){sumv[o]+=v;return;}
        int mid=(l+r)>>1;
        if(q<=mid)change(lson,l,mid,q,v);
        else change(rson,mid+1,r,q,v);
        pushup(o);
    }
}T; 

在修改時，她會這么寫：

for(int i=l;i<=r;i++)T.change(1,1,n,i,addv);

顯然，這棵線段樹每個節點有一個值，為該節點管轄區間的區間和，

康娜是個愛思考的孩子，于是她突然想到了一個問題：

如果每次在線段樹區間加操作做完后，從根節點開始等概率的選擇一個子節點進入，直到進入葉子結點為止，將一路經過的節點權值累加，最后能得到的期望值是多少？

1 ≤ n , m ≤ 1 0 6 1 \leq n,m \leq 10^6 1≤n,m≤106

? 1000 ≤ a i , x ≤ 1000 -1000 \leq a_i,x \leq 1000 ?1000≤ai?,x≤1000

題解

思路

對于本題，我們有一個最樸素的想法就是對每一層求一個和，乘上到達這一層的概率，即 1 2 d e p ? 1 \frac{1}{2^{dep-1}} 2dep?11?,但這樣是無法比較快速的應對修改操作的

基于這種思路，我們換個思考的方向，即思考一個 i i i

顯然包含 i i i 的塊是連續的，如下圖：

對于包含 2 2 2 下標的塊，一定是連續的

而他所做的貢獻就是上圖示注的

所以現在我們只需要知道每一個下標 i , i ∈ [ 1 , n ] i,i\in [1,n] i,i∈[1,n]，它對應的葉節點的深度是多少

所以為了實作這一目標，我們來單獨去求這個東西：

求深度是可以用一個搜索來解決的，但是我們要快，一個搜索是不夠的

那么優化搜索的方法是什么？

記憶化！

對的，我們在這里有一個比較好玩的性質，對于每一個長度相同的區間，這兩個區間中相對應的兩個下標 i , j i,j i,j 到這兩個下標的最深深度距離是一樣的

可能有點抽象，我們舉個栗子：

上圖中第 2 2 2 層的 [ 1 , 3 ] [1,3] [1,3] 和 [ 4 , 6 ] [4,6] [4,6]，區間長度一樣

那么 [ 1 , 3 ] [1,3] [1,3]區間中的第 2 2 2 個數也就是 2 2 2，它到 [ 2 , 2 ] [2,2] [2,2]的距離是 2 2 2；

[ 4 , 6 ] [4,6] [4,6]區間中的第 2 2 2 個數也就是 5 5 5，它到 [ 5 , 5 ] [5,5] [5,5]的距離也是 2 2 2；

當然，我們多找幾個來舉例，也是一樣的

也就是說我們是可以通過這種方法實作記憶化

void dfs(int l,int r,int sum){
	if(mem[r-l+1]==true){
		for(int i=l;i<=r;i++){
			s[i]=s[i-l+s1[r-l+1]]-s2[r-l+1]+sum;
		}
		return;
	}
	if(l==r){
		s[l]=sum;
		w=max(w,sum);
		return;
	}
	int mid=(l+r)>>1;
	dfs(l,mid,sum+1);
	dfs(mid+1,r,sum+1);
	s1[r-l+1]=l;
	s2[r-l+1]=sum;
	mem[r-l+1]=true;
}

處理好了深度，剩下的事情就真的簡單了，一個前綴和， o v e r over over

code

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=1000005;
int s1[MAXN];
int s2[MAXN];
long long s[MAXN];
bool mem[MAXN];
long long pre[MAXN];
int dep[MAXN],pre_d[MAXN];
int w;
void dfs(int l,int r,int sum){
	if(mem[r-l+1]==true){
		for(int i=l;i<=r;i++){
			s[i]=s[i-l+s1[r-l+1]]-s2[r-l+1]+sum;
		}
		return;
	}
	if(l==r){
		s[l]=sum;
		w=max(w,sum);
		return;
	}
	int mid=(l+r)>>1;
	dfs(l,mid,sum+1);
	dfs(mid+1,r,sum+1);
	s1[r-l+1]=l;
	s2[r-l+1]=sum;
	mem[r-l+1]=true;
}
int main(){
	int n,m;
	long long qwq;
	scanf("%d %d %lld",&n,&m,&qwq);
	qwq*=128;
	dfs(1,n,1);
	dep[1]=qwq;
	pre_d[1]=qwq;
	for(int i=2;i<=w;i++){
		dep[i]=dep[i-1]>>1;
		pre_d[i]=pre_d[i-1]+dep[i];
	}
	for(int i=1;i<=n;i++){
		pre[i]=pre[i-1]+pre_d[s[i]];
	}
//	for(int i=1;i<=n;i++){
//		cout<<pre[i]<<endl;
//	}
	long long ans=0;
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		ans+=(pre[i]-pre[i-1])*x;
	}
	for(int i=1;i<=m;i++){
		int l,r,x;
		scanf("%d %d %d",&l,&r,&x);
		ans+=(pre[r]-pre[l-1])*x;
		printf("%lld\n",ans/128);
	}
return 0;
}