【BZOJ2989】数列（二进制分组，主席树）
题面
权限题啊。。。
Description
给定一个长度为n的正整数数列a[i]。
定义2个位置的graze值为两者位置差与数值差的和，即graze(x,y)=|x-y|+|a[x]-a[y]|。
2种操作（k都是正整数）：
1.Modify x k：将第x个数的值修改为k。
2.Query x k：询问有几个i满足graze(x,i)<=k。因为可持久化数据结构的流行，询问不仅要考虑当前数列，还要
考虑任意历史版本，即统计任意位置上出现过的任意数值与当前的a[x]的graze值<=k的对数。（某位置多次修改为
同样的数值，按多次统计）
Input
第1行两个整数n,q。分别表示数列长度和操作数。
第2行n个正整数，代表初始数列。
第3–q+2行每行一个操作。
Output
对于每次询问操作，输出一个非负整数表示答案
Sample Input
3 5
2 4 3
Query 2 2
Modify 1 3
Query 2 2
Modify 1 2
Query 1 1
Sample Output
2
3
3
HINT
N<=60000 修改操作数<=40000 询问<=50000 Max{a[i]}含修改<=100000
题解
其实这题并不需要支持强制在线，所以二进制分组被CDQ分治打爆了。
我们对于每个组开主席树，每次询问相当于在每个组内都查询一次求和，
好暴力啊。。。。。
然而复杂度\(O(nlog^2n)\)，惨遭\(CDQ\)分治打爆。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
#define ll long long
#define inf 1000000000
#define MAX 200200
#define MAXNODE MAX<<5
#define py 65000
#define N 200000
#define pi pair<int,int>
#define mp make_pair
#define pb push_back
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
char ch[20];
struct Node{int ls,rs,v;}t[MAXNODE];
int top,St[MAXNODE];bool vis[MAXNODE];
int NewNode(){vis[St[top]]=true;return St[top--];}
int Query(int A,int B,int l,int r,int L,int R)
{
if(L<=l&&r<=R)return t[B].v-t[A].v;
int mid=(l+r)>>1,ret=0;
if(L<=mid)ret+=Query(t[A].ls,t[B].ls,l,mid,L,R);
if(R>mid)ret+=Query(t[A].rs,t[B].rs,mid+1,r,L,R);
return ret;
}
void modify(int &x,int ff,int l,int r,int p)
{
t[x=NewNode()]=t[ff];t[x].v+=1;if(l==r)return;
int mid=(l+r)>>1;
if(p<=mid)modify(t[x].ls,t[ff].ls,l,mid,p);
else modify(t[x].rs,t[ff].rs,mid+1,r,p);
}
void Del(int &x)
{
if(!vis[x])return;
St[++top]=x;vis[x]=false;
Del(t[x].ls);Del(t[x].rs);
t[x].v=0;x=0;
}
vector<pi> v[20];
int rt[20][MAX],Top;
void insert(int x,int y)
{
v[++Top].pb(mp(x,y));
modify(rt[Top][1],rt[Top][0],1,N,y);
while(Top>1&&v[Top-1].size()==v[Top].size())
{
int t1=0,t2=0;vector<pi> t;
for(int i=1;i<=v[Top-1].size();++i)Del(rt[Top-1][i]);
for(int i=1;i<=v[Top].size();++i)Del(rt[Top][i]);
while(t1<v[Top-1].size()||t2<v[Top].size())
{
if(t1<v[Top-1].size()&&(t2==v[Top].size()||v[Top-1][t1]<v[Top][t2]))
t.pb(v[Top-1][t1++]);
else t.pb(v[Top][t2++]);
modify(rt[Top-1][t1+t2],rt[Top-1][t1+t2-1],1,N,t[t1+t2-1].second);
}
v[Top-1]=t;v[Top].clear();Top--;
}
}
int Query(int x,int y,int d)
{
int ret=0;
for(int i=1;i<=Top;++i)
{
int k1=lower_bound(v[i].begin(),v[i].end(),mp(x+d,inf))-v[i].begin();
int k2=lower_bound(v[i].begin(),v[i].end(),mp(x-d,000))-v[i].begin();
ret+=Query(rt[i][k2],rt[i][k1],1,N,max(1,y-d),min(y+d,N));
}
return ret;
}
int n,Q,a[MAX];
int main()
{
n=read();Q=read();
for(int i=1;i<MAXNODE;++i)St[++top]=i,vis[i]=false;
for(int i=1;i<=n;++i)a[i]=read(),insert(a[i]+i,a[i]-i+py);
while(Q--)
{
scanf("%s",ch);int x=read(),y=read();
if(ch[0]=='Q')printf("%d\n",Query(a[x]+x,a[x]-x+py,y));
else a[x]=y,insert(a[x]+x,a[x]-x+py);
}
return 0;
}
