1 #include<cstdio>  2 #include<cmath>  3 #include<algorithm>  4 #include<cstring>  5 using namespace std;  6 int sum,sz,l[400],r[400],num[51001],a[51001],b[51001],x,y,k,n,m,op,tmp[2000];  7 void makeblock()  8 {  9     memcpy(b,a,sizeof(a)); 10     sz=sqrt((double)n*log2(n)); 11     for(sum=1;sum*sz<n;sum++) 12       { 13         l[sum]=(sum-1)*sz+1; 14         r[sum]=sum*sz; 15         for(int i=l[sum];i<=r[sum];i++) num[i]=sum; 16         sort(b+l[sum],b+r[sum]+1); 17       } 18     l[sum]=sz*(sum-1)+1; r[sum]=n; 19     for(int i=l[sum];i<=r[sum];i++) num[i]=sum; 20 } 21 inline void Update() 22 { 23     *lower_bound(b+l[num[x]],b+r[num[x]]+1,a[x])=y; 24     sort(b+l[num[x]],b+r[num[x]]+1); 25     a[x]=y; 26 } 27 inline void Rank() 28 { 29     int ans=0; 30     if(num[x]+1>=num[y]) {for(int i=x;i<=y;i++) if(a[i]<k) ans++;} 31     else 32       { 33         for(int i=x;i<=r[num[x]];i++) if(a[i]<k) ans++; 34         for(int i=l[num[y]];i<=y;i++) if(a[i]<k) ans++; 35         for(int i=num[x]+1;i<num[y];i++) ans+=lower_bound(b+l[i],b+r[i]+1,k)-(b+l[i]); 36       } 37     printf("%d\n",ans+1); 38 } 39 inline void Kth() 40 { 41     if(num[x]+1>=num[y]) 42       { 43         int en=0; 44         for(int i=x;i<=y;i++) tmp[++en]=a[i]; 45         sort(tmp+1,tmp+en+1); 46         printf("%d\n",tmp[k]); 47       } 48     else 49       { 50         int L=0,R=1000000001; 51         while(L!=R) 52           { 53             int mid=L+R>>1,cnt=0; 54             for(int i=x;i<=r[num[x]];i++) if(a[i]<mid) cnt++; 55             for(int i=l[num[y]];i<=y;i++) if(a[i]<mid) cnt++; //统计<mid的值数 56             for(int i=num[x]+1;i<num[y];i++) cnt+=lower_bound(b+l[i],b+r[i]+1,mid)-(b+l[i]); 57             if(cnt>=k) R=mid; 58             else L=mid+1; 59           } 60         printf("%d\n",L-1); 61       } 62 } 63 inline void Front() 64 { 65     int ans=-2147483647;int* p; 66     if(num[x]+1>=num[y]) {for(int i=x;i<=y;i++) if(a[i]>ans && a[i]<k) ans=a[i];} 67     else 68       { 69         for(int i=x;i<=r[num[x]];i++) if(a[i]>ans && a[i]<k) ans=a[i]; 70         for(int i=l[num[y]];i<=y;i++) if(a[i]>ans && a[i]<k) ans=a[i]; 71         for(int i=num[x]+1;i<num[y];i++) 72           { 73             p=lower_bound(b+l[i],b+r[i]+1,k); 74             if(p!=b+l[i] && *(p-1)<k && *(p-1)>ans) ans=*(p-1); 75           } 76       } 77     printf("%d\n",ans); 78 } 79 inline void Next() 80 { 81     int ans=2147483647;int* p; 82     if(num[x]+1>=num[y]) {for(int i=x;i<=y;i++) if(a[i]<ans && a[i]>k) ans=a[i];} 83     else 84       { 85         for(int i=x;i<=r[num[x]];i++) if(a[i]<ans && a[i]>k) ans=a[i]; 86         for(int i=l[num[y]];i<=y;i++) if(a[i]<ans && a[i]>k) ans=a[i]; 87         for(int i=num[x]+1;i<num[y];i++) 88           { 89             p=upper_bound(b+l[i],b+r[i]+1,k); 90             if(p!=b+r[i]+1 && *p>k && *p<ans) ans=*p; 91           } 92       } 93     printf("%d\n",ans); 94 } 95 int main() 96 { 97     scanf("%d%d",&n,&m); 98     for(int i=1;i<=n;i++) scanf("%d",&a[i]); 99     makeblock();100     for(int i=1;i<=m;i++)101       {102         scanf("%d%d%d",&op,&x,&y);103         if(op==3) Update();104         else105           {106               scanf("%d",&k);107             if(op==1) Rank();108             else if(op==2) Kth();109             else if(op==4) Front();110             else Next();111           }112       }113     return 0;114 }