#include<cstdio>
#include<ctime>
#include<cstdlib>
#include<iostream>
#define M 3000009
using namespace std;
struct shu
{
int l,r,sum1,zhi,dui,sum2;
}a[M];
int n,root[M],size,ans,b[M],m;
void you(int &a1)
{
int t=a[a1].l;
a[a1].l=a[t].r;
a[t].r=a1;
a[t].sum1=a[a1].sum1;
a[a1].sum1=a[a[a1].l].sum1+a[a[a1].r].sum1+a[a1].sum2;
a1=t;
return;
}
void zuo(int &a1)
{
int t=a[a1].r;
a[a1].r=a[t].l;
a[t].l=a1;
a[t].sum1=a[a1].sum1;
a[a1].sum1=a[a[a1].l].sum1+a[a[a1].r].sum1+a[a1].sum2;
a1=t;
return;
}
void cha(int &a1,int a2)
{
if(!a1)
{
size++;
a1=size;
a[a1].sum1=;
a[a1].sum2=;
a[a1].zhi=a2;
a[a1].dui=rand();
return;
}
a[a1].sum1++;
if(a[a1].zhi==a2)
{
a[a1].sum2++;
return;
}
if(a2<a[a1].zhi)
{
cha(a[a1].l,a2);
if(a[a[a1].l].dui<a[a1].dui)
you(a1);
}
else
{
cha(a[a1].r,a2);
if(a[a[a1].r].dui<a[a1].dui)
zuo(a1);
}
}
void shan(int &a1,int a2)
{
if(a1==)
return;
if(a[a1].zhi==a2)
{
if(a[a1].sum2>)
{
a[a1].sum2--;
a[a1].sum1--;
}
else if(a[a1].l*a[a1].r==)
a1=a[a1].l+a[a1].r;
else if(a[a[a1].l].dui<a[a[a1].r].dui)
{
you(a1);
shan(a1,a2);
}
else
{
zuo(a1);
shan(a1,a2);
}
return;
}
a[a1].sum1--;
if(a[a1].zhi<a2)
shan(a[a1].r,a2);
else
shan(a[a1].l,a2);
return;
}
int cha1(int a1,int a2)
{
if(!a1)
return ;
if(a[a1].zhi==a2)
return a[a[a1].l].sum1;
if(a[a1].zhi>a2)
return cha1(a[a1].l,a2);
return a[a[a1].l].sum1+a[a1].sum2+cha1(a[a1].r,a2);
}
void qian(int a1,int a2)
{
if(!a1)
return;
if(a[a1].zhi<a2)
{
ans=max(a[a1].zhi,ans);
qian(a[a1].r,a2);
}
else
qian(a[a1].l,a2);
return;
}
void hou(int a1,int a2)
{
if(!a1)
return;
if(a[a1].zhi>a2)
{
ans=min(a[a1].zhi,ans);
hou(a[a1].l,a2);
}
else
hou(a[a1].r,a2);
return;
}
void build(int a1,int l,int r,int x,int v)
{
cha(root[a1],v);
if(l==r)
return;
int mid=(l+r)>>;
if(x<=mid)
build(a1*,l,mid,x,v);
else
build(a1*+,mid+,r,x,v);
return;
}
void xicha1(int a1,int l,int r,int l1,int r1,int x)
{
if(l1<=l&&r1>=r)
{
ans+=cha1(root[a1],x);
return;
}
int mid=(l+r)>>;
if(l1<=mid)
xicha1(a1*,l,mid,l1,r1,x);
if(r1>mid)
xicha1(a1*+,mid+,r,l1,r1,x);
return;
}
void xicha2(int l1,int r1,int x)
{
int l2=,r2=,q=;
for(;l2<=r2;)
{
int mid=(l2+r2)>>;
ans=;
xicha1(,,n,l1,r1,mid);
if(ans<=x)
{
q=mid;
l2=mid+;
}
else
r2=mid-;
}
printf("%d\n",q);
}
void change(int a1,int l,int r,int l1,int x,int y)
{
shan(root[a1],y);
cha(root[a1],x);
if(l==r)
return;
int mid=(l+r)>>;
if(l1<=mid)
change(a1*,l,mid,l1,x,y);
else
change(a1*+,mid+,r,l1,x,y);
return;
}
void xiqian(int a1,int l,int r,int l1,int r1,int x)
{
if(l1<=l&&r1>=r)
{
qian(root[a1],x);
return;
}
int mid=(l+r)>>;
if(l1<=mid)
xiqian(a1*,l,mid,l1,r1,x);
if(r1>mid)
xiqian(a1*+,mid+,r,l1,r1,x);
return;
}
void xihou(int a1,int l,int r,int l1,int r1,int x)
{
if(l1<=l&&r1>=r)
{
hou(root[a1],x);
return;
}
int mid=(l+r)>>;
if(l1<=mid)
xihou(a1*,l,mid,l1,r1,x);
if(r1>mid)
xihou(a1*+,mid+,r,l1,r1,x);
return;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
scanf("%d",&b[i]);
for(int i=;i<=n;i++)
build(,,n,i,b[i]);
for(int i=;i<m;i++)
{
int a1,a2,a3,a4;
scanf("%d%d%d",&a1,&a2,&a3);
if(a1==)
{
scanf("%d",&a4);
ans=;
xicha1(,,n,a2,a3,a4);
printf("%d\n",ans);
}
if(a1==)
{
scanf("%d",&a4);
xicha2(a2,a3,a4);
}
if(a1==)
{
change(,,n,a2,a3,b[a2]);
b[a2]=a3;
}
if(a1==)
{
ans=;
scanf("%d",&a4);
xiqian(,,n,a2,a3,a4);
printf("%d\n",ans);
}
if(a1==)
{
scanf("%d",&a4);
ans=;
xihou(,,n,a2,a3,a4);
printf("%d\n",ans);
}
}
return ;
}
却是是二逼平衡树。