敌兵布阵 树状数组

?

#include <cstdio>#include <cstring>using namespace std;const int MAXN=50005;int c[MAXN],t,i,a,b,n,k;int lowbit(int id){? ? ? ? return id&-id;}void add(int a,int b){ ? ? ? ??while(a<=n) ? ? ? ??{ ? ? ? ??? ? ? ??c[a]+=b; ? ? ? ??? ? ? ??a+=lowbit(a); ? ? ? ??}}int sum(int x){ ? ? ? ??int res=0; ? ? ? ??while(x>0) ? ? ? ??{ ? ? ? ??? ? ? ??res+=c[x]; ? ? ? ??? ? ? ??x-=lowbit(x); ? ? ? ??} ? ? ? ??return res;}int main(){ ? ? ? ??char m[10]; ? ? ? ??int l=1; ? ? ? ??scanf("%d",&t); ? ? ? ??while(t--) ? ? ? ??{ ? ? ? ??? ? ? ??scanf("%d",&n); ? ? ? ??? ? ? ??memset(c,sizeof(c)); ? ? ? ??? ? ? ??for(i=1;i<=n;i++) ? ? ? ??? ? ? ??{ ? ? ? ??? ? ? ??? ? ? ??scanf("%d",&k); ? ? ? ??? ? ? ??? ? ? ??add(i,k); ? ? ? ??? ? ? ??} ? ? ? ??? ? ? ??printf("Case %d:n",l); ? ? ? ??? ? ? ??l++; ? ? ? ??? ? ? ??while(scanf("%s",m)!=EOF&&m[0]!=‘E‘) ? ? ? ??? ? ? ??{ ? ? ? ??? ? ? ??? ? ? ??if(m[0]==‘Q‘) ? ? ? ??? ? ? ??? ? ? ??{ ? ? ? ??? ? ? ??? ? ? ??? ? ? ??scanf("%d%d",&a,&b); ? ? ? ??? ? ? ??? ? ? ??? ? ? ??printf("%dn",sum(b)-sum(a-1)); ? ? ? ??? ? ? ??? ? ? ??} ? ? ? ??? ? ? ??? ? ? ??else if(m[0]==‘A‘) ? ? ? ??? ? ? ??? ? ? ??{ ? ? ? ??? ? ? ??? ? ? ??? ? ? ??scanf("%d%d",&b); ? ? ? ??? ? ? ??? ? ? ??? ? ? ??add(a,b); ? ? ? ??? ? ? ??? ? ? ??} ? ? ? ??? ? ? ??? ? ? ??else if(m[0]==‘S‘) ? ? ? ??? ? ? ??? ? ? ??{ ? ? ? ??? ? ? ??? ? ? ??? ? ? ??scanf("%d%d",-b); ? ? ? ??? ? ? ??? ? ? ??} ? ? ? ??? ? ? ??} ? ? ? ??} ? ? ? ??return 0;}