POJ2528 (Mayor's posters)[线段树，离散化]

发表于 | 更新于 | | 阅读次数：

题目链接：http://poj.org/problem?id=2528

基本思路是把坐标离散化，然后用线段树维护区间颜色即可。
颜色标记有未涂色、某一种具体单色、混合色三种，向上维护的时候需要特别判断。查询区间中颜色总数量时，只需要向下找到单色的节点，并借助一个vis数组统计颜色即可。

需要注意的是这题卡常数，离散化时不能用map，因为map常数非常大会被卡掉。可以用lower_bound来搞，也可以直接用一个数组来搞（因为数据范围只有1e7）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=10009;
const int MIX=10008;
int l[MAXN];
int r[MAXN];
int d[MAXN*2],ne=0,size;
bool vis[MAXN];
int rd[10000010];
int n;


int t=2;

struct Node {
	int col,nc;
	int lc,rc;
}v[MAXN*4];

void build(int now,int l,int r) {
	v[now].col=0;
	v[now].nc=0;
	if(l<r-1) {
		int mid=(l+r)>>1;
		v[now].lc=t;
		build(t++,l,mid);
		v[now].rc=t;
		build(t++,mid,r);
	}
	else {
		v[now].lc=v[now].rc=0;
	}
}

void update(int now,int l,int mid,int r) {
	if(v[now].nc==0) return ;
	v[v[now].lc].nc=v[now].nc;
	v[v[now].rc].nc=v[now].nc;
	v[v[now].lc].col=v[now].nc;
	v[v[now].rc].col=v[now].nc;
	v[now].nc=0;
}

void change(int now,int l,int r,int lr,int rr,int nc) {
	if(lr<=l&&r<=rr) {
		v[now].nc=nc;
		v[now].col=nc;
		return ;
	}
	int mid=(l+r)>>1;
	if(v[now].nc!=0) update(now,l,mid,r);
	if(lr<mid) change(v[now].lc,l,mid,lr,rr,nc);
	if(mid<rr) change(v[now].rc,mid,r,lr,rr,nc);
	if(v[v[now].lc].col==MIX || v[v[now].rc].col==MIX) v[now].col=MIX;
	else if(v[v[now].lc].col==v[v[now].rc].col) v[now].col=v[v[now].lc].col;
	else v[now].col=MIX;
}

int cnt=0;
void query(int now,int l,int r) {
	if(l>=r) return ;
	if(v[now].col!=MIX) {
		if(v[now].col!=0) {
			if(!vis[v[now].col]) {
				cnt++;
				vis[v[now].col]=1;
			}
		}
		return ;
	}
	int mid=(l+r)>>1;
	if(v[now].nc!=0) update(now,l,mid,r);
	query(v[now].lc,l,mid);
	query(v[now].rc,mid,r);
}

int root=1;


int main() {
	int T;
	scanf("%d",&T);
	while(T--) {
		scanf("%d",&n);
		memset(d,0,sizeof(d));
		memset(vis,0,sizeof(vis));
		ne=0;
		for(int i=1;i<=n;i++) {
			scanf("%d%d",l+i,r+i);
			d[++ne]=l[i];
			d[++ne]=r[i];
		}
		sort(d+1,d+ne+1);
		size=unique(d+1,d+ne+1)-(d+1);
		for(int i=1;i<=size;i++) {
			rd[d[i]]=i;
		}
		t=2; cnt=0;
		build(root,0,size+2);
		int ll,rr;
		for(int i=1;i<=n;i++) {
			ll=rd[l[i]];
			rr=rd[r[i]];
			change(root,0,size+2,ll,rr+1,i);
		}
		query(root,0,size+2);
		printf("%d\n",cnt);
	}
}