南阳理工OJ 600 花儿朵朵（离散化）

连接：http://acm.nyist.net/JudgeOnline/problem.php?pid=600

 

花儿朵朵

时间限制：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<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int t1,t2,t3;
int n,m;
struct noder
{
       int date;
       int type;//1是开始，2是结束，3是询问
       int num;
}node[300010];
int res[100010];
int q[100010];
bool operator < (const noder a,const noder b)
{
       if(a.date==b.date)return a.num<b.num ;
       else return a.date<b.date ;
}
int main()
{
	int T,i,a,b,k,term,j;
	scanf("%d",&T);
	while(T--)
	{
	       memset(res,0,sizeof(res));
	       scanf("%d%d",&n,&m);
	       t1=t2=t3=0;k=0;
	       for(i=1;i<=n;i++)
	       {
	              scanf("%d%d",&a,&b);
	              node[k].date=a;node[k].num=t1++; node[k++].type=1;
	              node[k].date=b;node[k].num=t2++;node[k++].type=2;
	       }
	       for(i=1;i<=m;i++)
	       {
	              scanf("%d",&a);
	              node[k].date=a;node[k].num=t3++;node[k++].type=3;
	       }
	       sort(node,node+k);
	       term=0;b=node[0].date;j=0;
	       for(i=0;i<k;i++)
	       {
	              a=node[i].date;
	              if(a>b)term++;
	              if(node[i].type==1)res[term]++;
	              else if(node[i].type==2)res[term+1]--;
	              else q[node[i].num]=term;
	              b=a;
	       }
	       for(i=1;i<=term;i++)res[i]+=res[i-1];
              for(i=0;i<m;i++)printf("%d\n",res[q[i]]);
	}
	return 0;
}