首页 > 代码库 > poj2528-Mayor's posters-线段树离散化、基础
poj2528-Mayor's posters-线段树离散化、基础
题意：高度为1byte的n（n <= 10000）张海报贴在高度为1byte长度为10000000byte的板上。海报按顺序张贴，给出每张海报的张贴范围，求最后能够看见多少张海报（不完整的都算）。
思路：因为数组不可能开10^7那么大，而且海报的张数只有10000张，则边界值最多20000个，于是我们离散化坐标值，这里用到了sort、unique、还有lower_bound去二分查找。用sort排序，unique去重后的数组的元素个数建线段树，之后，就是线段树的区间操作、lazy标记了。线段树记录当前是第几次被张贴，最后单点查询，不同的张贴数表示能看到的海报数，这里用一个vis数组去记录。
AC代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <vector> 5 #include <cstring> 6 using namespace std; 7 #define lson l, m, rt<<1 8 #define rson m+1, r, rt<<1|1 9 #define maxn 20000 10 struct node 11 { 12 int l, r; 13 }; 14 int sgt[maxn<<2]; 15 vector<node> arr; 16 vector<int> sor; 17 int lazy[maxn<<2]; 18 bool vis[maxn]; 19 void input() 20 { 21 arr.clear(); 22 sor.clear(); 23 int n; scanf("%d", &n); 24 for(int i = 0; i < n; i++) { 25 node x; scanf("%d%d", &x.l, &x.r); 26 arr.push_back(x); 27 sor.push_back(x.l); 28 sor.push_back(x.r); 29 } 30 sort(sor.begin(), sor.end()); 31 vector<int>::iterator it; 32 it = unique(sor.begin(), sor.end()); 33 sor.resize(distance(sor.begin(), it)); 34 memset(vis, 0, sizeof(vis)); 35 memset(lazy, 0, sizeof(lazy)); 36 } 37 void push_down(int rt) 38 { 39 if(lazy[rt] != 0) { 40 lazy[rt<<1] = lazy[rt]; 41 lazy[rt<<1|1] = lazy[rt]; 42 sgt[rt<<1] = lazy[rt]; 43 sgt[rt<<1|1] = lazy[rt]; 44 lazy[rt] = 0; 45 } 46 } 47 void build(int l, int r, int rt) 48 { 49 lazy[rt] = 0; 50 if(l == r) { 51 sgt[rt] = 0; 52 return; 53 } 54 int m = (l+r)>>1; 55 build(lson); 56 build(rson); 57 } 58 void change(int l, int r, int rt, int L, int R, int del) 59 { 60 if(L <= l && r <= R) { 61 lazy[rt] = del; 62 sgt[rt] = del; 63 return; 64 } 65 push_down(rt); 66 int m = (l + r)>>1; 67 if( L <= m) change(lson, L, R, del); 68 if(m < R) change(rson, L, R, del); 69 } 70 void query(int l, int r, int rt) 71 { 72 if(l == r) { 73 vis[sgt[rt]] = 1; 74 return; 75 } 76 push_down(rt); 77 int m = (l+r)>>1; 78 query(lson); 79 query(rson); 80 } 81 void num() 82 { 83 int ans = 0; 84 int l = sor.size(); 85 for(int i = 1; i <= l; i++) { 86 if(vis[i] != 0) ans ++; 87 } 88 printf("%d\n", ans); 89 } 90 91 void work() 92 { 93 input(); 94 int n = sor.size(); 95 build(1, n, 1); 96 int len = arr.size(); 97 for(int i = 0; i < len; i++){ 98 int l = lower_bound(sor.begin(), sor.end(), arr[i].l) - sor.begin()+1; 99 int r = lower_bound(sor.begin(), sor.end(), arr[i].r) - sor.begin()+1;100 change(1, n, 1, l, r, i+1);101 }102 query(1, n, 1);103 num();104 }105 int main()106 {107 int t; scanf("%d", &t);108 while(t--) work();109 return 0;110 }
poj2528-Mayor's posters-线段树离散化、基础
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。