蒟蒻树状数组版写腻了,于是来贡献一发CDQ分治版的
总所周知CDQ分治是一个分治(废话),那我们首先第一步就要把子问题划分出来
我们还是用到差分序列的思想,讲区间修改改成差分序列上的两个点
对于询问,则是差分序列某个位置上的前缀和,显然该位置后面的对其没有贡献
于是我们按时间顺序进行分治,内部合并时再按操作的位置排序
这样一来,我们就可以很轻松的处理左边对于右边的贡献
而右边对右边的贡献我们已经在分治成子问题时求解完成
于是乎本题完
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const int N = 400010;
struct nod
{
ll x , y;
int id;
} p[N] , tmp[N];
ll ans[N] , num[N] , tot;
int n , m ;
ll a[N];
char c;
void solve(int l , int r)
{
if(l >= r) return;
int mid = (l + r) >> 1 , i = l , j = mid + 1 , k = 0 , sum = 0;
solve(l , mid) ; solve(mid + 1 , r);
while(i <= mid && j <= r)
{
if(p[i].x <= p[j].x)
{
if(!p[i].id)
sum += p[i].y;
tmp[k++] = p[i++];
}
else
{
if(p[j].id)
ans[p[j].id] += sum;
tmp[k++] = p[j++];
}
}
while(i <= mid) tmp[k++] = p[i++];
while(j <= r)
{
if(p[j].id)
ans[p[j].id] += sum;
tmp[k++] = p[j++];
}
for(int i = 0 ; i < k ; i++) p[l + i] = tmp[i];
}//CDQ分治
int main()
{
scanf("%d%d" , &n , &m);
for(int i = 1 ; i <= n ; i++) cin >> a[i];
int cnt = 0;
for(int i = 1 , l , r , d ; i <= m ; i++)
{
cin >> c;
if(c == 'C')
{
cin >> l >> r >> d;
p[++cnt].x = l ; p[cnt].y = d ; p[cnt].id = 0;
p[++cnt].x = r + 1 ; p[cnt].y = -d ; p[cnt].id = 0;
}
else
{
cin >> l;
p[++cnt].x = l ; p[cnt].id = ++tot ; num[tot] = l;
}
}
solve(1 , cnt);
for(int i = 1 ; i <= tot ; i++) printf("%d\n" , ans[i] + a[num[i]]);
return 0;
}
orz