POJ 2528 Mayor's posters（线段树区间修改+离散化）
最后更新于：2022-04-01 15:53:20
题目链接：[点击打开链接](http://poj.org/problem?id=2528)
题意：在墙上贴海报,海报可以互相覆盖,问最后可以看见几张海报。
该题是线段树区间修改+离散化的应用。
不难想到， 每次对一个最长10^7的线段进行线段树的区间修改， 最后统计。
线段树的复杂度是log10^7， 应该不会超时， 但是会超内存。 所以想到要离散化， 将区间端点值有映射成一个尽量小的值。
但是该题求的是覆盖情况， 如果按照单纯的点对点的离散化， 那样会出现错误答案。
例如： 依次贴[1,10], [1,3], [5,10] ， 离散化后1->1, 3->2, 5->3, 10->4
那么第一次让离散后的区间[1,4]变成1，第二次让[1,2]变成2，第三次让[3,4]变成3，那么最终答案成了2， 其实是3。
问题之所在就在于：小的区间不会覆盖大区间的所有部分。 解决方法就是在相邻区间端点大于1时再添加一个二者中间的数当作“空白”区域。
不会离散化的先学学离散化吧， 一般用二分来维护比较简单。
细节参见代码：
~~~
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
const int maxn = 11111;
int T,n,ans,setv[maxn<<4],X[maxn<<3];
bool vis[maxn];
struct node {
int l, r;
node(int ll=0, int rr=0):l(ll), r(rr) {}
bool operator < (const node& rhs) const {
return l < rhs.l || (l == rhs.l && r < rhs.r);
}
}a[maxn];
void pushdown(int o) {
if(setv[o]) {
setv[o<<1] = setv[o<<1|1] = setv[o];
setv[o] = 0;
}
}
void update(int L, int R, int v, int l, int r, int o) {
int m = (l + r) >> 1;
if(L <= l && r <= R) {
setv[o] = v; return ;
}
pushdown(o);
if(L <= m) update(L, R, v, l, m, o<<1);
if(m < R) update(L, R, v, m+1, r, o<<1|1);
}
void query(int l, int r, int o) {
int m = (l + r) >> 1;
if(setv[o]) {
if(!vis[setv[o]]) {
vis[setv[o]] = true;
++ans;
}
return ;
}
if(l == r) return ;
query(l, m, o<<1);
query(m+1, r, o<<1|1);
}
int main() {
scanf("%d",&T);
while(T--) {
scanf("%d",&n);
int cnt = 0;
for(int i=1;i<=n;i++) {
scanf("%d%d",&a[i].l,&a[i].r);
X[cnt++] = a[i].l; X[cnt++] = a[i].r;
}
sort(X, X+cnt);
cnt = unique(X, X+cnt) - X;
int m = cnt;
for(int i=1;i<cnt;i++) {
if(X[i] > X[i-1]+1) X[m++] = X[i] + 1;
}
sort(X, X + m);
memset(vis, false, (n+1)*sizeof(vis[0]));
memset(setv, 0, sizeof(setv));
for(int i=1;i<=n;i++) {
int lc = lower_bound(X, X + m, a[i].l) - X + 1;
int rc = lower_bound(X, X + m, a[i].r) - X + 1;
update(lc, rc, i, 1, m, 1);
}
ans = 0;
query(1, m, 1);
printf("%d\n",ans);
}
return 0;
}
~~~