花儿朵朵
时间限制：1000 ms | 内存限制：65535 KB
难度：5
- 描述
- 春天到了，花儿朵朵盛开，hrdv是一座大花园的主人，在他的花园里种着许多种鲜花，每当这个时候，就会有一大群游客来他的花园欣赏漂亮的花朵，游客们总是会询问，某个时间有多少种花儿同时在盛开着？hrdv虽然知道每种花儿的开花时间段，但是他不能很快的答出游客的问题，你能编写一个程序帮助他吗？
- 输入
- 第一行有个整数t,表示有t组测试数据，每组测试数据第一行为两个整数n,m(0<n<100000，0<m<100000);随后有n行，每一行有两个整数x,y(0<x<y<1000000000)，表示这一种花的盛开时间是从x到y；随后有m行，每行有一个整数，代表游客询问的时间。
- 输出
- 对于每次游客的询问，输出一个整数在单独的一行，表示这个时间盛开的花有多少种。
- 样例输入
2
1 1
5 10
4
2 3
1 4
4 8
1
4
6- 样例输出
0
1
2
1 解题思路：先把所给的值都离散化后再操作。然后就是插线问点了。#include<bits/stdc++.h>
using namespace std;
const int maxn=120000;
#define mid (L+R)/2
#define lson rt*2,L,mid
#define rson rt*2+1,mid+1,R
int a[maxn*2],aa[maxn*2],a_[maxn*2];
int x[maxn*2],y[maxn*2],q[maxn];
int f_num[maxn*4];
int discretization(int *tm,int l,int r,int key){
int m; //离散化
while(l<=r){
m=(l+r)/2;
if(tm[m]<key){
l=m+1;
}else if(tm[m]>key){
r=m-1;
}else{
return m;
}
}
}
void update(int rt,int L,int R,int l_ran,int r_ran){
if(l_ran<=L&&R<=r_ran){ //区间更新
f_num[rt]+=1;
return ;
}
if(l_ran<=mid){
update(lson,l_ran,r_ran);
}
if(r_ran>mid){
update(rson,l_ran,r_ran);
}
}
void PushDown(int rt){
f_num[rt*2]+=f_num[rt];
f_num[rt*2+1]+=f_num[rt];
f_num[rt]=0;
}
int query(int rt,int L,int R,int v){ //单点查询
if(L==R){
return f_num[rt];
}
if(f_num[rt]!=0)
PushDown(rt);
if(mid>=v){
return query(lson,v);
}
if(mid<v){
return query(rson,v);
}
}
int main(){
int t;
scanf("%d",&t);
while(t--){
memset(f_num,0,sizeof(f_num));
int n,m,tmp;
scanf("%d%d",&n,&m);
int num_a=n*2+m;
for(int i=0;i<num_a;i++){
scanf("%d",&tmp);
a[i]=tmp;
aa[i]=tmp;
}
sort(a,a+num_a);
int num=0;
a_[num++]=a[0];
for(int i=1;i<num_a;i++){
if(a[i]!=a[i-1]){
a_[num++]=a[i];
}
}
int num_x=0,num_y=0,num_q=0,nn=0;
for(int i=0;i<n*2;i++){
if(i%2==0){
x[num_x++]=discretization(a_,0,num-1,aa[i])+1;
if(nn<x[num_x-1]){
nn=x[num_x-1];
}
}else{
y[num_y++]=discretization(a_,0,num-1,aa[i])+1;
if(nn<y[num_y-1]){
nn=y[num_y-1];
}
}
}
for(int i=n*2;i<num_a;i++){
q[num_q++]=discretization(a_,0,num-1,aa[i])+1;
}
for(int i=0;i<n;i++){
update(1,1,nn,x[i],y[i]);
}
for(int i=0;i<num_q;i++){
int ans=query(1,1,nn,q[i]);
printf("%d\n",ans);
}
}
return 0;
}