【POJ】2528 Mayor‘s posters 题解

题解"/>

【POJ】2528 Mayor‘s posters 题解

题目大意

在只考虑长度的情况下，先后放置 n n n个海报，每个海报的范围是 [ l , r ] [l,r] [l,r]会覆盖下面的海报，问最后能看到几个海报。

题目链接

思路

我们可以用一个数组来表示整个区间，每次放新的海报(第 i i i张)，就把对应区间的数字改为 i i i。

而这种区间修改我们可以直接用线段树来做~~(珂朵莉树也可以)~~

而由于区间范围比较大，我们要离散化区间。

另外需要注意的是,由于是区间覆盖问题，所以普通离散化会出问题，比如:
[ 1 , 6 ] , [ 1 , 3 ] , [ 5 , 6 ] [1,6],[1,3],[5,6] [1,6],[1,3],[5,6]离散化后会变为 [ 1 , 4 ] , [ 1 , 2 ] , [ 3 , 4 ] [1,4],[1,2],[3,4] [1,4],[1,2],[3,4],这样一来，原来第一个区间就会被完全覆盖。

这是因为，离散化操作让不相邻的点变得相邻了，这在普通问题中没有什么影响，但是在区间覆盖问题上就变得很关键了。
所以我们要在离散化数组中，插入 r [ i ] + 1 r[i]+1 r[i]+1,防止后续点不相邻的点在离散化后和它相邻( l [ i ] , r [ i ] l[i],r[i] l[i],r[i]是否相邻没有什么影响)

线段树中的tag就相当于懒标记，它意思就是表示这个区间的数被修改了为同一个数，那么查询的时候，就不用下放了，因为我们是统计有多少个海报。

代码

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;const int maxN = 1e5 + 7;struct Tree {int l, r, color, tag;
}t[maxN << 4];int T, n, l[maxN], r[maxN], vis[maxN], ans;vector<int> pos;inline int getPos(int x)
{return lower_bound(pos.begin(), pos.end(), x) - pos.begin(); 
}void build(int l, int r, int num)
{t[num].l = l; t[num].r = r;t[num].color = 0;t[num].tag = -1;if(l == r)return ;int mid = (l + r) >> 1;build(l, mid, num << 1);build(mid + 1, r, num << 1 | 1);
}void spread(int num)
{if(t[num].tag != 0) {t[num << 1].color = t[num].color;t[num << 1 | 1].color = t[num].color;t[num << 1].tag = t[num << 1 | 1].tag = 1;t[num].tag = 0;}
}void change(int l, int r, int num, int x)
{if(l <= t[num].l && r >= t[num].r) {t[num].color = x;t[num].tag = 1;    return ;}spread(num);int mid = (t[num].l + t[num].r) >> 1;if(l <= mid)change(l, r, num << 1, x);if(r > mid)change(l, r, num << 1 | 1, x);
}void query(int l, int r, int num)
{if(t[num].tag == -1)return ;if(t[num].tag != 0) {if(!vis[t[num].color] && t[num].color != 0) {++ans;vis[t[num].color] = 1;}return ;}int mid = (l + r) >> 1;query(l, r, num << 1); query(l, r, num << 1 | 1);
}int main()
{scanf("%d", &T);while(T--) {scanf("%d", &n);ans = 0;memset(vis, 0, sizeof vis);pos.clear(); pos.push_back(0);for(int i = 1; i <= n; ++i) {scanf("%d%d", &l[i], &r[i]);pos.push_back(l[i]);pos.push_back(r[i]);pos.push_back(r[i] + 1);}sort(pos.begin(), pos.end());pos.erase(unique(pos.begin(), pos.end()), pos.end());int len = pos.size() , cnt = 0;build(1, len, 1);for(int i = 1; i <= n; ++i) {l[i] = getPos(l[i]); r[i] = getPos(r[i]);change(l[i], r[i], 1, ++cnt);}query(1, len, 1);printf("%d\n", ans);}return 0;
}