区间k大，分块大法好，每个区间内存储一个有序表。
二分答案，统计在区间内小于二分到的答案的值的个数，在每个整块内二分、零散的暴力即可。
还是说∵有二分操作，∴每个块的大小定为sqrt(n*log2(n))比较快呢。
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 ",tmp[k]); 34 } 35 else 36 { 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 ",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 }