模拟题，可以用树链剖分+线段树维护。

但是学了一个厉害的。。树状数组的区间修改与区间查询。。

分割线里面的是转载的：

--------------------------------------------------------------------------------

[ 3 ]  上面都不是重点……重点是树状数组的区间修改+区间查询 这个很好玩 其实也挺简单

首先依旧是引入delta数组 delta[i]表示区间 [i, n] 的共同增量 于是修改区间 [l, r] 时修改 delta[l] 和 delta[r + 1] 即可（就是差分的思路）

查询的时候是查询区间 [l, r] 的和 即sum[r] - sum[l - 1] 所以现在的问题是求sum[i]

 

1 sum[i] = a[1]+...+a[i] + delta[1]*i + delta[2]*(i - 1) + delta[3]*(i - 2)+...+delta[i]*1   // a[i]为原始数组  2        = sigma( a[x] ) + sigma( delta[x]  *  (i + 1 - x) )  3        = sigma( a[x] ) + (i + 1) * sigma( delta[x] ) - sigma( delta[x] * x )

 

 

其中 sigma( a[x] ) 是可以预处理出来的 于是只需要维护 delta[x] 与 delta[x] * x 的前缀和（作为两个树状数组就可以了）

 

为了试验这个方法我专门去找了之前写线段树挂了好久的例题 = = 

然后交树状数组的代码是 324ms 内存5M过了 线段树是1027ms 13M 如果去掉读入优化的话代码会更短。

--------------------------------------------------------------------------------------------------------------------------

转自：

很好。。这题本机测系统暴栈了。。交上去才A。。

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 using namespace std; 8 9 const int N=2*100010,S=30,D=20; 10 struct node{ 11 int x,y,next; 12 }a[2*N]; 13 struct trnode{ 14 int l,r,lc,rc,d; 15 }t[2*N]; 16 int n,m,len,num,first[N],dep[N],f[N][S],tot[N],zs[N],dfn[N],top[N],c0[N],c1[N],delta[N]; 17 char s[10]; 18 19 void add(int x,int d) 20 { 21 for(int i=x;i<=n;i+=(i&(-i))) c0[i]+=d,c1[i]+=d*x; 22 } 23 24 int getsum(int x) 25 { 26 int a0=0,a1=0; 27 for(int i=x;i>=1;i-=(i&(-i))) a0+=c0[i],a1+=c1[i]; 28 return a0*(x+1)-a1; 29 } 30 31 32 void ins(int x,int y) 33 { 34 a[++len].x=x;a[len].y=y; 35 a[len].next=first[x];first[x]=len; 36 } 37 38 void dfs(int x,int fa) 39 { 40 dep[x]=dep[fa]+1; 41 f[x][0]=fa; 42 tot[x]=1; 43 zs[x]=0; 44 for(int i=first[x];i;i=a[i].next) 45 { 46 int y=a[i].y; 47 if(y==fa) continue; 48 dfs(y,x); 49 tot[x]+=tot[y]; 50 if(zs[x]==0 || tot[y]>tot[zs[x]]) zs[x]=y; 51 } 52 } 53 54 void find_top(int x,int fa) 55 { 56 dfn[x]=++num; 57 if(zs[x]) 58 { 59 top[zs[x]]=top[x]; 60 find_top(zs[x],x); 61 } 62 for(int i=first[x];i;i=a[i].next) 63 { 64 int y=a[i].y; 65 if(y==fa || y==zs[x]) continue; 66 top[y]=y; 67 find_top(y,x); 68 } 69 } 70 71 int solve(int x,int y,int tmp) 72 { 73 int tx=top[x],ty=top[y],ans=0; 74 while(tx!=ty) 75 { 76 if(dep[tx]
           
            =0;i--)110 {111 if(f[x][i]==0) continue;112 if(dep[f[x][i]]>=dep[y]) x=f[x][i];113 }114 if(x==y) return x;115 for(int i=D;i>=0;i--)116 {117 if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];118 }119 return f[x][0];120 }121 122 int main()123 {124 freopen("a.in","r",stdin);125 // freopen("a.out","w",stdout);126 // freopen("grassplant.in","r",stdin);127 // freopen("grassplant.out","w",stdout);128 scanf("%d%d",&n,&m);129 int x,y,z;len=0;num=0;130 memset(first,0,sizeof(first));131 memset(f,0,sizeof(f));132 memset(c0,0,sizeof(c0));133 memset(c1,0,sizeof(c1));134 memset(dep,0,sizeof(dep));135 memset(tot,0,sizeof(tot));136 memset(zs,0,sizeof(zs));137 memset(dfn,0,sizeof(dfn));138 for(int i=1;i