#include树状数组#include const int N = 50010; int w[N],n; struct Node { int l,r,sum; }tr[N*4]; void pushup(int u) { tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum; } void build(int u,int l,int r) { if(l==r) tr[u]={l,r,w[l]}; else { tr[u]={l,r}; int mid=l+r>>1; build(u<<1,l,mid); build(u<<1|1,mid+1,r); pushup(u); } } void update(int u,int x,int d) { if(tr[u].l==x&&tr[u].r==x) tr[u].sum+=d; else { int mid=tr[u].l+tr[u].r>>1; if(x<=mid) update(u<<1,x,d); if(x>mid) update(u<<1|1,x,d); pushup(u); } } int query(int u,int l,int r) { if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum; else { int mid=tr[u].l+tr[u].r>>1; int res=0; if(l<=mid) res=query(u<<1,l,r); if(r>mid) res+=query(u<<1|1,l,r); return res; } } int main() { int T,t=1;scanf("%d",&T); while(T--) { printf("Case %d:n",t++); int n;scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&w[i]); build(1,1,n); char op[10]; while(scanf("%s",op)!=EOF) { if(strcmp(op,"End")==0) break; int l,r;scanf("%d%d",&l,&r); if(strcmp(op,"Add")==0) update(1,l,r); if(strcmp(op,"Sub")==0) update(1,l,-r); if(strcmp(op,"Query")==0) printf("%dn",query(1,l,r)); } } return 0; }
#include#include const int N = 50010; int n,c[N]; int add(int x,int y){for(;x<=n;x+=(x&-x)) c[x]+=y;} int getsum(int x){int res=0;for(;x;x-=(x&-x)) res+=c[x];return res;} int main() { int T,t=1;scanf("%d",&T); while(T--) { memset(c,0,sizeof c); printf("Case %d:n",t++); scanf("%d",&n); for(int i=1;i<=n;i++) { int x;scanf("%d",&x); add(i,x); } char op[10]; while(scanf("%s",op)!=EOF) { if(strcmp(op,"End")==0) break; int l,r;scanf("%d%d",&l,&r); if(strcmp(op,"Add")==0) add(l,r); if(strcmp(op,"Sub")==0) add(l,-r); if(strcmp(op,"Query")==0) printf("%dn",getsum(r)-getsum(l-1)); } } return 0; }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)