题意：
输入cas
n m
输入n个数
输入m组 每组表示一个范围内l r 中小于num的数的个数
注意从l是0开始的
思路 :区间内找数 很容易联想到划分树 划分树是用来求一个区间内的第k大的数
那么我们可以找出第1第2第3……大数的值 和num进行比较
用二分法很容易找到第几大的数小于且等于num
下面的几乎就是个模板 二分法居然也搞了我一下 坑爹
[cpp]
#include<stdio.h>
#include<algorithm>
using namespace std;
#define M 100005
int tree[40][M],sorted[M];
int toLeft[40][M];
void build（int level,int left,int right）{
if（left==right）return ;
int mid=（left+right）》1;
int i;
int suppose;//假设在中位数sorted[mid]左边的数都全部小于sorted[mid]
suppose=mid-left+1;
for（i=left;i<=right;i++）{
if（tree[level][i]<sorted[mid]）{
suppose--;
}
}
//如果suppose==1,则说明数组中值为sorted[mid]只有一个数。比如序列：1 3 4 5 6,sorted[mid]=4
/*如果suppose>1,则说明数组中左半边值为sorted[mid]的不止一个数，为mid-suppose.比如序列：1 4 4 4 6,sorted[mid]=4
*/
int lpos=left,rpos=mid+1;
for（i=left;i<=right;i++）{
if（i==left）
{//这里是预处理，相当与初始化
toLeft[level][i]=0;
}
else
{
toLeft[level][i]=toLeft[level][i-1];
}
if（tree[level][i]<sorted[mid]）{//划分到中位数左边
toLeft[level][i]++;
tree[level+1][lpos++]=tree[level][i];
}else if（tree[level][i]>sorted[mid]）{//划分到中位数右边
tree[level+1][rpos++]=tree[level][i];
}else{//这里，suppose大于0的数划分到中位数的左边
if（suppose!=0）{//这里的处理太巧妙了！帅气！
suppose--;
toLeft[level][i]++;
tree[level+1][lpos++]=tree[level][i];
}else{//表示
tree[level+1][rpos++]=tree[level][i];
}
}
}
build（level+1,left,mid）；
build（level+1,mid+1,right）；
}
//在[left,right]数据中查询[qleft,qright]中第k大的数据
int query（int level,int left,int right,int qleft,int qright,int k）{
if（ qleft==qright）
return tree[level][qleft];
int s;//代表[left,qleft）之间有多个个元素被分到左边
int ss;//[qleft, qright]内将被划分到左子树的元素数目
int mid=（left+right）》1;
if（left==qleft）{
s=0;
ss=toLeft[level][qright];
}else{
s=toLeft[level][qleft-1];
ss=toLeft[level][qright]-s;
}
int newl,newr;
if（k<=ss）{//查询左边
newl=left+s;
newr=left+s+ss-1;
return query（level+1,left,mid,newl,newr,k）；
}else{//查询右边
newl=mid-left+1+qleft-s;
newr=mid-left+1+qright-s-ss;
return query（level+1,mid+1,right,newl, newr,k - ss）；
}
}
int main（）
{
int n,m,cas,ca=0;
scanf（"%d",&cas）；
while（cas--）
{
printf（"Case %d:\n",++ca）；
scanf（"%d %d",&n,&m）；
int i;
for（i=1;i<=n;i++）{
scanf（"%d",&tree[0][i]）；
sorted[i]=tree[0][i];
}
sort（sorted+1,sorted+n+1）；
build（0,1,n）；
int ql,qr,num,ans=0;
for（i=0;i<m;i++）
{
scanf（"%d %d %d",&ql,&qr,&num）；
ql++;qr++;//注意这里哦 题意是按从0开始的
int mid,left=1,right=qr-ql+1,ans=0;
mid=（left+right）/2;
while（left<=right）//别少了等于号
{
mid=（left+right）/2;
if（query（0,1,n,ql,qr,mid）>num） right=mid-1;
else {ans=mid;left=mid+1;}//我一开始写的二分法居然不知道是哪里出错了一个劲RE
}
printf（"%d\n",ans）；
}
} return 0;
}