nyoj_600_花儿朵朵

nyoj_600_花儿朵朵_201404162000

花儿朵朵

时间限制：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行，每行有一个整数，代表游客询问的时间。

输出

对于每次游客的询问，输出一个整数在单独的一行，表示这个时间盛开的花有多少种。

样例输入

样例输出

上传者

TC_胡仁东

 1 //本题的关键是离散化，不然数组的空间不能开那么大，接下来运用树状数组来存储，查找，问题便可迎刃而解
 2 
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <algorithm>
 6 using namespace std;
 7 const int MAX = 300010;
 8 //测试数据有点水，将 MAX 改为100010 也能过 
 9 typedef struct Node 
10 {
11     int num;
12     int id; //id为记录输入的顺序，是建立一一映射的关键
13 }Node;
14 Node s[MAX];
15 int a[MAX],c[MAX];
16 
17 int cmp(const void *a,const void *b)
18 {
19     return (*(Node *)a).num - (*(Node *)b).num;
20 }
21 
22 int lowbit(int i)
23 {
24     return i&(-i);
25 }
26 
27 void add(int i,int value)
28 {
29     while(i<MAX)
30     {
31         c[i]+=value;
32         i+=lowbit(i);
33     }
34 }
35 
36 int sum(int i)
37 {
38     int t=0;
39     while(i>0)
40     {
41         t+=c[i];
42         i-=lowbit(i);
43     }
44     return t;
45 }
46 
47 int main()
48 {
49     int T;
50     scanf("%d",&T);
51     while(T--)
52     {
53         int i,j,n,m,total,count;
54         memset(c,0,sizeof(c));
55         scanf("%d%d",&n,&m);
56         total=n*2+m;// 把所有要输入的数据综合到一块，然后建立一一映射的关系（把大数变成小数，以缩小存储空间）
57         for(i=0;i<total;i++)
58         {
59             scanf("%d",&s[i].num);
60             s[i].id=i;
61         }
62         qsort(s,total,sizeof(s[0]),cmp);
63         count = 1;a[s[0].id]=count;
64         for(i=1;i<total;i++)//大数变小，建立成映射关系
65         {
66             if(s[i].num!=s[i-1].num)
67             a[s[i].id]=++count;
68             else
69             a[s[i].id]=count;
70         }
71         for(i=0;i<n*2;i+=2)//更新树状数组结点信息（插线取点法）
72         {
73             add(a[i],1);
74             add(a[i+1]+1,-1);
75         }
76         for(i=n*2;i<total;i++)
77         printf("%d
",sum(a[i]));
78     }
79     return 0;
80 }
81 //a树状数组 + 离散化

树状数组 + 离散化