hihoCoder #1079 离散化

P1 : 离散化

Time Limit:10000ms

Case Time Limit:1000ms

Memory Limit:256MB

描述

小Hi和小Ho在回国之后，重新过起了朝7晚5的学生生活，当然了，他们还是在一直学习着各种算法~

这天小Hi和小Ho所在的学校举办社团文化节，各大社团都在宣传栏上贴起了海报，但是贴来贴去，有些海报就会被其他社团的海报所遮挡住。看到这个场景，小Hi便产生了这样的一个疑问——最后到底能有几张海报还能被看见呢？

于是小Ho肩负起了解决这个问题的责任：因为宣传栏和海报的高度都是一样的，所以宣传栏可以被视作长度为L的一段区间，且有N张海报按照顺序依次贴在了宣传栏上，其中第i张海报贴住的范围可以用一段区间[a_i, b_i]表示，其中a_i, b_i均为属于[0, L]的整数，而一张海报能被看到当且仅当存在长度大于0的一部分没有被后来贴的海报所遮挡住。那么问题就来了：究竟有几张海报能被看到呢？

提示一：正确的认识信息量

提示二：小Hi大讲堂之线段树的节点意义

输入

每个测试点（输入文件）有且仅有一组测试数据。

每组测试数据的第1行为两个整数N和L，分别表示总共贴上的海报数量和宣传栏的宽度。

每组测试数据的第2-N+1行，按照贴上去的先后顺序，每行描述一张海报，其中第i+1行为两个整数a_i, b_i，表示第i张海报所贴的区间为[a_i, b_i]。

对于100%的数据，满足N<=10^5，L<=10^9，0<=a_i<b_i<=L。

输出

对于每组测试数据，输出一个整数Ans，表示总共有多少张海报能被看到。

Sample Input

Sample Output

5

解题：线段树。。。离散化

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <climits>
 7 #include <vector>
 8 #include <queue>
 9 #include <cstdlib>
10 #include <string>
11 #include <set>
12 #include <stack>
13 #define LL long long
14 #define pii pair<int,int>
15 #define INF 0x3f3f3f3f
16 using namespace std;
17 const int maxn = 100100;
18 struct node{
19     int lt,rt,cover;
20 };
21 node tree[maxn<<2];
22 void build(int lt,int rt,int v){
23     tree[v].lt = lt;
24     tree[v].rt = rt;
25     tree[v].cover = 0;
26     if(lt + 1 == rt) return;
27     int mid = (lt + rt)>>1;
28     build(lt,mid,v<<1);
29     build(mid,rt,v<<1|1);
30 }
31 void update(int lt,int rt,int p,int v){
32     if(tree[v].lt >= lt && tree[v].rt <= rt){
33         tree[v].cover = p;
34         return;
35     }
36     if(tree[v].cover){
37         tree[v<<1].cover = tree[v<<1|1].cover = tree[v].cover;
38         tree[v].cover = 0;
39     }
40     if(lt < tree[v<<1].rt) update(lt,rt,p,v<<1);
41     if(rt > tree[v<<1|1].lt) update(lt,rt,p,v<<1|1);
42 }
43 set<int>s;
44 void query(int v){
45     if(tree[v].cover){
46         s.insert(tree[v].cover);
47         return;
48     }
49     if(tree[v].lt + 1 == tree[v].rt) return;
50     query(v<<1);
51     query(v<<1|1);
52 }
53 int lisan[maxn<<2],n,L,x[maxn],y[maxn],tot,cnt;
54 int main() {
55     while(~scanf("%d %d",&n,&L)){
56         tot = cnt = 0;
57         for(int i = 1; i <= n; ++i){
58             scanf("%d %d",x+i,y+i);
59             lisan[tot++] = x[i];
60             lisan[tot++] = y[i];
61         }
62         sort(lisan,lisan+tot);
63         for(int i = 1; i < tot; ++i)
64             if(lisan[cnt] != lisan[i])
65                 lisan[++cnt] = lisan[i];
66         build(0,cnt,1);
67         s.clear();
68         for(int i = 1; i <= n; ++i){
69             int a = lower_bound(lisan,lisan+cnt+1,x[i])-lisan;
70             int b = lower_bound(lisan,lisan+cnt+1,y[i])-lisan;
71             if(a == b) continue;
72             update(a,b,i,1);
73         }
74         query(1);
75         printf("%d
",s.size());
76     }
77     return 0;
78 }

View Code