题目描述
线段树
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define LL long long
#define lc p << 1
#define lr p << 1 | 1
const int MX = 1e5 + 5;
LL N,M;
LL w[MX];
struct node
{
LL l,r,sum;
LL add;
}tr[4 * MX];
void pushup(LL p)
{
tr[p].sum = tr[lc].sum + tr[lr].sum;
}
void pushdown(LL p)
{
if(tr[p].add)
{
tr[lc].sum += tr[p].add * (tr[lc].r - tr[lc].l + 1);
tr[lr].sum += tr[p].add * (tr[lr].r - tr[lr].l + 1);
tr[lc].add += tr[p].add;
tr[lr].add += tr[p].add;
tr[p].add = 0;
}
}
void build(LL p , LL l , LL r)
{
tr[p] = {l , r , w[l]};
if(l == r) return;
LL mid = (l + r) >> 1;
build(lc , l , mid);
build(lr , mid + 1 , r);
tr[p].sum += tr[lc].sum + tr[lr].sum;
}
LL query(LL p , LL x)
{
if(tr[p].l == x && tr[p].r == x)
{
return tr[p].sum;
}
pushdown(p);
LL ans = 0;
LL mid = (tr[p].l + tr[p].r) >> 1;
if(x <= mid) ans = query(lc , x);
if(x > mid) ans = query(lr , x);
return ans;
}
void update(LL p , LL x , LL y , LL k)
{
if(x <= tr[p].l && tr[p].r <= y)
{
tr[p].sum += (tr[p].r - tr[p].l + 1) * k;
tr[p].add += k;
return;
}
LL mid = (tr[p].l + tr[p].r) >> 1;
pushdown(p);
if(x <= mid) update(lc , x , y , k);
if(y > mid) update(lr , x , y , k);
pushup(p);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> M;
for(int i = 1 ; i <= N ; i++)
{
cin >> w[i];
}
build(1 , 1 , N);
while(M--)
{
char c;
cin >> c;
if(c == 'Q')
{
LL x;
cin >> x;
cout << query(1 , x) << endl;
}
else if(c == 'C')
{
LL l,r,x;
cin >> l >> r >> x;
update(1 , l , r , x);
}
}
return 0;
}