Posts Tagged ‘线段树’

POJ 3225 Help with Intervals（区间）

Posted in PKU OJ on 四月 30th, 2010 by 纳米 – Be the first to comment

友情提示：这道题有简体中文的，可以在Language那里选择。

2010-04-27，阅读题目
2010-04-28，分析
2010-04-29，Coding，WA，Debug，WA，Debug，WA，Debug
2010-04-30，Debug，AC

解题报告：
1. 关于区间端点的问题，把点和开区间都抽象成一个点即可。例如：[0,0]->1、(0,1)->2、[1,1]->3、(1,2)->4、[2,2]->5……
2. 5种操作其实都可以利用覆盖和翻转实现，具体见代码main部分。
3. 插入量很大，查询量很小，线段树解决。覆盖问题很容易，关于翻转，我是这样做的：如果当前节点的颜色是确定的，那么直接改变；如果是不确定的，做标记，下次递归进里面的点的时候子结点，方法同上。但是效率不很好，用了2297ms。

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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

#include <stdio.h>
 
const int n = 131072, maxn = 262144;
int pos[maxn][2], color[maxn] = {0};
bool ct[maxn] = {0};
 
void build_tree(int t, int l, int r) {
	pos[t][0] = l;
	pos[t][1] = r;
	if (l < r) {
		build_tree(t << 1, l, (l + r) >> 1);
		build_tree((t << 1) + 1, ((l + r) >> 1) + 1, r);
	}
}
 
void change(int t) {
	ct[t] = !ct[t];
	if (ct[t] && color[t] < 2) {
		color[t] = 1 - color[t];
		ct[t] = 0;
	}
}
 
void update_node(int t, int &wl, int &wr, int &wm, int &sl, int &sr) {
	wl = pos[t][0], wr = pos[t][1];
	wm = (wl + wr) >> 1;
	sl = wl < wr ? t << 1 : 0;
	sr = sl ? sl + 1 : 0;
	if (ct[t]) {
		ct[t] = 0;
		change(sl), change(sr);
	}
	if (sl && color[t] < 2) {
		color[sl] = color[sr] = color[t];
		ct[sl] = ct[sr] = 0;
	}
}
 
void cover(int t, int l, int r, int key) {
	int wl, wr, wm, sl, sr;
	update_node(t, wl, wr, wm, sl, sr);
	if (l == wl && r == wr) {
		color[t] = key;
		ct[t] = 0;
	} else {
		if (l <= wm)
			cover(sl, l, r < wm ? r : wm, key);
		++wm;
		if (r >= wm)
			cover(sr, l > wm ? l : wm, r, key);
		color[t] = color[sl] == color[sr] ? color[sl] : 2;
	}
}
 
void turn(int t, int l, int r) {
	int wl, wr, wm, sl, sr;
	update_node(t, wl, wr, wm, sl, sr);
	if (l == wl && r == wr) {
		change(t);
	} else {
		if (l <= wm)
			turn(sl, l, r < wm ? r : wm);
		++wm;
		if (r >= wm)
			turn(sr, l > wm ? l : wm, r);
		color[t] = color[sl] == color[sr] ? color[sl] : 2;
	}
}
 
void update_tree(int t) {
	int wl, wr, wm, sl, sr;
	update_node(t, wl, wr, wm, sl, sr);
	if (wl < wr) {
		update_tree(sl);
		update_tree(sr);
	}
}
 
int main() {
	build_tree(1, 1, n);
	while (1) {
		char t = 0, p0 = 0, p1 = 0;
		int c0, c1, rt = 1;
		while (rt != EOF && t != 'U' && t != 'I' && t != 'D' && t != 'C' && t != 'S')
			rt = scanf("%c", &t);
		if (rt == EOF)
			break;
		scanf("%*c%c%d%*c%d%c", &p0, &c0, &c1, &p1);
		c0 = p0 == '[' ? (c0 << 1) + 1 : (c0 << 1) + 2;
		c1 = p1 == ']' ? (c1 << 1) + 1 : c1 << 1;
		if (c0 > c1)
			c0 = 2, c1 = 1;
		if (t == 'U') {
			if (c0 <= c1)
				cover(1, c0, c1, 1);
		} else if (t == 'I') {
			if (1 < c0)
				cover(1, 1, c0 - 1, 0);
			if (c1 < n)
				cover(1, c1 + 1, n, 0);
		} else if (t == 'D') {
			if (c0 <= c1)
				cover(1, c0, c1, 0);
		} else if (t == 'C') {
			if (1 < c0)
				cover(1, 1, c0 - 1, 0);
			if (c1 < n)
				cover(1, c1 + 1, n, 0);
			if (c0 <= c1)
				turn(1, c0, c1);
		} else if (t == 'S') {
			if (c0 <= c1)
				turn(1, c0, c1);
		}
	}
	update_tree(1);
	int space = 0, l, r;
	for (int i = n; i < maxn; ++i)
		if (color[i]) {
			if (i == n || !color[i - 1])
				l = i - n + 1;
			r = i - n + 1;
		} else if (i > n && color[i - 1]) {
			if (space)
				printf(" ");
			space = 1;
			if (l & 1)
				printf("[%d,", (l - 1) >> 1);
			else
				printf("(%d,", (l - 1) >> 1);
			if (r & 1)
				printf("%d]", r >> 1);
			else
				printf("%d)", r >> 1);
		}
	if (space)
		printf("\n");
	else
		printf("empty set\n");
	return 0;
}