Descriptionios
Input算法
Outputui
Sample Inputspa
Sample Outputcode
#include"cstdio" #include"cstring" #include"iostream" #include"algorithm" using namespace std; #define MAX 50005 struct TREE { int l,r; int sum; }tree[MAX*4]; int a[MAX]; void build(int id,int l,int r) { tree[id].l = l; tree[id].r = r; if(l == r) { tree[id].sum = a[l]; } else { int mid = (l+r)/2; build(2*id,l,mid); build(2*id+1,mid+1,r); tree[id].sum = tree[id*2].sum + tree[id*2+1].sum; } } void update(int id,int pos,int val) { if(tree[id].l == tree[id].r) { tree[id].sum += val; } else { int mid = (tree[id].l+tree[id].r)/2; if(pos <= mid) { update(id*2,pos,val); } else { update(id*2+1,pos,val); } tree[id].sum = tree[id*2].sum + tree[id*2+1].sum; } } int query(int id,int L,int R) { if(tree[id].l >= L && tree[id].r <= R) { return tree[id].sum; } else { int mid = (tree[id].l+tree[id].r)/2; int ans = 0; if(L <= mid) { ans += query(id*2,L,R); } if(R > mid) { ans += query(id*2+1,L,R); } return ans; } } int main() { int T; while(~scanf("%d",&T)) { for(int cas = 1;cas <= T;cas++) { int N; scanf("%d",&N); for(int i = 1;i <= N;i++) { scanf("%d",&a[i]); } build(1,1,N); printf("Case %d:\n",cas); int p,q; string c; while(cin >> c) { if(c == "Query") { scanf("%d%d",&p,&q); printf("%d\n",query(1,p,q)); } if(c == "Sub") { scanf("%d%d",&p,&q); update(1,p,-q); } if(c == "Add") { scanf("%d%d",&p,&q); update(1,p,q); } if(c == "End") { break; } } } } return 0; }