poj 3225 Help with Intervals

本文从WordPress迁移而来, 查看全部WordPress迁移文章

线段树

题意:给出一系列的操作,输出最后那些区间为1,(初始化为0)

U:把区间[l,r]覆盖成1

I:把[-∞,l)(r,∞]覆盖成0

D:把区间[l,r]覆盖成0

C:把[-∞,l)(r,∞]覆盖成0 , 且[l,r]区间0/1互换

S:[l,r]区间0/1互换

这题是有开闭区间的,只要将区间倍增就行了

[l,r] === [2l,2r]

(l,r) === [2l+1,2r-1]

开和闭的处理

找到的报告都说这题很难,可能之前写过了类似的,所以觉得这题也不太难,这题和uva 11402 Ahoy, Pirates!差不多是一样的,都是区间有0,1然后将一些区间变1,变0,或者区间内的0,1取反。不过这题,要比UVA那题简单,因为这题不需要记录什么,一个lazy标记就行了

lazy的含义是相同的,1为该区间全部为1,0为该区间全部为0,2为该区间进行过取反操作,-1为该区间没有进行操作,区间内掺杂了01

关于最后怎么输出答案。因为是要按顺序去输出所有为1的区间,这其实不好做的,但是最笨的一个方法就是遍历一次整个线段树,把之前记录的lazy信息传递整个树,那么每次遍历到叶子的时候,就能得到叶子最后的信息,也就是说,遍历一次整个线段树,得到整个区间最后的样子。
一开始担心会超时,后来发现不会

当然可以适当剪枝一下,遍历的时候来到[t[rt],l,t[rt],r],lazy=0,说明整个区间都是0,可以返回了不必继续深入,如果[t[rt].l,t[rt].r],lazy=1,说明整个区间都是1,也不必继续深入,可以返回,但是返回前先把这段区间内个单元都变为1

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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include <iostream>
#include <cstdio>
#include <cstring>
#include <utility>
#include <vector>
using namespace std;
#define MAX 131070
//#define MAX 20
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define lson(i) ((i)<<1)
#define rson(i) ((i)<<1|1)

struct SegTree{
int l,r,lazy;
SegTree(){}
SegTree(int _l,int _r){
l = _l; r = _r; lazy = 0;
}
int mid(){
return (l+r)>>1;
}
}t[(MAX+10)<<4];
bool val[MAX+5];
int ans[MAX+5][2],num;

void build(int rt,int a,int b){
t[rt] = SegTree(a,b);
if(a == b) return ;
int mid = t[rt].mid();
build(lson(rt),a,mid);
build(rson(rt),mid+1,b);
}

void del(int rt,int k){
if(k == 2)
t[rt].lazy = 1 - t[rt].lazy;
else
t[rt].lazy = k;
}

void PushDown(int rt){
if(t[rt].lazy == -1) return;
del(lson(rt),t[rt].lazy);
del(rson(rt),t[rt].lazy);
t[rt].lazy = -1;
}

void updata(int rt,int a,int b,int k){
if(t[rt].l == a && t[rt].r == b){
del(rt,k);
return;
}
PushDown(rt);
int mid = t[rt].mid();
if(b <= mid)
updata(lson(rt),a,b,k);
else if(a > mid)
updata(rson(rt),a,b,k);
else{
updata(lson(rt),a,mid,k);
updata(rson(rt),mid+1,b,k);
}
}

void solve(char op,int a,int b){
if(op == 'U'){
updata(1,a,b,1);
}
else if(op == 'D'){
updata(1,a,b,0);
}
else if(op == 'C'){
if(a-1 >= 0) updata(1,0,a-1,0);
if(b+1 <= MAX) updata(1,b+1,MAX,0);
updata(1,a,b,2);
}
else if(op == 'I'){
if(a-1 >= 0) updata(1,0,a-1,0);
if(b+1 <= MAX) updata(1,b+1,MAX,0);
}
else{
updata(1,a,b,2);
}
}

void input(){
char op[10],ll,rr;
int a,b;
while(scanf("%s %c%d,%d%c",op,&ll,&a,&b,&rr)!=EOF){
//printf("%s %c%d,%d%c\n",op,ll,a,b,rr);
if(ll == '(') a = 2 * a + 1;
else a = 2 * a;
if(rr == ')') b = 2 * b - 1;
else b = 2 * b;
if(a > b) continue;
solve(op[0],a,b);
}
}

void query(int rt){
if(t[rt].lazy == 0) return ;
if(t[rt].lazy == 1){
for(int i = t[rt].l; i <= t[rt].r; i++)
val[i] = true;
return ;
}
if(t[rt].l == t[rt].r){
if(t[rt].lazy == 1) val[t[rt].l] = true;
else if(t[rt].lazy == 0) val[t[rt].l] = false;
else if(t[rt].lazy == 2) val[t[rt].l] = true;
return ;
}
PushDown(rt);
query(lson(rt));
query(rson(rt));
}

int main(){
//freopen("case.txt","r",stdin);

build(1,0,MAX);
input();
cl(val,false);
query(1);

num = 0;
bool one = false;
int st = -1,en = -1;
for(int i = 0; i <= MAX; i++){
if(val[i]){
if(one) en = i;
else{ st = en = i , one = true; }
}
else{
if(one){ ans[num][0] = st; ans[num++][1] = en; one = false; }
}
}
if(one){ ans[num][0] = st; ans[num][1] = en;}

if(num == 0){
puts("empty set");
return 0;
}
for(int i = 0; i < num; i++){
int st = ans[i][0];
int en = ans[i][1];
if(st&1) printf("(%d,",st/2);
else printf("[%d,",st/2);
if(en&1) printf("%d)",(en+1)/2);
else printf("%d]",(en+1)/2);
if(i != num-1) printf(" ");
}
puts("");
return 0;
}