AcWing 242. 一个简单的整数问题
原题链接
简单
作者:
bruce
,
2021-01-21 13:32:17
,
所有人可见
,
阅读 303
#include<iostream>
#include<vector>
#include<string>
using namespace std;
const int N = 100010;
int a[N], b[N], c[N], n, m;
#define lowbit(i) ((i) & (-i))
typedef long long LL;
void update(int x, int v)
{
for(int i= x;i<=n;i+=lowbit(i))
c[i] += v;
}
LL getSum(int x)
{
LL sum = 0;
for(int i =x; i>0; i-=lowbit(i))
sum += c[i];
return sum;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) scanf("%d", &a[i]);
for(int i=1;i<=n;i++) update(i, a[i] - a[i-1]);
while(m--)
{
char c;
int l, r, d;
cin>>c;
if(c == 'C')
{
scanf("%d%d%d", &l, &r, &d);
update(l, d);
update(r+1, -d);
}
else if(c=='Q')
{
scanf("%d", &l);
cout<<getSum(l)<<endl;
}
}
}