传送门：POJ3468
题意：给定n个数和两种操作，Q i j 代表求Σnum[t](i<=t<=j) C i j k 代表将num[t](i<=t<=j)加上k.
思路：线段树基本操作，成段更新，区间询问。也可以用树状数组做，详见挑战程序设计第二版P179.
代码：
#include<stdio.h> #include<iostream> #include<string.h> #include<math.h> #include<algorithm> #include<queue> #include<stack> #include<set> #include<vector> #include<map> #define ll long long #define pi acos(-1) #define inf 0x3f3f3f3f #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 using namespace std; typedef pair<int,int>P; const int MAXN=100010; struct node{ ll key,lazy;//lazy为懒惰标记，也称延时标记 }num[MAXN<<2]; void pushup(int rt) { num[rt].key=num[rt<<1].key+num[rt<<1|1].key; } void pushdown(int rt,int k) { if(num[rt].lazy) { num[rt<<1].lazy+=num[rt].lazy; num[rt<<1|1].lazy+=num[rt].lazy; num[rt<<1].key+=num[rt].lazy*(k-(k>>1)); num[rt<<1|1].key+=num[rt].lazy*(k>>1); num[rt].lazy=0; } } void build(int l,int r,int rt) { num[rt].lazy=num[rt].key=0; if(l==r) { scanf("%lld",&num[rt].key); return ; } int mid=(l+r)>>1; build(lson); build(rson); pushup(rt); } ll query(int L,int R,int l,int r,int rt) { if(L<=l&&r<=R)return num[rt].key; pushdown(rt,r-l+1); int mid=(l+r)>>1; ll ans=0; if(L<=mid)ans+=query(L,R,lson); if(R>mid)ans+=query(L,R,rson); return ans; } void update(int L,int R,int x,int l,int r,int rt) { if(L<=l&&r<=R) { num[rt].key+=(ll)x*(r-l+1); num[rt].lazy+=x; return ; } pushdown(rt,r-l+1); int mid=(l+r)>>1; if(L<=mid)update(L,R,x,lson); if(R>mid)update(L,R,x,rson); pushup(rt); } int main() { int n,q,a,b,x; char s[10]; scanf("%d%d",&n,&q); build(1,n,1); while(q--) { scanf("%s",s); if(s[0]=='Q') { scanf("%d%d",&a,&b); printf("%lld\n",query(a,b,1,n,1)); } else if(s[0]=='C') { scanf("%d%d%d",&a,&b,&x); update(a,b,x,1,n,1); } } return 0; }
