1 //Accepted    14796 KB    453 ms  2 //划分树  3 //把查询的次数m打成n，也是醉了一晚上！！！  4 //二分l--r区间第k大的数和h比较  5 #include <cstdio>  6 #include <cstring>  7 #include <iostream>  8 #include <queue>  9 #include <cmath> 10 #include <algorithm> 11 using namespace std; 12 /** 13   * This is a documentation comment block 14   * 如果有一天你坚持不下去了，就想想你为什么走到这儿！ 15   * @authr songt 16   */ 17 const int imax_n = 100005; 18 struct node 19 { 20     int val[imax_n]; 21     int num[imax_n]; 22 }f[20]; 23 int a[imax_n]; 24 int sorted[imax_n]; 25 int n,m; 26 void build(int t,int l,int r) 27 { 28     if (l==r) return ; 29     int mid=(l+r)/2; 30     int isame=mid-l+1; 31     int same=0; 32     for (int i=l;i<=r;i++) 33     if (f[t].val[i]<sorted[mid]) isame--; 34     int ln=l; 35     int rn=mid+1; 36     for (int i=l;i<=r;i++) 37     { 38         if (i==l) 39         { 40             f[t].num[i]=0; 41         } 42         else f[t].num[i]=f[t].num[i-1]; 43  44         if (f[t].val[i]<sorted[mid]) 45         { 46             f[t].num[i]++; 47             f[t+1].val[ln++]=f[t].val[i]; 48         } 49         else if (f[t].val[i]>sorted[mid]) 50         { 51             f[t+1].val[rn++]=f[t].val[i]; 52         } 53         else 54         { 55             if (isame>same) 56             { 57                 same++; 58                 f[t].num[i]++; 59                 f[t+1].val[ln++]=f[t].val[i]; 60             } 61             else 62             { 63                 f[t+1].val[rn++]=f[t].val[i]; 64             } 65         } 66     } 67     build(t+1,l,mid); 68     build(t+1,mid+1,r); 69 } 70 int query(int t,int l,int r,int a,int b,int k) 71 { 72     if (l==r) return f[t].val[l]; 73     int mid=(l+r)/2; 74     int s,ss; 75     if (a==l) 76     { 77         ss=0; 78         s=f[t].num[b]; 79     } 80     else 81     { 82         ss=f[t].num[a-1]; 83         s=f[t].num[b]-ss; 84     } 85  86     if (s>=k) 87     { 88         a=l+ss; 89         b=l+ss+s-1; 90         return query(t+1,l,mid,a,b,k); 91     } 92     else 93     { 94         int b1=a-l-ss; 95         int b2=b-a+1-s; 96         a=mid+1+b1; 97         b=mid+b1+b2; 98         return query(t+1,mid+1,r,a,b,k-s); 99     }100 }101 int x,y,h;102 void slove()103 {104     build(0,1,n);105     for (int i=1;i<=m;i++)106     {107         scanf("%d%d%d",&x,&y,&h);108         x++;109         y++;110         int l=1,r=y-x+1;111         int mid=(l+r)/2;112         int ans=0;113         while (l<=r)114         {115             mid=(l+r)/2;116             int t=query(0,1,n,x,y,mid);117             //printf("pre :l=%d r=%d mid=%d t=%d\n",l,r,mid,t);118             if (t>h) r=mid-1;119             else120             {121                 ans=mid;122                 l=mid+1;123             }124             //printf("l=%d r=%d t=%d\n",l,r,t);125         }126         printf("%d\n",ans);127     }128 }129 int main()130 {131     int T;132     int t=0;133     scanf("%d",&T);134     while (T--)135     {136         scanf("%d%d",&n,&m);137         for (int i=1;i<=n;i++)138         {139             scanf("%d",&a[i]);140             f[0].val[i]=sorted[i]=a[i];141         }142         sort(sorted+1,sorted+n+1);143         printf("Case %d:\n",++t);144         slove();145     }146     return 0;147 }