POJ-2528 Mayor's posters 线段树+离散化 或 DFS

题目大意

有 t 组数据，每组有 n 张(1<=n<=1e4)覆盖了 区间 [li,ri] 的海报(1<=i<=n,1<=li<=ri<=1e7)，海报会由于张贴顺序先后而被覆盖

问还有多少张海报能够看得见

解析

区间问题，无脑线段树，但是仔细考虑一下，区间大小1e7，如果是平均 log 级别不会超 log1e7 大概就 20 左右

但是思考这样一个问题，一个大区间由多个海报或是空白构成，我们就要去查他的子区间，而最糟糕的情况就是，

我们可能要把 叶子结点查个遍 ，于是一次查询 最差就会 O(1e7) ，想不超时都难。

事实上，由于这个问题不会在乎你覆盖的区间多大，而只在乎覆盖的这块区间是谁的，100的长度和1的长度没啥区别

而海报数量最多1e4，我们可以把区间缩得很小，于是这就是离散化——把一段连续区间缩成一个点

离散化方法讲解

最简单的想法就是 给区间标号 [1,4] 是 1，[6,10] 是 2 这样的

但是这并不好标记 想一想做数学题你怎么标 x 轴，标几个点的坐标对吧

于是 标成 像 x[1]=1 x[2]=4 x[3]=6 x[4]=10 这样

但是 细心的你有没有发现什么问题？

4 6 之间有一个空白的 5

然而 化作 2 3 的话中间就没东西了

例如 先后 覆盖 [1,10] [1,4] [6,10] 答案应该是 3

如果 先后覆盖 离散化后的 [1,4] [1,2] [3,4] 于是[1,4]全被盖死了 答案就变成了2

所以对于空白的部分，我们也要浓缩成一个点，给他标记上去，但是你还要先去判断出空白的部分，没有意义

我们知道 反正添多大一块或缩多大一块没有影响 干脆把 端点值相差大于 1  的都额外浓缩出一个点来

这也就是说 比如 对 [1,4] 那么就是 x[1]=1, x[2-3]=2,x[4]=3，端点值与内部区间分别浓缩成值较小的一个点

下面是AC代码：

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
int t,n,le[10005],ri[10005],num[10005*4],cnt,tmp,tree[10005*16],ans;
bool vis[10005];
void push_down(int rt)
{
	if(!tree[rt]) return;
	tree[rt*2]=tree[rt*2+1]=tree[rt];
	tree[rt]=0;
}
void update(int a,int b,int id,int l,int r,int rt)
{
	if(l>b||r<a) return;
	if(a<=l&&r<=b)
	{
		tree[rt]=id;
		return;
	}
	push_down(rt);
	update(a,b,id,l,(l+r)/2,rt*2);
	update(a,b,id,(l+r)/2+1,r,rt*2+1);
}
void query(int l,int r,int rt)
{
	if(tree[rt]&&!vis[tree[rt]])
	{
		ans++;
		vis[tree[rt]]=1;
		return;
	}
	if(l==r) return;
	push_down(rt);
	query(l,(l+r)/2,rt*2);
	query((l+r)/2+1,r,rt*2+1);
}
int main()
{
	cin>>t;
	while(t--)
	{
		cnt=ans=0;
		memset(tree,0,sizeof tree);
		memset(vis,0,sizeof vis);
		cin>>n;
		for(int i=1;i<=n;i++) scanf("%d%d",&le[i],&ri[i]),num[cnt++]=le[i],num[cnt++]=ri[i];
		sort(num,num+cnt);
		tmp=cnt=unique(num,num+cnt)-num;
		for(int i=1;i<tmp;i++) if(num[i]-num[i-1]>1) num[cnt++]=num[i-1]+1;
		sort(num,num+cnt);
		for(int i=1;i<=n;i++) update(lower_bound(num,num+cnt,le[i])-num,lower_bound(num,num+cnt,ri[i])-num,i,0,cnt-1,1);
		query(0,cnt-1,1);
		cout<<ans<<endl;
	}
	return 0;
}
           

PS

接下来说一点不是那么重要的东西

首先本题由于其特殊性 lazy 没必要单独写，直接就和 tree 融为一体了

其次，是在编码时的一个小重点

update(lower_bound(num,num+cnt,le[i])-num,lower_bound(num,num+cnt,ri[i])-num,i,0,cnt-1,1);
           

我们这里用了二分去快速查找下标，事实上你也可以反着存一遍，比如用数组存一下

for(int i=0;i<cnt;i++) disc[num[i]]=i;
           

但是此时反而二分更快，博主亲测

二分 79 ms   数组反着再存一遍  110 ms 而且开1e7蛮浪费空间，虽然没炸

用map来反着存一遍，因为内部维护导致 时间 657 ms

事实上 由于 poj 不支持 ， 本来应该用 hash_map 或 unordered_map 的话就会和 开数组时间差不多了

这里说一下 map 和 unordered 差别在于 一个是 红黑树 一个是hash

如果你 像树一样 增添删除修改 用 map 显然更快 

如果你 像数组一样 随机化访问 显然是 unordered_map 更胜一筹

然后的话这个题 千万别对  map.clear 会超时的 不做不必要的 clear 也是很重要的

方法二

虽然说一般人第一眼想到的都是线段树，但下面这个方法还是很容易想到的

后来的覆盖先来的，只需要从后来的往先来的进行染色，并无法重复染色即可

思路非常简单，直接上代码了

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
int t,n,ans,le[10005],ri[10005];
bool vis[10005];
void dfs(int l,int r,int x)
{
	if(!x) return;
	cout<<l<<" "<<r<<"    "<<x<<" "<<le[x]<<" "<<ri[x]<<"   "<<ans<<endl;
	if(l<=ri[x]&&le[x]<=r)
	{
		if(!vis[x]) vis[x]=1,ans++;
		if(l<le[x]) dfs(l,le[x]-1,x-1);
		if(r>ri[x]) dfs(ri[x]+1,r,x-1);
	}                           
	else dfs(l,r,x-1);
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		ans=0;
		memset(vis,0,sizeof vis);
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d%d",&le[i],&ri[i]);
		dfs(1,10000000,n);
		printf("%d\n",ans);
	}
	return 0;
}
           

这个方法确实各个方面都优于线段树

但怎么说呢，就像两种考量方式

一种是寻找合适的数据结构进行存储后做所需操作

另一种则是直接进行算法设计得到答案

都是很不错的方法