uva 12086

线段树单点更新因为CASE之间的换行WA了两次
 1 #include<cstdio>
 2 #include<cstring>
 3 const int maxn=200000+5;
 4 int sum[maxn<<2];
 5 int CASE=1;
 6 void push_up(int rt)
 7 {
 8     sum[rt]=sum[rt<<1]+sum[rt<<1|1];
 9 }
10 void build(int l,int r,int rt)
11 {
12     if(l==r)
13     {
14         scanf("%d",&sum[rt]);
15         return;
16     }
17     int m=(l+r)>>1;
18     build(l,m,rt<<1);
19     build(m+1,r,rt<<1|1);
20     push_up(rt);
21 }
22 void update(int x,int y,int l,int r,int rt)
23 {
24     if(l==r)
25     {
26         sum[rt]=y;
27         return ;
28     }
29     int  m=(l+r)>>1;
30     if(x<=m) update(x,y,l,m,rt<<1);
31     else update(x,y,m+1,r,rt<<1|1);
32     push_up(rt);
33 }
34 int query(int L,int R,int l,int r,int rt)
35 {
36     if(L<=l&&r<=R)
37     {
38         return sum[rt];
39     }
40     int m=(l+r)>>1;
41     int ret=0;
42     if(L<=m) ret+=query(L,R,l,m,rt<<1);
43     if(R>m) ret+=query(L,R,m+1,r,rt<<1|1);
44     return ret;
45 }
46 int main()
47 {
48     int n;
49     while(scanf("%d",&n)&&n)
50     {
51         if(CASE!=1)
52         printf("
");
53         memset(sum,0,sizeof(sum));
54         build(1,n,1);
55         char com[8];
56         printf("Case %d:
",CASE++);
57         while(scanf("%s",com)&&strcmp(com,"END"))
58         {
59             int x,y;
60             scanf("%d%d",&x,&y);
61             if(com[0]=='M')
62                 printf("%d
",query(x,y,1,n,1));
63             else
64                update(x,y,1,n,1);
65         }
66     }
67     return 0;
68 }