hdu 4417 2012杭州ネット試合

n個の数,m個の問合せを与え,各問合せ出力[l,r]区間においてhより大きい数を与えると,nとmが大きいため,直接肯定することはできず,線分ツリーで解くことができる.
セグメントツリーの各区間は、その区間の長さと同じように対応するデータセグメントを保存してソートし、クエリーの際にその区間が問い合わせたい区間に含まれている場合は、直接2分で上界を調べます.そうしないと、下に問い合わせ続けます.

#include<iostream>
#include<algorithm>
using namespace std;

#define lson u<<1
#define rson u<<1|1
#define MAXN 100010

int dat[MAXN];

struct Node{
	int lef,rig;
	//int sum;
	int *sub;

}T[MAXN<<2];

void Build(int u,int l,int r){
	T[u].lef=l;
	T[u].rig=r;
	T[u].sub=new int[r-l+3];
	int subc=0;
	for(int i=l;i<=r;i++)T[u].sub[subc++]=dat[i];
	sort(T[u].sub,T[u].sub+subc);
	if(l==r)return;
	int mid=(l+r)>>1;
	Build(lson,l,mid);
	Build(rson,mid+1,r);
}

void finalizer(int u,int l,int r){
	delete[] T[u].sub;
	if(l==r)return;
	int mid=(l+r)>>1;
	finalizer(lson,l,mid);
	finalizer(rson,mid+1,r);
}

int Query(int u,int l,int r,int h){
	if(l<=T[u].lef&&T[u].rig<=r){
		int cnt=upper_bound(T[u].sub,T[u].sub+r-l+1,h)-T[u].sub;
		return cnt;
	}
	else{
		if(r<=T[lson].rig)return Query(lson,l,r,h);
		if(l>=T[rson].lef)return Query(rson,l,r,h);
		else return Query(lson,l,T[lson].rig,h)+Query(rson,T[rson].lef,r,h);
	}
}

int main(){
	int t,n,q;
	scanf("%d",&t);
	for(int cas=1;cas<=t;cas++){

		scanf("%d%d",&n,&q);
		for(int i=1;i<=n;i++)scanf("%d",dat+i);

		printf("Case %d:
",cas);
		Build(1,1,n);
		int lf,rg,hg;
		while(q--){
			scanf("%d%d%d",&lf,&rg,&hg);
			printf("%d
",Query(1,lf+1,rg+1,hg));
		}
		finalizer(1,1,n);
	}
}