思路：将点按值从小到大排序，询问按h从小到大排序。
在建立线段树，按h的大小更新树并得到该次查询的结果！
代码如下：
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#define MAX 100005
#define I(x) scanf("%d",&x)
#define lson step<<1
#define rson step<<1|1
using namespace std;
int ans[MAX];
struct node
{
int x,y,h,id;
bool operator<(const node a)const{
return h<a.h;
}
}q[MAX];
struct point
{
int v,id;
bool operator<(const point a)const{
return v<a.v;
}
}p[MAX];
struct tree
{
int l,r,cnt;
}T[MAX<<];
void built(int step,int l,int r)
{
T[step].l=l;
T[step].r=r;
T[step].cnt=;
if(l==r) return ;
int m=(l+r)>>;
built(lson,l,m);
built(rson,m+,r);
}
void update(int step,int pos)
{
T[step].cnt++;
if(T[step].l==T[step].r) return;
int m=(T[step].l+T[step].r)>>;
if(pos<=m) update(lson,pos);
else update(rson,pos);
}
int query(int step,int l,int r)
{
if(T[step].l==l&&T[step].r==r) return T[step].cnt;
int m=(T[step].l+T[step].r)>>;
if(r<=m) return query(lson,l,r);
else if(l>m) return query(rson,l,r);
else return query(lson,l,m)+query(rson,m+,r);
}
int main()
{
int t,i,j,m,n,k,ca=;
I(t);
while(t--){
scanf("%d%d",&n,&m);
for(i=;i<n;i++){
I(p[i].v);
p[i].id=i+;
}
for(i=;i<m;i++){
scanf("%d%d%d",&q[i].x,&q[i].y,&q[i].h);
q[i].id=i;
}
built(,,n);
sort(p,p+n);
sort(q,q+m);
j=;
for(i=;i<m;i++){
while(j<n&&p[j].v<=q[i].h){
update(,p[j].id);
j++;
}
ans[q[i].id]=query(,q[i].x+,q[i].y+);
}
printf("Case %d:\n",++ca);
for(i=;i<m;i++)
printf("%d\n",ans[i]);
}
return ;
}
这个是划分树做的。
#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<queue>
#define inf 1<<28
#define M 6000005
#define N 100005
#define maxn 300005
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define pb(a) push_back(a)
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
#define MOD 1000000007
#define lson step<<1
#define rson step<<1|1
using namespace std;
struct Node{
int left,right;
int sum;
}L[N*];
int sa[N],num[][N],cnt[][N];//sa中是排序后的，num记录每一层的排序结果，cnt[deep][i]表示第deep层，前i个数中有多少个进入左子树
void Bulid(int step,int l,int r,int deep){
L[step].left=l;
L[step].right=r;
if(l==r)
return;
int mid=(l+r)>>;
int mid_val=sa[mid],lsum=mid-l+;;
for(int i=l;i<=r;i++)
if(num[deep][i]<mid_val)
lsum--; //lsum表示左子树中还需要多少个中值
int L=l,R=mid+;
for(int i=l;i<=r;i++){
if(i==l)
cnt[deep][i]=;
else
cnt[deep][i]=cnt[deep][i-];
if(num[deep][i]<mid_val||(num[deep][i]==mid_val&&lsum>)){ //左子树
num[deep+][L++]=num[deep][i];
cnt[deep][i]++;
if(num[deep][i]==mid_val)
lsum--;
}
else
num[deep+][R++]=num[deep][i];
}
Bulid(*step,l,mid,deep+);
Bulid(*step+,mid+,r,deep+);
}
int Query(int step,int l,int r,int k,int deep){
if(l==r)
return num[deep][l];
int s1,s2; //s1为[L[step].left,l-1]中分到左子树的个数
if(L[step].left==l)
s1=;
else
s1=cnt[deep][l-];
s2=cnt[deep][r]-s1; //s2为[l,r]中分到左子树的个数
int m=(L[step].left+L[step].right)/;
if(k<=s2) //左子树的数量大于k,递归左子树
return Query(lson,L[step].left+s1,L[step].left+s1+s2-,k,deep+);
int b1=l--L[step].left+-s1; //b1为[L[step].left,l-1]中分到右子树的个数
int b2=r-l+-s2; //b2为[l,r]中分到右子树的个数
return Query(rson,m++b1,m++b1+b2-,k-s2,deep+);
}
int slove(int l,int r,int h){
int ans=,low=,high=r-l+,mid;
while(low<=high){
mid=(low+high)/;
int tmp=Query(,l,r,mid,);
if(tmp<=h){ans=mid;low=mid+;}
else high=mid-;
}
return ans;
}
int main(){
int n,q,t,cas=;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&q);
for(int i=;i<=n;i++){
scanf("%d",&sa[i]);
num[][i]=sa[i];
}
sort(sa+,sa++n);
Bulid(,,n,);
printf("Case %d:\n",++cas);
while(q--){
int l,r,h;
scanf("%d%d%d",&l,&r,&h);
l++;r++;
printf("%d\n",slove(l,r,h));
}
}
return ;
}