POJ 2528 Mayor's posters 【离散化+线段树区间覆盖】

线段树区间覆盖】"/>

POJ 2528 Mayor's posters 【离散化+线段树区间覆盖】

题目链接：=2528

思路：

这里着重讲讲离散化的方式。离散化的方式是根据题目意思来选择的，不同的题目会有不同的离散化方式。

这里题目要求的是在n次区间覆盖过后，求没被覆盖的海报有多少个； 题目给出可能的区间多达 1e7 ，如果用线段树的区间覆盖就需要开 4倍的空间，因为题目给出的空间有限，直接就用线段树显然是不行的。

我们先从结果开始考虑，n次覆盖过后，最后得到的是一整个区间有若干个连续的小区间，我们要求的就是这些区间中不重复的个数，显然这些区间有多长是不影响结果的，只要知道这个区间存在就行了，比如说 1-5 有两个连续的区间1-2 和 2-5，我们把这两个区间压缩成长度为1的区间可以得到  1-2 和2-3 ，那么整个区间就只需要1-3 就足够了。这就是这道题离散化的方式。

我们假设题目给出的区间各不相交， 那么最多需要准备 2*n的区间，题目给出的n是很小的，所以这种离散方式是合理的。

红色的数字就是离散化后区间端点，原本长度为10的区间能离散成长度为7的区间，不仅不会影响答案还能节省空间；

代码的离散过程就是依次读入区间左右端点，排序过后再去重，对应数组的下标就是对应端点离散化后的区间端点；

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <cstdlib>
#include <cmath>
#include <set>using namespace std;const int Maxn = 2e4+10;int Set[4*Maxn], x, y, z, ans, v[Maxn];
bool vis[Maxn];
vector <pair <int, int> > a;void update (int o, int L, int R) {int lc = 2*o, rc = 2*o+1;if (x <= L && R <= y) {Set[o] = z;} else {if (Set[o] > 0) {Set[lc] = Set[rc] = Set[o];Set[o] = 0;}int M = L+(R-L)/2;if (x <= M) update (lc, L, M);if (M < y) update (rc, M+1, R);}
}void solve (int o, int L, int R) {int lc = 2*o, rc = 2*o+1;if (Set[o] > 0) {if (!vis[Set[o]]) {ans++; vis[Set[o]] = true;}} else {if (L == R) return;int M = L+(R-L)/2;solve (lc, L, M);solve (rc, M+1, R);}
}int main (void)
{int T;scanf ("%d", &T);while (T--) {int n, maxn = 0;scanf ("%d", &n);memset (Set, 0, sizeof (Set));a.clear();for (int i = 1; i <= n; ++i) {scanf ("%d%d", &x, &y);a.push_back(make_pair(x, y));v[maxn++] = x; v[maxn++] = y;}int m = a.size();sort (v, v+maxn);maxn = unique(v, v+maxn)-v;for (int i = 0; i < m; ++i) {x = lower_bound(v, v+maxn, a[i].first)-v+1; // 找出对应的下标y = lower_bound(v, v+maxn, a[i].second)-v+1;//   cout << x << " " << y << endl;z = i+1;update (1, 1, maxn);}ans = 0;memset (vis, false, sizeof (vis));solve (1, 1, maxn);printf ("%d\n", ans);}return 0;
}