hdu1166敌兵布阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<stdio.h>
#include<string.h>
#define N 500000
int sum[N];
inline int lowbit(int x)
{
return x&-x;
}
void add(int i,int x)
{
while(i<N)
{
sum[i]+=x;
i+=lowbit(i);
}
}
int getsum(int i){
int ans=0;
while(i>0){
ans+=sum[i];
i-=lowbit(i);
}
return ans;
}
int main()
{
int t,cs=0,n,i,a,b;
char op[10];
bool flag;
scanf("%d",&t);
while(t--){
++cs;
memset(sum,0,sizeof(sum));
printf("Case %d:n",cs);
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&a);
add(i,a);
}
getchar();
flag=true;
while(flag)
{
scanf("%s",op);
switch(op[0])
{
case 'Q':
scanf("%d%d",&a,&b);
printf("%dn",getsum(b)-getsum(a-1));
break;
case 'A':
scanf("%d%d",&a,&b);
add(a,b);
break;
case 'S':
scanf("%d%d",&a,&b);
add(a,-b);
break;
default:flag=false;
break;
}
}
}
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<stdio.h>
#include<string.h>
struct seg
{
int l;
int r;
int sum;
}T[150011];
void build(int l,int r,int rt)
{
T[rt].l=l;
T[rt].r=r;
T[rt].sum=0;
if(l==r)
return ;
int mid=(l+r)/2;
build(l,mid,2*rt);
build(mid+1,r,2*rt+1);
}
void add(int n,int d,int rt)
{
if(T[rt].l==T[rt].r)
{
if(T[rt].l==d);
T[rt].sum+=n;
return ;
}
int mid=(T[rt].l+T[rt].r)>>1;
if(d<=mid)
add(n,d,2*rt);
else
add(n,d,2*rt+1);
T[rt].sum=T[2*rt].sum+T[2*rt+1].sum;
}
int ans;
void query(int l,int r,int rt)
{
if(T[rt].l==l&&T[rt].r==r){
ans+=T[rt].sum;
return ;
}
if(T[rt].l==l&&T[rt].r==r)
{
ans+=T[rt].sum;
return ;
}
int mid=(T[rt].l+T[rt].r)>>1;
if(r<=mid)
query(l,r,2*rt);
else if(l>mid)
query(l,r,2*rt+1);
else
{
query(l,mid,2*rt);
query(mid+1,r,2*rt+1);
}
}
int main()
{
int t,cs=0,n,i,a,b;
char op[10];
bool flag;
scanf("%d",&t);
while(t--)
{
++cs;
printf("Case %d:n",cs);
scanf("%d",&n);
build(1,n,1);
for(i=1;i<=n;i++)
{
scanf("%d",&a);
add(a,i,1);
}
getchar();
flag=true;
while(flag)
{
ans=0;
scanf("%s",op);
switch(op[0])
{
case 'Q':
scanf("%d%d",&a,&b);
query(a,b,1);
printf("%dn",ans);
break;
case 'A':
scanf("%d%d",&a,&b);
add(b,a,1);
break;
case 'S':
scanf("%d%d",&a,&b);
add(-b,a,1);
break;
default:flag=false;
break;
}
}
}
return 0;
}