题意：有n个数。m个询问（l，r，k），问在区间[l,r] 有多少个数小于等于k。
划分树——查找区间第k大的数。。。。
利用划分树的性质。二分查找在区间[l,r]小于等于k的个数。
假设在区间第 i 大的数tmp>k,则往下找，假设tmp<k,往上找。
#include<cstdio>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<map>
#include<cmath>
#include<iostream>
#include <queue>
#include <stack>
#include<algorithm>
#include<set>
using namespace std;
#define INF 1e8
#define eps 1e-8
#define LL long long
#define N 100010
#define mod 1000000007
int a[N],s[N],t[20][N],num[20][N],n,m;
void build(int c,int l,int r)
{
if(l==r) return;
int mid=(l+r)/2;
int lm=mid-l+1,lp=l,rp=mid+1;
for(int i=l;i<=r;i++)
lm-=s[i]<s[mid];
for(int i=l;i<=r;i++)
{
if(i==l)
num[c][i]=0;
else num[c][i]=num[c][i-1];
if(t[c][i]==s[mid])
{
if(lm)
{
lm--;
num[c][i]++;
t[c+1][lp++]=t[c][i];
}
else t[c+1][rp++]=t[c][i];
}
else if(t[c][i]<s[mid])
{
num[c][i]++;
t[c+1][lp++]=t[c][i];
}
else t[c+1][rp++]=t[c][i];
}
build(c+1,l,mid);
build(c+1,mid+1,r);
}
int query(int c,int l,int r,int ql,int qr,int k)
{
if(l==r)
return t[c][l];
int s,ss,mid=(l+r)/2;
if(ql==l)
s=0,ss=num[c][qr];
else s=num[c][ql-1],ss=num[c][qr]-num[c][ql-1];
if(k<=ss)
return query(c+1,l,mid,l+s,s+l+ss-1,k);
else return query(c+1,mid+1,r,mid+1+ql-l-s,mid+1+qr-l-s-ss,k-ss);
}
int main()
{
int T,ca=1;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
s[i]=t[0][i]=a[i];
}
sort(s+1,s+n+1);
build(0,1,n);
printf("Case %d:
",ca++);
while(m--)
{
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
l++;r++;
if(query(0,1,n,l,r,r-l+1)<=k)
printf("%d
",r-l+1);
else if(query(0,1,n,l,r,1)>k)
puts("0");
else
{
int ll=0,rr=r-l+1,mid;
while(ll<=rr)
{
mid=(ll+rr)>>1;
int tmp=query(0,1,n,l,r,mid);//假设在区间[l,r]第mid大的数大于k，rr=mid-1
if(tmp>k)
rr=mid-1;
else ll=mid+1;//否则ll=mid+1
}
printf("%d
",ll-1);
}
}
}
return 0;
}
/*
1
10 10
0 5 2 7 5 4 3 8 7 7
2 8 6
3 5 0
1 3 1
1 9 4
0 1 0
3 5 5
5 5 1
4 6 3
1 5 7
5 7 3
*/