IV.【模板】二逼平衡树（树套树）
树状数组套权值线段树最好了……\(n\log^2n\)的复杂度可比\(n\log^3n\)的什么线段树套平衡树要强一百万倍！其实是我不会写
分析一下操作：
-
二分出来最大的\(<k\)的数后直接权值线段树上查询前缀和。
-
就是II.Dynamic Rankings。
-
直接修改。
-
权值线段树上二分前驱。
-
权值线段树上二分后继。
操作全都是\(O(\log^2n)\)的。
敲出来，一遍\(90\%\)，TLE一个点，祭出快读，AC。
代码：
#include<bits/stdc++.h>
using namespace std;
#define mid ((l+r)>>1)
int n,m,cnt,bin[1001000],tp,root[50100],lim,val[50100];
struct node{
int lson,rson,sum;
}seg[5010000];
vector<int>v;
inline void newnode(int &x){
if(!tp)x=++cnt;
else x=bin[tp--];
}
inline void segmod(int &x,int l,int r,int P,int val){
if(l>P||r<P)return;
if(!x)newnode(x);
seg[x].sum+=val;
if(l!=r)segmod(seg[x].lson,l,mid,P,val),segmod(seg[x].rson,mid+1,r,P,val);
if(!seg[x].sum)bin[++tp]=x,x=0;
}
inline void finmod(int x,int P,int k){
while(x<=n)segmod(root[x],1,lim,P,k),x+=x&-x;
}
inline void modify(int x,int y){
y=lower_bound(v.begin(),v.end(),y)-v.begin()+1;
finmod(x,val[x],-1);
finmod(x,val[x]=y,1);
}
inline int segkth(vector<int>&x,vector<int>&y,int l,int r,int k){
int lsum=0;
if(l==r)return v[l-1];
for(auto i:x)lsum+=seg[seg[i].lson].sum;
for(auto i:y)lsum-=seg[seg[i].lson].sum;
if(lsum>=k){
for(auto &i:x)i=seg[i].lson;
for(auto &i:y)i=seg[i].lson;
return segkth(x,y,l,mid,k);
}else{
for(auto &i:x)i=seg[i].rson;
for(auto &i:y)i=seg[i].rson;
return segkth(x,y,mid+1,r,k-lsum);
}
}
inline int finkth(int l,int r,int k){
vector<int>x,y;
l--;
while(l)y.push_back(root[l]),l-=l&-l;
while(r)x.push_back(root[r]),r-=r&-r;
return segkth(x,y,1,lim,k);
}
inline int segrak(int x,int l,int r,int L,int R){
if(!x||l>R||r<L)return 0;
if(L<=l&&r<=R)return seg[x].sum;
return segrak(seg[x].lson,l,mid,L,R)+segrak(seg[x].rson,mid+1,r,L,R);
}
inline int finrak(int x,int y){
int sum=0;
while(x)sum+=segrak(root[x],1,lim,1,y),x-=x&-x;
return sum;
}
inline int rak(int l,int r,int x){
x=lower_bound(v.begin(),v.end(),x)-v.begin();
return finrak(r,x)-finrak(l-1,x)+1;
}
inline int segpre(vector<int>&x,vector<int>&y,int l,int r,int k){
int sum=0;
for(auto i:x)sum+=seg[i].sum;
for(auto i:y)sum-=seg[i].sum;
if(!sum||l>k)return *v.begin();
if(l==r)return v[l-1];
vector<int>p,q;
p.clear(),q.clear();
for(auto i:x)p.push_back(seg[i].rson);
for(auto i:y)q.push_back(seg[i].rson);
int tmp=segpre(p,q,mid+1,r,k);
if(tmp!=*v.begin())return tmp;
p.clear(),q.clear();
for(auto i:x)p.push_back(seg[i].lson);
for(auto i:y)q.push_back(seg[i].lson);
return segpre(p,q,l,mid,k);
}
inline int finpre(int l,int r,int k){
k=lower_bound(v.begin(),v.end(),k)-v.begin();
vector<int>x,y;
l--;
while(l)y.push_back(root[l]),l-=l&-l;
while(r)x.push_back(root[r]),r-=r&-r;
return segpre(x,y,1,lim,k);
}
inline int segsuf(vector<int>&x,vector<int>&y,int l,int r,int k){
int sum=0;
for(auto i:x)sum+=seg[i].sum;
for(auto i:y)sum-=seg[i].sum;
if(!sum||r<k)return *v.rbegin();
if(l==r)return v[l-1];
vector<int>p,q;
p.clear(),q.clear();
for(auto i:x)p.push_back(seg[i].lson);
for(auto i:y)q.push_back(seg[i].lson);
int tmp=segsuf(p,q,l,mid,k);
if(tmp!=*v.rbegin())return tmp;
p.clear(),q.clear();
for(auto i:x)p.push_back(seg[i].rson);
for(auto i:y)q.push_back(seg[i].rson);
return segsuf(p,q,mid+1,r,k);
}
inline int finsuf(int l,int r,int k){
k=upper_bound(v.begin(),v.end(),k)-v.begin()+1;
vector<int>x,y;
l--;
while(l)y.push_back(root[l]),l-=l&-l;
while(r)x.push_back(root[r]),r-=r&-r;
return segsuf(x,y,1,lim,k);
}
struct opt{
int op,t1,t2,t3;
}q[50100];
inline void read(int &x){
x=0;
char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
inline void print(int x){
if(x<0)putchar('-'),print(-x);
else if(x<=9)putchar('0'+x);
else print(x/10),putchar('0'+x%10);
}
int main(){
read(n),read(m),v.push_back(-2147483647),v.push_back(2147483647);
for(int i=1;i<=n;i++)read(val[i]),v.push_back(val[i]);
for(int i=1;i<=m;i++){
read(q[i].op),read(q[i].t1),read(q[i].t2);
if(q[i].op==3)v.push_back(q[i].t2);
else read(q[i].t3);
}
sort(v.begin(),v.end()),v.resize(lim=(unique(v.begin(),v.end())-v.begin()));
// for(auto x:v)printf("%d ",x);puts("");
for(int i=1;i<=n;i++)finmod(i,val[i]=lower_bound(v.begin(),v.end(),val[i])-v.begin()+1,1);
// puts("IN");
for(int i=1;i<=m;i++){
if(q[i].op==1)print(rak(q[i].t1,q[i].t2,q[i].t3)),putchar('\n');
if(q[i].op==2)print(finkth(q[i].t1,q[i].t2,q[i].t3)),putchar('\n');
if(q[i].op==3)modify(q[i].t1,q[i].t2);
if(q[i].op==4)print(finpre(q[i].t1,q[i].t2,q[i].t3)),putchar('\n');
if(q[i].op==5)print(finsuf(q[i].t1,q[i].t2,q[i].t3)),putchar('\n');
}
return 0;
}