~~不会 FHQ 啊/fad~~
如果平衡树维护的是有序序列可以试着用 BST 的性质来找每个区间的前驱/后缀然后再合并？
对 FHQ 不熟悉咱就不在您代码上修改了。
```cpp
int getPre(int &root,int v)//查找最大的比 v 小的数
{
int u=root,res=-INF;
while(u)
{
if(tree[u].v<v) res=max(res,tree[u].v),u=tree[u].s[1];
else u=tree[u].s[0];
}
return res;
}
int getSuc(int &root,int v)//查找最小的比 v 大的数
{
int u=root,res=INF;
while(u)
{
if(tree[u].v>v) res=min(res,tree[u].v),u=tree[u].s[0];
else u=tree[u].s[1];
}
return res;
}
int queryPre(int node,int l,int r,int x)//查找前驱
{
if(l<=tr1[node].l&&tr1[node].r<=r) return getPre(tr1[node].root,x);
int mid=tr1[node].l+tr1[node].r>>1;
int res=-INF;
if(l<=mid) res=max(res,queryPre(lnode,l,r,x));
if(r>mid) res=max(res,queryPre(rnode,l,r,x));
return res;
}
int querySuc(int node,int l,int r,int x)//查找后继
{
if(l<=tr1[node].l && tr1[node].r<=r) return getSuc(tr1[node].root,x);
int mid=tr1[node].l+tr1[node].r>>1;
int res=INF;
if(l<=mid) res=min(res,querySuc(lnode,l,r,x));
if(r>mid) res=min(res,querySuc(rnode,l,r,x));
return res;
}
```
by RemiliaScar1et @ 2021-04-20 16:22:10
@[RemiliaScarlet◎](/user/278259) 那不如帮我调一下新写的带修莫队（）
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10,inf=2147483647;
struct node
{
int l,r;
int p;
int num;
int k;
int id;
}q[N];
struct ch
{
int from,to;
int p;
} c[N];
int n,m,t;
int maxn;
int maxm;
int maxq,maxc;
int a[N],typ[N*2];
int bl[N],sq;
bool cmp(node x,node y)
{
if(bl[x.l]!=bl[y.l]) return x.l<y.l;
if(x.r!=y.r) return x.r<y.r;
return x.k>y.k;
}
int sn,b[N],bn[N],lbn[N],rbn[N],sum[N];
void change(int from,int to)
{
b[from]--;
b[to]++;
sum[bn[from]]--;
sum[bn[to]]++;
}
int get_rank(int x)
{
int i=1;
int ans=0;
while(rbn[i]<x)
{
ans+=sum[i];
i++;
}
int k=lbn[i];
while(k<x) ans+=b[k],k++;
return ans+1;
}
int get_key(int x)
{
int i=1;
int ans=0;
while(x>sum[i])
{
x-=sum[i];
i++;
}
int k=lbn[i];
while(x>b[k])
{
x-=b[k];
k++;
}
while(b[k]==0) k++;
return typ[k];
}
int ans[N];
signed main() {
cin>>n>>m;
sq=pow(n,0.6666);
for(int i=1;i<=n;i++)
{
bl[i]=(i-1)/sq+1;
cin>>a[i];
typ[++maxn]=a[i];
}
for(int i=1;i<=m;i++)
{
int op;
cin>>op;
if(op==1)
{
int x,l,r;
cin>>l>>r>>x;
int p=++maxq;
q[p].l=l;
q[p].r=r;
q[p].p=x;
q[p].k=maxc;
q[p].num=1;
q[p].id=p;
typ[++maxn]=x;
}
if(op==2)
{
int x,l,r;
cin>>l>>r>>x;
int p=++maxq;
q[p].l=l;
q[p].r=r;
q[p].p=x;
q[p].k=maxc;
q[p].id=p;
q[p].num=2;
}
if(op==3)
{
int p,v;
cin>>p>>v;
c[++maxc].from=a[p];
c[maxc].to=v;
c[maxc].p=p;
typ[++maxn]=v;
a[p]=v;
}
if(op==4)
{
int x,l,r;
cin>>l>>r>>x;
int p=++maxq;
q[p].l=l;
q[p].r=r;
q[p].p=x;
q[p].num=4;
q[p].k=maxc;
q[p].id=p;
typ[++maxn]=x;
}
if(op==5)
{
int x,l,r;
cin>>l>>r>>x;
int p=++maxq;
q[p].l=l;
q[p].r=r;
q[p].p=x;
q[p].num=5;
q[p].k=maxc;
q[p].id=p;
typ[++maxn]=x;
}
}
//for(int i=1;i<=maxq;i++)
//cout<<"l:"<<q[i].l<<" r:"<<q[i].r<<" id:"<<q[i].id<<" p:"<<q[i].p<<" k:"<<q[i].k<<" op:"<<q[i].num<<endl;
//for(int i=1;i<=maxc;i++)
//cout<<c[i].from<<" "<<c[i].to<<endl;
sort(q+1,q+maxq+1,cmp);
sort(typ+1,typ+maxn+1);
maxm=unique(typ+1,typ+maxn+1)-typ-1;
//for(int i=1;i<=maxm;i++) cout<<typ[i]<<" ";
//cout<<endl;
sn=sqrt(maxm);
t=maxm/sn;
for(int i=1;i<=maxm;i++) bn[i]=(i-1)/sn+1;
for(int i=1;i<=t;i++) {
lbn[i]=(i-1)*sn+1;
rbn[i]=i*sn;
}
if(t*sq<n) {
t++;
lbn[t]=(t-1)*sn+1;
rbn[t]=n;
}
for(int i=1;i<=n;i++) a[i]=lower_bound(typ+1,typ+maxm+1,a[i])-typ;
for(int i=1;i<=maxq;i++)
if(q[i].num!=2)
{
q[i].p=lower_bound(typ+1,typ+maxm+1,q[i].p)-typ;
}
for(int i=1;i<=maxc;i++)
{
c[i].from=lower_bound(typ+1,typ+maxm+1,c[i].from)-typ;
c[i].to=lower_bound(typ+1,typ+maxm+1,c[i].to)-typ;
//cout<<typ[c[i].from]<<" "<<typ[c[i].to]<<endl;
}
int l=1,r=0,k=maxc;
for(int i=1;i<=maxq;i++)
{
int ql=q[i].l,qr=q[i].r,qk=q[i].k,op=q[i].num,p=q[i].p;
while(k<qk)
{
++k;
if(c[k].p>=l&&c[k].p<=r)
change(c[k].from,c[k].to);
a[c[k].p]=c[k].to;
}
while(k>qk)
{
if(c[k].p>=l&&c[k].p<=r)
change(c[k].to,c[k].from);
a[c[k].p]=c[k].from;
--k;
}
while(r<qr)
{
++r;
b[a[r]]++;
sum[bn[a[r]]]++;
}
while(l>ql)
{
--l;
b[a[l]]++;
sum[bn[a[l]]]++;
}
while(r>qr)
{
b[a[r]]--;
sum[bn[a[r]]]--;
--r;
}
while(l<ql)
{
b[a[l]]--;
sum[bn[a[l]]]--;
++l;
}
//cout<<q[i].id<<" "<<l<<" "<<r<<endl;
//cout<<l<<" "<<r<<" "<<k<<endl;
//for(int i=1;i<=t;i++) cout<<typ[lbn[i]]<<" "<<typ[rbn[i]]<<" "<<sum[i]<<endl;
//cout<<endl;
if(op==1) ans[q[i].id]=get_rank(p);
if(op==2) ans[q[i].id]=get_key(p);
if(op==4)
{
int rank=get_rank(p);
int val=get_key(rank-1);
if(rank>0&&rank<=r-l+1)
ans[q[i].id]=val;
else ans[q[i].id]=-inf;
}
if(op==5)
{
int rank=get_rank(p+1);
int val=get_key(rank);
if(rank>0&&rank<=r-l+1)
ans[q[i].id]=val;
else ans[q[i].id]=inf;
}
}
for(int i=1;i<=maxq;i++) cout<<ans[i]<<endl;
}
```
by koishi_offical @ 2021-06-13 17:12:45