题目
线段树模版
//hdu1166 敌兵布阵 #include<iostream> #include<string> #include<cstdio> #include<cstring> #define lson l,m,pos<<1 #define rson m+1,r,pos<<1|1 using namespace std; int n,T; int sum[200100]; void pushup(int pos){sum[pos]=sum[pos<<1]+sum[pos<<1|1];} void build(int l,int r,int pos) { if (l==r) {scanf("%d",&sum[pos]);return;} int m=(l+r)>>1; build(lson);build(rson); pushup(pos); } void update(int p,int add,int l,int r,int pos) { if (l==r){sum[pos]+=add;return;} int m=(l+r)>>1; if (p<=m) update(p,add,lson); else if (p>m) update(p,add,rson); pushup(pos); } int query(int L,int R,int l,int r,int pos) { if (L<=l&&r<=R) return sum[pos]; int m=(l+r)>>1,ret=0; if (L<=m) ret+=query(L,R,lson); if (R>m) ret+=query(L,R,rson); return ret; } int main() { scanf("%d",&T); for (int i=1;i<=T;i++) { scanf("%d",&n); printf("Case %d:\n",i); build(1,n,1); string s; while(cin>>s) { if (s[0]=='E') break; int a,b;scanf("%d%d",&a,&b); if (s[0]=='A') update(a,b,1,n,1); else if (s[0]=='S') update(a,-b,1,n,1); else printf("%d\n",query(a,b,1,n,1)); } } return 0; }
