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