首页 > 代码库 > hihoCoder #1079 离散化
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
5 104 100 21 65 93 4
- Sample Output
5
解题：线段树。。。离散化
View Code1 #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 long14 #define pii pair<int,int>15 #define INF 0x3f3f3f3f16 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\n",s.size());76 }77 return 0;78 }
hihoCoder #1079 离散化
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。