题意求区间内比h小的数的个数
将所有的询问离线读入之后，按H从小到大排序。然后对于所有的结点也按从小到大排序，然后根据查询的H，将比H小的点加入到线段树，然后就是一个区间和.
2015-07-27：专题训练到此
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root 1,n,1
#define mid ((l+r)>>1)
#define ll long long
#define cl(a) memset(a,0,sizeof(a))
#define ts printf("*****\n");
using namespace std;
const int MAXN=+;
int sum[MAXN<<],lsum[MAXN<<],rsum[MAXN<<];
int n,m,tt;
struct Node
{
int L,R,H;
int id;
void in(int w)
{
scanf("%d%d%d",&L,&R,&H);
L++,R++;
id=w;
}
}node[MAXN];
struct No
{
int val;
int id;
void in(int w)
{
scanf("%d",&val);
id=w;
}
}no[MAXN];
bool cmp1(Node a,Node b)
{
return a.H<b.H;
}
bool cmp2(No a,No b)
{
return a.val<b.val;
}
int pushup(int rt)
{
sum[rt]=sum[rt<<]+sum[rt<<|];
}
void update(int pos,int l,int r,int rt)
{
if(l==r)
{
sum[rt]=;
return;
}
if(pos<=mid) update(pos,lson);
else update(pos,rson);
pushup(rt);
}
int query(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
return sum[rt];
}
int ans=;
if(L<=mid) ans+=query(L,R,lson);
if(R>mid) ans+=query(L,R,rson);
return ans;
}
int a[MAXN];
int main()
{
int i,j,k;
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
scanf("%d",&tt);
int ca=;
while(tt--)
{
scanf("%d%d",&n,&m);
cl(sum);
for(i=;i<=n;i++)
{
no[i].in(i);
}
sort(no+,no+n+,cmp2);
for(i=;i<=m;i++)
{
node[i].in(i);
}
sort(node+,node+m+,cmp1);
int tot=;
for(i=;i<=m;i++)
{
while(node[i].H>=no[tot].val)
{
update(no[tot].id,root);
tot++;
}
a[node[i].id]=query(node[i].L,node[i].R,root);
}
printf("Case %d:\n",ca++);
for(i=;i<=m;i++)
{
printf("%d\n",a[i]);
}
}
}
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root 1,n,1
#define mid ((l+r)>>1)
#define ll long long
#define cl(a) memset(a,0,sizeof(a))
#define ts printf("*****\n");
using namespace std;
const int MAXN=;
int sum[MAXN<<],o[MAXN];
int n,m,t;
struct Node
{
int L,R,H;
int id;
void in(int i)
{
scanf("%d%d%d",&L,&R,&H);
L++,R++;
id=i;
}
}node[MAXN];
struct Num
{
int val,id;
void in(int i)
{
scanf("%d",&val);
id=i;
}
}num[MAXN];
bool cmp1(Num a,Num b)
{
return a.val<b.val;
}
bool cmp2(Node a,Node b)
{
return a.H<b.H;
}
void pushup(int rt)
{
sum[rt]=sum[rt<<]+sum[rt<<|];
}
void build(int l,int r,int rt)
{
sum[rt]=;
if(l==r) return;
build(lson);
build(rson);
}
void update(int pos,int l,int r,int rt)
{
if(l==r)
{
sum[rt]=;
return;
}
if(pos<=mid) update(pos,lson);
if(pos>mid) update(pos,rson);
pushup(rt);
}
int query(int L,int R,int l,int r,int rt)
{
if(L<=l&&R>=r)
{
return sum[rt];
}
int ans=;
if(L<=mid) ans+=query(L,R,lson);
if(R>mid) ans+=query(L,R,rson);
return ans;
}
int main()
{
int i,j,k,q,tt;
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
scanf("%d",&tt);
int ca=;
while(tt--)
{
scanf("%d%d",&n,&m);
build(root);
for(i=;i<=n;i++)
{
num[i].in(i);
}
for(i=;i<m;i++)
{
node[i].in(i);
}
sort(num+,num+n+,cmp1);
sort(node,node+m,cmp2);
i=,j=;
while(i<m)
{
while(j<=n)
{
if(node[i].H<num[j].val) break;
update(num[j].id,root);
j++;
}
while(i<m)
{
if(j<=n&&node[i].H>=num[j].val) break;
o[node[i].id]=query(node[i].L,node[i].R,root);
i++;
}
}
printf("Case %d:\n",ca++);
for(i=;i<m;i++)
{
printf("%d\n",o[i]);
}
}
return ;
}