A Simple Problem with Integers Time Limit:5000MS Memory Limit:131072KB 64bit IO Format:%lld & %llu Description 给出了一个序列，你需要处理如下两种询问。 "C a b c"表示给[a, b]区间中的值全部增加c (-10000 ≤ c ≤ 10000)。 "Q a b" 询问[a, b]区间中所有值的和。 Input 第一行包含两个整数N, Q。1 ≤ N,Q ≤ 100000. 第二行包含n个整数，表示初始的序列A (-1000000000 ≤ Ai ≤ 1000000000)。 接下来Q行询问，格式如题目描述。 Output 对于每一个Q开头的询问，你需要输出相应的答案，每个答案一行。 Sample Input 10 5 1 2 3 4 5 6 7 8 9 10 Q 4 4 Q 1 10 Q 2 4 C 3 6 3 Q 2 4 Sample Output 4 55 9 15
//用到懒惰标记法。
//Query查询求和，UpData更新数据。
//AC代码：
1 #include"iostream" 2 #include"algorithm" 3 #include"cstdio" 4 #include"cstring" 5 #include"cmath" 6 using namespace std; 7 #define MX 1000000 + 10 8 #define INF 0 9 #define lson l,m,rt<<1 10 #define rson m+1,r,rt<<1|1 11 12 long long sum[MX<<2]; //数据很大可能会爆int，用long long 13 long long lazy[MX<<2]; 14 15 void PushUp(int rt) { 16 sum[rt]=sum[rt<<1]+sum[rt<<1|1]; 17 } 18 19 void PushDown(int rt,int m) { 20 if(lazy[rt]) { //如果存在懒惰标记就把标记下移； 21 lazy[rt<<1] +=lazy[rt]; 22 lazy[rt<<1|1]+=lazy[rt]; 23 sum[rt<<1] +=lazy[rt]*(m-(m>>1)); 24 sum[rt<<1|1] +=lazy[rt]*(m>>1); 25 lazy[rt]=INF; 26 } 27 } 28 29 void Build(int l,int r, int rt) { 30 lazy[rt]=INF; //清空懒惰标记 31 if(r==l) { 32 scanf("%I64d",&sum[rt]); //输入每个叶节点的值 33 return ; 34 } 35 int m=(r+l)>>1; 36 Build(lson); 37 Build(rson); 38 PushUp(rt); 39 } 40 41 void UpData(int L,int R,int c,int l,int r,int rt) { 42 if (L<=l&&r<=R) { 43 lazy[rt]+=c; //输要改变的值，记录懒惰标记 。 44 sum[rt]+=(r-l+1)*c; //中间N个数都要进行相同的加减。 45 return ; 46 } 47 PushDown(rt,r-l+1); //下移懒惰标记 48 int m=(r+l)>>1; 49 if(L<=m) UpData(L,R,c,lson); 50 if(R> m) UpData(L,R,c,rson); 51 PushUp(rt); 52 } 53 54 long long Query(int L,int R,int l,int r,int rt) { 55 if(L<=l&&r<=R) return sum[rt]; 56 PushDown(rt,r-l+1); 57 //【这步不能少，如果区间没有全部包括，要保证每一个标记都放到目标子节点】 58 int m=(r+l)>>1; 59 long long ret=0; 60 if(L<=m) ret+=Query(L,R,lson); 61 if(R> m) ret+=Query(L,R,rson); 62 return ret; 63 } 64 65 int main() { 66 int n,q; 67 while(~scanf("%d%d",&n,&q)) { 68 Build(1,n,1); 69 char s[2]; 70 int a,b,c; 71 for(int i=0; i<q; i++) { 72 scanf("%s",s); 73 if(s[0]=='Q') { 74 scanf("%d%d",&a,&b); 75 printf("%I64d ",Query(a,b,1,n,1)); 76 } else if(s[0]=='C') { 77 scanf("%d%d%d",&a,&b,&c); 78 UpData(a,b,c,1,n,1); 79 } 80 } 81 } 82 return 0; 83 }