本文共 2915 字,大约阅读时间需要 9 分钟。
1、
2、题目大意:
求某一区间内兵的总数,
线段树功能:update:单点增减 query:区间求和
3、题目:
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 23500 Accepted Submission(s): 10209
1101 2 3 4 5 6 7 8 9 10Query 1 3Add 3 6Query 2 7Sub 10 2Add 6 3Query 3 10End
Case 1:63359
4、代码:
#include#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1int sum[50005*4];void build(int l,int r,int rt){ if(l==r) { scanf("%d",&sum[rt]); return ; } int m=(l+r)>>1; build(lson); build(rson); sum[rt]=sum[rt<<1]+sum[rt<<1|1];}int query(int L,int R,int l,int r,int rt){ if(L<=l&&R>=r) return sum[rt]; int m=(l+r)>>1; int ret=0; if(L<=m) ret+=query(L,R,lson); if(R>=m+1) ret+=query(L,R,rson); return ret;}void update(int a,int b,int l,int r,int rt){ if(l==r) { sum[rt]+=b; return ; } int m=(l+r)>>1; if(a<=m) update(a,b,lson); else update(a,b,rson); sum[rt]=sum[rt<<1]+sum[rt<<1|1];}int main(){ int t,n; char str[10]; int a,b; scanf("%d",&t); for(int i=1;i<=t;i++) { printf("Case %d:\n",i); scanf("%d",&n); build(1,n,1); while(scanf("%s",str)!=EOF) { if(str[0]=='E') break; if(str[0]=='A') { scanf("%d%d",&a,&b); update(a,b,1,n,1); } if(str[0]=='S') { scanf("%d%d",&a,&b); update(a,-b,1,n,1); } if(str[0]=='Q') { scanf("%d%d",&a,&b); printf("%d\n",query(a,b,1,n,1)); } /*for(int i=1;i<=25;i++) printf("sum[%d]=%d ",i,sum[i]); printf("\n"); */ } } return 0;}/*1101 2 3 4 5 6 7 8 9 10Query 1 3Add 3 6Query 2 7Sub 10 2Add 6 3Query 3 10End*/
转载地址:http://ffcdi.baihongyu.com/