HDU 1166 敌兵布阵

线段树单点更新。

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=1166

模板题。我写的。

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 #define N 100000
 5 struct node
 6 {
 7     int l,r;
 8     int sum;
 9 }xtree[4*N];
10 void pushup(int rn)
11 {
12     xtree[rn].sum=xtree[rn<<1].sum+xtree[rn<<1|1].sum;
13 }
14 void build(int l,int r,int rn)
15 {
16     xtree[rn].l=l;
17     xtree[rn].r=r;
18     if(l==r)
19     {
20         scanf("%d",&xtree[rn].sum);
21         return ;
22     }
23     int mid=(l+r)>>1;
24     build(l,mid,rn<<1);
25     build(mid+1,r,rn<<1|1);
26     pushup(rn);
27 }
28 void update(int num,int val,int rn)
29 {
30     if(xtree[rn].l==xtree[rn].r)
31     {
32         xtree[rn].sum+=val;
33         return ;
34     }
35     int mid=(xtree[rn].l+xtree[rn].r)>>1;
36     if(num<=mid)
37     {
38         update(num,val,rn<<1);
39     }
40     else
41     {
42         update(num,val,rn<<1|1);
43     }
44     pushup(rn);
45 }
46 int que(int le,int ri,int rn)
47 {
48     if(xtree[rn].l==le&&xtree[rn].r==ri)
49     {
50         return xtree[rn].sum;
51     }
52     int mid=(xtree[rn].l+xtree[rn].r)>>1;
53     if(le>mid)
54     {
55         return que(le,ri,rn<<1|1);
56     }
57     else if(ri<=mid)
58     {
59         return que(le,ri,rn<<1);
60     }
61     else
62     {
63         return que(le,mid,rn<<1)+que(mid+1,ri,rn<<1|1);
64     }
65 }
66 int main()
67 {
68     char str[10];
69     int n,m,a,b,c=1;
70     scanf("%d",&n);
71     while(n--)
72     {
73   printf("Case %d:\n",c);
74         scanf("%d",&m);
75         build(1,m,1);
76         while(scanf("%s",str))
77         {
78             if(str[0]=='E')
79             break;
80             if(str[0]=='Q')
81             {
82                 scanf("%d%d",&a,&b);
83                 printf("%d\n",que(a,b,1));
84             }
85             else if(str[0]=='A')
86             {
87                 scanf("%d%d",&a,&b);
88                 update(a,b,1);
89             }
90             else if(str[0]=='S')
91             {
92                 scanf("%d%d",&a,&b);
93                 update(a,-b,1);
94             }
95         }
96   c++;
97     }
98     return 0;
99 }

底下的是HH风格的代码

View Code

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #define maxn 50007
 5 using namespace std;
 6 int a[maxn*4];
 7 int n;
 8 void pushup(int rt)
 9 {
10     a[rt] = a[rt<<1] + a[rt<<1|1];
11 }
12 void build(int l,int r,int rt)
13 {
14     if (l == r)
15     {
16         scanf("%d",&a[rt]);
17         return ;
18     }
19     int m = (l + r)>>1;
20     build(l,m,rt<<1);
21     build(m + 1,r,rt<<1|1);
22     pushup(rt);
23 }
24 void update(int l,int r,int pos,int sc,int rt)
25 {
26     if (l == r)
27     {
28         a[rt] += sc;
29         return ;
30     }
31     int m = (l + r)>>1;
32     if (pos <= m) update(l,m,pos,sc,rt<<1);
33     else  update(m + 1,r,pos,sc,rt<<1|1);
34     pushup(rt);
35 }
36 int query(int l,int r,int L,int R,int rt)
37 {
38     if (l >= L && r <= R)
39     {
40         return a[rt];
41     }
42     int m = (l + r)>>1;
43     int res = 0;
44     if (L <= m) res += query(l,m,L,R,rt<<1);
45     if (R > m) res += query(m + 1,r,L,R,rt<<1|1);
46     return res;
47 }
48 int main()
49 {
50     //freopen("in.txt","r",stdin);
51    int t,b,c,cas = 1;
52    char op[10];
53    scanf("%d",&t);
54    while (t--)
55    {
56         printf("Case %d:\n",cas++);
57        scanf("%d",&n);
58        build(0,n - 1,1);
59        while (scanf("%s",op))
60        {
61            if (op[0] == 'E') break;
62            scanf("%d%d",&b,&c);
63            if (op[0] == 'A')
64            {
65                update(0,n - 1,b - 1,c,1);
66            }
67            else if (op[0] == 'S')
68            {
69                update(0,n - 1,b - 1,-c,1);
70            }
71            else
72            {
73                int ans = query(0,n - 1,b - 1,c - 1,1);
74                printf("%d\n",ans);
75            }
76        }
77    }
78     return 0;
79 }