?

思路：这是一个区间修改区间查询的题，由于题目中的给的数据比较大，那么用单个修改和查询肯定不行，所以。。。。注意数据可能比较大，应该用__int64或long long存数据。。。。。

code：

?

#include
  
   
#include
   
     #define L(u) (u<<1) #define R(u) (u<<1|1) const int M=100010; struct Node { __int64 l,r; __int64 add; long long sum; }node[M*4]; __int64 a[M]; void pushup(__int64 u) { node[u].sum=node[L(u)].sum+node[R(u)].sum; return ; } void pushdown(__int64 u) { node[L(u)].add+=node[u].add; node[L(u)].sum+=(node[L(u)].r-node[L(u)].l+1)*node[u].add; node[R(u)].add+=node[u].add; node[R(u)].sum+=(node[R(u)].r-node[R(u)].l+1)*node[u].add; node[u].add=0; } void build(__int64 u,__int64 left,__int64 right) { node[u].l=left; node[u].r=right; node[u].add=0; if(left==right) { node[u].sum=a[left]; return ; } __int64 mid=(node[u].l+node[u].r)/2; build(L(u),left,mid); build(R(u),mid+1,right); pushup(u); } void update(__int64 u,__int64 left,__int64 right,__int64 v) { if(left<=node[u].l&&node[u].r<=right) { node[u].add+=v; node[u].sum+=(node[u].r-node[u].l+1)*v; return ; } //node[u].sum+=(right-left+1)*v; //当前节点表示的区间不是查询区间的子区间 if(node[u].add) pushdown(u); //分析当前节点懒惰标记是否为0，不为0则要给他的子节点更新数据 __int64 mid=(node[u].l+node[u].r)/2; if(right<=mid) update(L(u),left,right,v); else if(left>mid) update(R(u),left,right,v); else { update(L(u),left,mid,v); update(R(u),mid+1,right,v); } node[u].sum=node[L(u)].sum+node[R(u)].sum; } __int64 query(__int64 u,__int64 left,__int64 right) { if(left<=node[u].l&&node[u].r<=right) { return node[u].sum; } if(node[u].add) pushdown(u); 
    //分析当前节点懒惰标记是否为0，不为0则要给他的子节点更新数据 __int64 mid=(node[u].l+node[u].r)/2; if(right<=mid) return query(L(u),left,right); else if(left>mid) return query(R(u),left,right); else { return (query(L(u),left,mid)+query(R(u),mid+1,right)); } } int main() { __int64 n,m,i,x,y,z; while(scanf(%I64d%I64d,&n,&m)==2) { for(i=1;i<=n;i++) { scanf(%I64d,&a[i]); } build(1,1,n); char str[5]; for(i=0;i
    
     
?