1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 int n,a[10001],num[10001],qx,qy,k,p,v,m,sz,sum,l[101],r[101],b[10001],tmp[1001]; 7 char s[2]; 8 void makeblock() 9 {10     memcpy(b,a,sizeof(a));11     sz=sqrt((double)n*log2(n));12     for(sum=1;sum*sz<n;sum++)13       {14         l[sum]=(sum-1)*sz+1;15         r[sum]=sum*sz;16         for(int i=l[sum];i<=r[sum];i++)17           num[i]=sum;18         sort(b+l[sum],b+r[sum]+1);19       }20     l[sum]=sz*(sum-1)+1;21     r[sum]=n;22     sort(b+l[sum],b+r[sum]+1);23     for(int i=l[sum];i<=r[sum];i++)24       num[i]=sum;25 }26 void query(int L,int R,int k)27 {28     if(num[L]+1>=num[R])29       {30         int en=0;31         for(int i=L;i<=R;i++) tmp[++en]=a[i];32         sort(tmp+1,tmp+en+1);33         printf("%d\n",tmp[k]);34       }35     else36       {37         int x=0,y=1000000001;38         while(x!=y)39           {40             int mid=x+y>>1,cnt=0;41             for(int i=L;i<=r[num[L]];i++) if(a[i]<mid) cnt++;42             for(int i=l[num[R]];i<=R;i++) if(a[i]<mid) cnt++; //统计<mid的值数43             for(int i=num[L]+1;i<num[R];i++) cnt+=( lower_bound(b+l[i],b+r[i]+1,mid) - (b+l[i]) );44             if(cnt>=k) y=mid;45             else x=mid+1;46           }47         printf("%d\n",x-1);48       }49 }50 void update(int p,int v)51 {52     *lower_bound(b+l[num[p]],b+r[num[p]]+1,a[p])=v;53     sort(b+l[num[p]],b+r[num[p]]+1);54     a[p]=v;55 }56 int main()57 {58     scanf("%d%d",&n,&m);59     for(int i=1;i<=n;i++) scanf("%d",&a[i]);60     makeblock();61     for(int i=1;i<=m;i++)62       {63         scanf("%s",s);64         if(s[0]==‘Q‘) {scanf("%d%d%d",&qx,&qy,&k);query(qx,qy,k);}65         else {scanf("%d%d",&p,&v);update(p,v);}66       }67     return 0;68 }