#include<iostream>
#include<cstring>
#include<stdlib.h>
#include<time.h>
using namespace std;
const int N=50010;
int n,m;
int cnt;
struct node{
int l;
int r;
int val;
int key;
int sz;
}fhq[N*40];
struct nd{
int l;
int r;
int root;
}tr[N<<2];
int w[N];
int x,y,z;
void update(int u)
{
fhq[u].sz=fhq[fhq[u].l].sz+1+fhq[fhq[u].r].sz;
}
void split(int now,int val,int &x,int &y)
{
if(!now)
{
x=0,y=0;
return;
}
if(fhq[now].val<=val)
{
x=now;
split(fhq[now].r,val,fhq[now].r,y);
}
else
{
y=now;
split(fhq[now].l,val,x,fhq[now].l);
}
update(now);
}
int merge(int x,int y)
{
if(!x || !y) return x|y;
if(fhq[x].key>fhq[y].key)
{
fhq[x].r=merge(fhq[x].r,y);
update(x);
return x;
}
else
{
fhq[y].l=merge(x,fhq[y].l);
update(y);
return y;
}
}
int newnode(int val)
{
++cnt;
fhq[cnt].val=val;
fhq[cnt].sz=1;
fhq[cnt].key=rand();
return cnt;
}
int getrank(int &root,int val)
{
split(root,val-1,x,y);
int res=fhq[x].sz;
root=merge(x,y);
return res;
}
int kth(int &root,int k)
{
int now=root;
while(now)
{
if(fhq[fhq[now].l].sz+1==k)
break;
else if(fhq[fhq[now].l].sz>=k)
now=fhq[now].l;
else
k-=fhq[fhq[now].l].sz+1,now=fhq[now].r;
}
return fhq[now].val;
}
void insert(int &root,int val)
{
split(root,val-1,x,y);
root=merge(merge(x,newnode(val)),y);
}
void del(int &root,int val)
{
split(root,val,x,y);
split(x,val-1,x,z);
z=merge(fhq[z].l,fhq[z].r);
root=merge(merge(x,z),y);
}
int pre(int &root,int val)
{
split(root,val-1,x,y);
int now=x;
int res=0;
while(fhq[now].r)
now=fhq[now].r;
res=fhq[now].val;
if(!now)
res=-1e9;
root=merge(x,y);
return res;
}
int next(int &root,int val)
{
split(root,val,x,y);
int now=y;
while(fhq[now].l)
now=fhq[now].l;
int res=fhq[now].val;
if(!res)
res=1e9;
root=merge(x,y);
return res;
}
void build(int u,int l,int r)
{
tr[u]={
l,r};
for(int i=l;i<=r;i++)
insert(tr[u].root,w[i]);
if(l==r) return ;
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
}
void mdf(int u,int x,int v)
{
del(tr[u].root,w[x]);
insert(tr[u].root,v);
if(tr[u].l==tr[u].r) return ;
int mid=tr[u].l+tr[u].r>>1;
if(x<=mid)
mdf(u<<1,x,v);
else
mdf(u<<1|1,x,v);
}
int qrrank(int u,int l,int r,int v)
{
if(tr[u].l>=l && tr[u].r<=r)
return getrank(tr[u].root,v);
int mid=tr[u].l+tr[u].r>>1;
int res=0;
if(l<=mid)
res+=qrrank(u<<1,l,r,v);
if(r>mid)
res+=qrrank(u<<1|1,l,r,v);
return res;
}
int qrkth(int l,int r,int k)
{
int L=0,R=1e8;
while(L<R)
{
int mid=L+R+1>>1;
if(qrrank(1,l,r,mid)<k)
L=mid;
else
R=mid-1;
}
return L;
}
int get_pre(int u,int l,int r,int x)
{
if(tr[u].l>=l && tr[u].r<=r)
return pre(tr[u].root,x);
int mid=tr[u].l+tr[u].r>>1;
int res=-1e9;
if(l<=mid)
res=get_pre(u<<1,l,r,x);
if(r>mid)
res=max(res,get_pre(u<<1|1,l,r,x));
return res;
}
int get_next(int u,int l,int r,int x)
{
if(tr[u].l>=l && tr[u].r<=r)
return next(tr[u].root,x);
int mid=tr[u].l+tr[u].r>>1;
int res=1e9;
if(l<=mid)
res=get_next(u<<1,l,r,x);
if(r>mid)
res=min(res,get_next(u<<1|1,l,r,x));
return res;
}
int main()
{
srand(time(NULL));
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>w[i];
build(1,1,n);
while(m--)
{
int op;
cin>>op;
if(op==1)
{
int l,r,x;
cin>>l>>r>>x;
cout<<qrrank(1,l,r,x)+1<<endl;
}
else if(op==2)
{
int l,r,x;
cin>>l>>r>>x;
cout<<qrkth(l,r,x)<<endl;
}
else if(op==3)
{
int x,v;
cin>>x>>v;
mdf(1,x,v);
w[x]=v;
}
else if(op==4)
{
int l,r,x;
cin>>l>>r>>x;
cout<<get_pre(1,l,r,x)<<endl;
}
else if(op==5)
{
int l,r,x;
cin>>l>>r>>x;
cout<<get_next(1,l,r,x)<<endl;
}
}
return 0;
}
京公网安备 11010502036488号