然而我还是在继续刷水题。。。
终于解开了区间第k大的心结。。。
比较裸的线段树套平衡树，比较不好想的是求区间第k大时需要二分一下答案，然后问题就转化为了第一个操作。复杂度nlog3n。跑的比较慢。。。
在查前驱后继的时候写错了。。。如果要直接赋值ans的话前驱是k[x]<=z,后继是k[x]<z,如果都写<的话需要取max和min。。。（不是第一次犯这种错了）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lc x*2,l,mid
#define rc x*2+1,mid+1,r
#define ls(x) ch[x][0]
#define rs(x) ch[x][1]
#define inf 0x3f3f3f3f
using namespace std;
int n,m;
int root[*];
int size[*],k[*];
int ch[*][],fa[*];
int a[];
int cnt;
inline void push_up(int x)
{
size[x]=size[ch[x][]]+size[ch[x][]]+;
return ;
}
inline void rotate(int p)
{
int q=fa[p],y=fa[q],x=(ch[q][]==p);
ch[q][x]=ch[p][x^];fa[ch[q][x]]=q;
ch[p][x^]=q;fa[q]=p;fa[p]=y;
if(y)
{
if(ls(y)==q)ch[y][]=p;
else ch[y][]=p;
}
push_up(q);push_up(p);
}
inline void splay(int now,int x)
{
for(int y;y=fa[x];rotate(x))
{
if(fa[y])
{
if((ls(y)==x&&ls(fa[y])==y)||(rs(y)==x&&rs(fa[y])==y))rotate(y);
else rotate(x);
}
}
root[now]=x;
}
inline void insert(int now,int x,int z)
{
size[x]++;
while(ch[x][k[x]<z])x=ch[x][k[x]<z],size[x]++;
ch[x][k[x]<z]=++cnt;fa[cnt]=x;size[cnt]=;k[cnt]=z;splay(now,cnt);
}
inline void build(int x,int l,int r)
{
root[x]=++cnt;k[cnt]=a[l];size[cnt]=;
for(int i=l+;i<=r;i++)insert(x,root[x],a[i]);
int mid=(l+r)>>;
if(l<r)build(lc),build(rc);
return ;
}
inline int fd(int x,int z)
{
int ans=;
while(x)
{
if(k[x]>z)
{
x=ch[x][];
}
else ans+=size[ch[x][]]+,x=ch[x][];
}
return ans;
}
inline int qur(int x,int l,int r,int ll,int rr,int kk)
{
if(ll<=l&&rr>=r)
{
return fd(root[x],kk);
}
int mid=(l+r)>>;
int ans=;
if(ll<=mid)ans+=qur(lc,ll,rr,kk);
if(rr>mid)ans+=qur(rc,ll,rr,kk);
return ans;
}
inline int find(int x,int z)
{
if(k[x]==z)return x;
while(ch[x][k[x]<z])
{
x=ch[x][k[x]<z];if(k[x]==z)return x;
}
return ;
}
inline void del(int now,int x)
{
splay(now,x);
if(!ch[x][])root[now]=ch[x][],fa[ch[x][]]=;
else if(!ch[x][])root[now]=ch[x][],fa[ch[x][]]=;
else
{
fa[ch[x][]]=;int tmp=ch[x][];
while(ch[tmp][])tmp=ch[tmp][];
splay(now,tmp);ch[tmp][]=ch[x][];fa[ch[x][]]=tmp;push_up(tmp);
}
}
inline void gai(int x,int l,int r,int pos,int z)
{
insert(x,root[x],z);
int x1=find(root[x],a[pos]);
del(x,x1);
if(l==r)return ;
int mid=(l+r)>>;
if(pos<=mid)gai(lc,pos,z);
else gai(rc,pos,z);
}
inline int pre(int x,int z)
{
int ans=-inf;
while(ch[x][k[x]<=z])
{
if(k[x]<=z)ans=k[x];
x=ch[x][k[x]<=z];
}if(k[x]<=z)ans=max(ans,k[x]);
return ans;
}
inline int suc(int x,int z)
{
int ans=inf;
while(ch[x][k[x]<z])
{
if(k[x]>=z)ans=k[x];
x=ch[x][k[x]<z];
}if(k[x]>=z)ans=min(ans,k[x]);
return ans;
}
inline int qur_pre(int x,int l,int r,int ll,int rr,int kk)
{
if(l>=ll&&r<=rr)
{
return pre(root[x],kk);
}
int ans=-inf;
int mid=(l+r)>>;
if(ll<=mid)ans=max(ans,qur_pre(lc,ll,rr,kk));
if(rr>mid)ans=max(ans,qur_pre(rc,ll,rr,kk));
return ans;
}
inline int qur_suc(int x,int l,int r,int ll,int rr,int kk)
{
if(l>=ll&&r<=rr)
{
return suc(root[x],kk);
}
int ans=inf;
int mid=(l+r)>>;
if(ll<=mid)ans=min(ans,qur_suc(lc,ll,rr,kk));
if(rr>mid)ans=min(ans,qur_suc(rc,ll,rr,kk));
return ans;
}
int mn,mx;
int main()
{
scanf("%d%d",&n,&m);mn=inf;mx=-inf;
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);mn=min(mn,a[i]);mx=max(mx,a[i]);
}
build(,,n);
for(int i=;i<=m;i++)
{
int t1;
scanf("%d",&t1);
int l,r,kk;
if(t1==)
{
scanf("%d%d%d",&l,&r,&kk);
printf("%d\n",qur(,,n,l,r,kk-)+);
}
else if(t1==)
{
scanf("%d%d%d",&l,&r,&kk);
int ha=mn;int ta=mx;
while(ha<=ta)
{
int mid=(ha+ta)>>;
if(qur(,,n,l,r,mid)<kk)ha=mid+;
else ta=mid-;
}
printf("%d\n",ha);
}
else if(t1==)
{
scanf("%d%d",&l,&kk);
gai(,,n,l,kk);a[l]=kk;
}
else if(t1==)
{
scanf("%d%d%d",&l,&r,&kk);
printf("%d\n",qur_pre(,,n,l,r,kk-));
}
else
{
scanf("%d%d%d",&l,&r,&kk);
printf("%d\n",qur_suc(,,n,l,r,kk+));
}
}
return ;
}