1 #include<cstdio>  2 #include<cstdlib>  3 #include<cmath>  4 #include<cstring>  5 #include<algorithm>  6 #include<iostream>  7 #include<vector>  8 #include<map>  9 #include<set> 10 #include<queue> 11 #define inf 1000000000 12 #define maxn 50000+100 13 #define maxm 2000000 14 #define eps 1e-10 15 #define ll long long 16 using namespace std; 17 inline int read() 18 { 19     int x=0,f=1;char ch=getchar(); 20     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 21     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 22     return x*f; 23 } 24 int n,m,tot,a[maxn],l[maxm],r[maxm],s[maxm],rnd[maxm],w[maxm],v[maxm]; 25 struct rec{int l,r,rt;}t[4*maxn]; 26 inline void pushup(int k) 27 {s[k]=s[l[k]]+s[r[k]]+w[k];} 28 inline void rturn(int &k) 29 {int t=l[k];l[k]=r[t];r[t]=k;s[t]=s[k];pushup(k);k=t;} 30 inline void lturn(int &k) 31 {int t=r[k];r[k]=l[t];l[t]=k;s[t]=s[k];pushup(k);k=t;} 32 void ins(int &k,int num) 33 { 34     if(!k) 35     {k=++tot;v[k]=num;s[k]=w[k]=1;l[k]=r[k]=0;rnd[k]=rand();return;} 36     s[k]++; 37     if(v[k]==num)w[k]++; 38     else if(num<v[k]) 39       {ins(l[k],num);if(rnd[l[k]]<rnd[k])rturn(k);} 40     else 41       {ins(r[k],num);if(rnd[r[k]]<rnd[k])lturn(k);}   42 } 43 void del(int &k,int num) 44 { 45     if(v[k]==num) 46     { 47         if(w[k]>1){w[k]--;s[k]--;} 48         else if(l[k]*r[k]==0)k=l[k]+r[k]; 49         else if(rnd[l[k]]<rnd[r[k]]) 50          {rturn(k);del(k,num);} 51         else {lturn(k);del(k,num);}  52         return; 53     } 54     s[k]--; 55     if(num<v[k])del(l[k],num);else del(r[k],num); 56 } 57 int rank(int k,int num) 58 { 59     if(!k) return 0; 60     if(v[k]==num)return s[l[k]]; 61     else if(num<v[k])return rank(l[k],num); 62     else return s[l[k]]+w[k]+rank(r[k],num); 63 } 64 int pre(int k,int num) 65 { 66     if(!k)return -inf; 67     if(num<=v[k])return pre(l[k],num); 68     else  69     { 70         int t=pre(r[k],num); 71         return t==-inf?v[k]:t; 72     } 73 } 74 int suc(int k,int num) 75 { 76     if(!k)return inf; 77     if(num>=v[k])return suc(r[k],num); 78     else 79     { 80         int t=suc(l[k],num); 81         return t==inf?v[k]:t; 82     } 83 } 84 void build(int k,int x,int y) 85 { 86     int l=t[k].l=x,r=t[k].r=y, mid=(l+r)>>1; 87     for(int i=l;i<=r;i++)ins(t[k].rt,a[i]); 88     if(l==r)return; 89     build(k<<1,l,mid);build(k<<1|1,mid+1,r); 90 } 91 void change(int k,int x,int y) 92 { 93     int l=t[k].l,r=t[k].r,mid=(l+r)>>1; 94     del(t[k].rt,a[x]);ins(t[k].rt,y); 95     if(l==r)return; 96     if(x<=mid)change(k<<1,x,y);else change(k<<1|1,x,y); 97 } 98 int query(int k,int x,int y,int z) 99 {100     int l=t[k].l,r=t[k].r,mid=(l+r)>>1;101     if(l==x&&r==y)return rank(t[k].rt,z);102     if(y<=mid)return query(k<<1,x,y,z);103     else if(x>mid)return query(k<<1|1,x,y,z);104     else return(query(k<<1,x,mid,z)+query(k<<1|1,mid+1,y,z));105 }106 int getpre(int k,int x,int y,int z)107 {108     int l=t[k].l,r=t[k].r,mid=(l+r)>>1;109     if(l==x&&r==y)return(pre(t[k].rt,z));110     if(y<=mid)return getpre(k<<1,x,y,z);111     else if(x>mid)return getpre(k<<1|1,x,y,z);112     else return max(getpre(k<<1,x,mid,z),getpre(k<<1|1,mid+1,y,z));113 }114 int getsuc(int k,int x,int y,int z)115 {116     int l=t[k].l,r=t[k].r,mid=(l+r)>>1;117     if(l==x&&r==y)return(suc(t[k].rt,z));118     if(y<=mid)return getsuc(k<<1,x,y,z);119     else if(x>mid)return getsuc(k<<1|1,x,y,z);120     else return min(getsuc(k<<1,x,mid,z),getsuc(k<<1|1,mid+1,y,z));121 }122 123 int main()124 {125     freopen("input.txt","r",stdin);126     freopen("output.txt","w",stdout);127     n=read();m=read();128     for(int i=1;i<=n;i++)a[i]=read();129     build(1,1,n);130     //for(int k=1;k<=4*n;k++)cout<<t[k].l<<‘ ‘<<t[k].r<<‘ ‘<<t[k].rt<<endl;131     //for(int k=1;k<=4*n;k++)cout<<l[k]<<‘ ‘<<r[k]<<‘ ‘<<s[k]<<‘ ‘<<w[k]<<‘ ‘<<v[k]<<‘ ‘<<rnd[k]<<endl;132     int x,y,z,ch;133     while(m--)134     {135         ch=read();136         if(ch==3){x=read();y=read();change(1,x,y);a[x]=y;}  137         else{138             x=read();y=read();z=read();139             if(ch==2)140                 {141                 int l=0,r=inf;142                 while(l<=r)143                    {144                     int mid=(l+r)>>1;145                     if(query(1,x,y,mid)+1>z)r=mid-1;else l=mid+1;146                     //cout<<query(1,x,y,mid)<<"!!!!!!"<<endl;147                 }148                  printf("%d\n",r);149                 }150             if(ch==1)printf("%d\n",query(1,x,y,z)+1);151             if(ch==4)printf("%d\n",getpre(1,x,y,z));152             if(ch==5)printf("%d\n",getsuc(1,x,y,z));153             }    154       155     }156     return 0;157 }