单点更新

showproblem.php?pid=1166

 1 #include<cstdio>
 2 #define lrrt int L,int R,int rt
 3 #define iall 1,n,1
 4 #define imid int mid=(L+R)>>1
 5 #define lson L,mid,rt<<1
 6 #define rson mid+1,R,rt<<1|1
 7 const int M=50010;
 8 int tree[M<<2];
 9 int a[M];
10 void pushup(int rt){
11     tree[rt]=tree[rt<<1]+tree[rt<<1|1];
12 }
13 void build(lrrt){
14     if(L==R){
15         tree[rt]=a[L];
16         return ;
17     }
18     imid;
19     build(lson);
20     build(rson);
21     pushup(rt);
22 }
23 void update(int x,int y,lrrt){
24     if(L==R){
25         tree[rt]+=y;
26         return ;
27     }
28     imid;
29     if(mid>=x) update(x,y,lson);
30     else       update(x,y,rson);
31     pushup(rt);
32 }
33 int query(int x,int y,lrrt){
34     if(x<=L&&R<=y) return tree[rt];
35     imid;
36     int ans=0;
37     if(mid>=x) ans+=query(x,y,lson);
38     if(mid<y)  ans+=query(x,y,rson);
39     return ans;
40 }
41 int main(){
42     int t,n;
43     while(~scanf("%d",&t)){
44         int cas=1;
45         while(t--){
46             printf("Case %d:
",cas++);
47             scanf("%d",&n);
48             for(int i=1;i<=n;i++){
49                 scanf("%d",&a[i]);
50             }
51             build(iall);
52             char op[8];
53             while(~scanf("%s",op)){
54                 if(op[0]=='E') break;
55                 int x,y;
56                 scanf("%d%d",&x,&y);
57                 if(op[0]=='A'){
58                     update(x,y,iall);
59                 }
60                 else if(op[0]=='S'){
61                     update(x,-y,iall);
62                 }
63                 else{
64                     printf("%d
",query(x,y,iall));
65                 }
66             }
67         }
68     }
69     return 0;
70 }

View Code

I Hate It http://acm.hdu.edu.cn/showproblem.php?pid=1754

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define lrrt int L,int R,int rt
 4 #define iall 1,n,1
 5 #define imid int mid=(L+R)>>1
 6 #define lson L,mid,rt<<1
 7 #define rson mid+1,R,rt<<1|1
 8 using namespace std;
 9 const int M=200010;
10 int a[M];
11 int tree[M<<2];
12 void pushup(int rt){
13     tree[rt]=max(tree[rt<<1],tree[rt<<1|1]);
14 }
15 void build(lrrt){
16     if(L==R){
17         tree[rt]=a[L];
18         return ;
19     }
20     imid;
21     build(lson);
22     build(rson);
23     pushup(rt);
24 }
25 void update(int x,int y,lrrt){
26     if(L==R){
27         tree[rt]=y;
28         return ;
29     }
30     imid;
31     if(mid>=x) update(x,y,lson);
32     else       update(x,y,rson);
33     pushup(rt);
34 }
35 int query(int x,int y,lrrt){
36     if(x<=L&&R<=y) return tree[rt];
37     imid;
38     int ans=0;
39     if(mid>=x) ans=max(ans,query(x,y,lson));
40     if(mid<y)  ans=max(ans,query(x,y,rson));
41     return ans;
42 }
43 int main(){
44     int n,m;
45     while(~scanf("%d%d",&n,&m)){
46         for(int i=1;i<=n;i++){
47             scanf("%d",&a[i]);
48         }
49         build(iall);
50         while(m--){
51             int x,y;
52             char op[4];
53             scanf("%s%d%d",op,&x,&y);
54             if(op[0]=='U'){
55                 update(x,y,iall);
56             }
57             else{
58                 printf("%d
",query(x,y,iall));
59             }
60         }
61     }
62     return 0;
63 }

View Code

Multiply game http://acm.hdu.edu.cn/showproblem.php?pid=3074

 1 #include<cstdio>
 2 #define lrrt int L,int R,int rt
 3 #define iall 1,n,1
 4 #define imid int mid=(L+R)>>1
 5 #define lson L,mid,rt<<1
 6 #define rson mid+1,R,rt<<1|1
 7 typedef __int64 LL;
 8 const int mod=1000000007;
 9 const int M=50010;
10 int a[M];
11 LL tree[M<<2];
12 void pushup(int rt){
13     tree[rt]=(tree[rt<<1]*tree[rt<<1|1])%mod;
14 }
15 void build(lrrt){
16     if(L==R){
17         tree[rt]=a[L];
18         return ;
19     }
20     imid;
21     build(lson);
22     build(rson);
23     pushup(rt);
24 }
25 void update(int x,int y,lrrt){
26     if(L==R){
27         tree[rt]=y;
28         return ;
29     }
30     imid;
31     if(mid>=x) update(x,y,lson);
32     else       update(x,y,rson);
33     pushup(rt);
34 }
35 LL query(int x,int y,lrrt){
36     if(x<=L&&R<=y) return tree[rt];
37     LL ans=1;
38     imid;
39     if(mid>=x) ans=(ans*query(x,y,lson))%mod;
40     if(mid<y)  ans=(ans*query(x,y,rson))%mod;
41     return ans;
42 }
43 int main(){
44     int t,n,m;
45     while(~scanf("%d",&t)){
46         while(t--){
47             scanf("%d",&n);
48             for(int i=1;i<=n;i++){
49                 scanf("%d",&a[i]);
50             }
51             build(iall);
52             scanf("%d",&m);
53             while(m--){
54                 int op,x,y;
55                 scanf("%d%d%d",&op,&x,&y);
56                 if(op){
57                     update(x,y,iall);
58                 }
59                 else{
60                     printf("%I64d
",query(x,y,iall));
61                 }
62             }
63         }
64     }
65     return 0;
66 }

View Code

Balanced Lineup http://poj.org/problem?id=3264

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define lrrt int L,int R,int rt
 4 #define iall 1,n,1
 5 #define imid int mid=(L+R)>>1
 6 #define lson L,mid,rt<<1
 7 #define rson mid+1,R,rt<<1|1
 8 using namespace std;
 9 const int M=50010;
10 int a[M];
11 struct T{
12     int big,sma;
13 }tree[M<<2];
14 void pushup(int rt){
15     tree[rt].big=max(tree[rt<<1].big,tree[rt<<1|1].big);
16     tree[rt].sma=min(tree[rt<<1].sma,tree[rt<<1|1].sma);
17 }
18 void build(lrrt){
19     if(L==R){
20         tree[rt].big=tree[rt].sma=a[L];
21         return ;
22     }
23     imid;
24     build(lson);
25     build(rson);
26     pushup(rt);
27 }
28 int querybig(int x,int y,lrrt){
29     if(x<=L&&R<=y) return tree[rt].big;
30     imid;
31     int ans=0;
32     if(mid>=x) ans=max(ans,querybig(x,y,lson));
33     if(mid<y)  ans=max(ans,querybig(x,y,rson));
34     return ans;
35 }
36 int querysma(int x,int y,lrrt){
37     if(x<=L&&R<=y) return tree[rt].sma;
38     imid;
39     int ans=1000010;
40     if(mid>=x) ans=min(ans,querysma(x,y,lson));
41     if(mid<y)  ans=min(ans,querysma(x,y,rson));
42     return ans;
43 }
44 int main(){
45     int n,m;
46     while(~scanf("%d%d",&n,&m)){
47         for(int i=1;i<=n;i++){
48             scanf("%d",&a[i]);
49         }
50         build(iall);
51         while(m--){
52             int x,y;
53             scanf("%d%d",&x,&y);
54             printf("%d
",querybig(x,y,iall)-querysma(x,y,iall));
55         }
56     }
57     return 0;
58 }

View Code

end