Fork me on GitHub

[LA-2191] Potentiometers 树状数组

发表于 | 分类于
字数统计: 300字 | 阅读时长 ≈ 2分钟

题面

传送门:LA-2191

题目大意:基本树状数组的操作，把add(x,d)改成了S(x,d)，把第x位上的变成d.

样例

3
100
100
100
M 1 1
M 1 3
S 2 200
M 1 2
S 3 0
M 2 3
END
10
1
2
3
4
5
6
7
8
9
10
M 1 10
END
0
Sample Output
Case 1:
100
300
300
200
Case 2:
55

代码

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
#include<bits/stdc++.h>
using namespace std;  
const int MAXN=200000+10;  
int a[MAXN],c[MAXN],n;  
inline int lowbit(const int &x){return x&(-x);}  
void add(int x,int d)  
{  
    while(x<=n)  
    {  
        c[x]+=d;  
        x+=lowbit(x);  
    }  
}  
long long sum(int L,int R)  
{  
    int x=R;  
    long long ans=0;  
    while(x>0)  
    {  
        ans+=c[x];  
        x-=lowbit(x);  
    }  
    return ans;  
}  
int main(int argc,char *argv[])  
{  
    int kase=1;  
    while(scanf("%d",&n),n)  
    {  
        if(kase!=1)  
            printf("\n");  
        printf("Case %d:\n",kase++);  
        memset(c,0,sizeof(c));  
        for(int i=1;i<=n;i++)  
        {  
                scanf("%d",&a[i]);  
                add(i,a[i]);  
        }                 
        char action[10];          
        while(scanf("%s",action),strcmp(action,"END"))  
        {  
            int x,y;  
            scanf("%d%d",&x,&y);  
            if(action[0]=='S')  
            {  
                    add(x,y-a[x]);  
                    a[x]=y;  
            }  
            else   
            { printf("%lld\n",sum(x,y)-sum(1,x-1));}  
        }  
    }  
    return 0;
}