BOJ 29162 북극여우는 괄호를 뒤집어
sorohue가 PS하는 블로그
BOJ 29162 북극여우는 괄호를 뒤집어
문제 링크입니다.
문제 요약
괄호 문자열이 주어집니다. 부분문자열의 순서를 뒤집거나 부분문자열을 구성하는 각 괄호를 반대 방향으로 바꾸는 업데이트와, 부분문자열에서 0개 이상의 괄호를 지워 얻을 수 있는 올바른 괄호 문자열의 길이를 묻는 쿼리를 처리하세요.
실제 쿼리는 괄호 쌍의 개수를 묻는데, 이는 올바른 괄호 문자열 길이의 절반과 같습니다. 풀이에서는 간단히 괄호 쌍 개수로 서술합니다.
풀이
업데이트가 없는 상황이라면 각 노드가 (여는 괄호 개수, 닫는 괄호 개수, 괄호 쌍 개수)를 저장하는 세그먼트 트리를 이용해 쿼리 당 ${\cal O}(\lg N)$의 시간 복잡도에 처리할 수 있습니다.
각 괄호를 뒤집는 업데이트 또한 느리게 갱신되는 세그먼트 트리를 이용하고, 노드에 괄호의 역할을 서로 바꿨을 때의 괄호 쌍 개수를 함께 저장하는 것으로 쿼리 당 ${\cal O}(\lg N)$에 처리할 수 있습니다.
부분문자열을 뒤집는 업데이트를 처리하기 위해 해당 기능을 내장한 스플레이 트리를 구현해 레이지 세그처럼 사용하면 모든 쿼리를 ${\cal O}(\lg N)$에 해결할 수 있습니다.
코드
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
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
struct node{
node *l, *r, *p;
int key, sub_sz;
ll o, c, sum, revsum;
bool flip, ocflip;
node(int v, node* x) : key(v), p(x){
l = r = nullptr;
o = (key == 1);
c = (key == -1);
sum = revsum = 0; sub_sz = 1; flip = ocflip = 0;
}
node(int v) : node(v, nullptr) {}
node() : node(0, nullptr) {}
};
struct SplayTree{
node* root;
node* ptr[4040404]={};
int N;
void push_flip(node* x){
if(!x->flip && !x->ocflip) return;
if(x->flip){
swap(x->l, x->r);
swap(x->o, x->c);
x->key *= -1;
}
if(x->ocflip){
swap(x->o, x->c);
swap(x->sum, x->revsum);
x->key *= -1;
}
if(x->l){
x->l->flip ^= x->flip;
x->l->ocflip ^= x->ocflip;
}
if(x->r){
x->r->flip ^= x->flip;
x->r->ocflip ^= x->ocflip;
}
x->flip = x->ocflip = 0;
}
void update(node* x){
push_flip(x);
x->sub_sz = 1;
x->o = (x->key == 1);
x->c = (x->key == -1);
x->sum = x->revsum = 0;
if(x->l){
push_flip(x->l);
x->sub_sz += x->l->sub_sz;
x->sum += x->l->sum + min(x->l->o - x->l->sum, x->c - x->sum);
x->revsum += x->l->revsum + min(x->l->c - x->l->revsum, x->o - x->revsum);
x->o += x->l->o;
x->c += x->l->c;
}
if(x->r){
push_flip(x->r);
x->sub_sz += x->r->sub_sz;
x->sum += x->r->sum + min(x->r->c - x->r->sum, x->o - x->sum);
x->revsum += x->r->revsum + min(x->r->o - x->r->revsum, x->c - x->revsum);
x->o += x->r->o;
x->c += x->r->c;
}
}
void rotate(node* x){
auto p = x->p;
node* cent = nullptr;
if(p) push_flip(p);
push_flip(x);
if(!p) return;
if(x == p->l){
p->l = cent = x->r;
x->r = p;
}
else{
p->r = cent = x->l;
x->l = p;
}
x->p = p->p;
p->p = x;
if(cent) cent->p = p;
(x->p ? p==x->p->l ? x->p->l : x->p->r : root) = x;
update(p); update(x);
}
void splay(node* x, node* g = nullptr){
while(x->p != g){
auto p = x->p;
if(p->p != g) rotate((x==p->l) == (p==p->p->l) ? p : x);
rotate(x);
}
if(!g) root = x;
}
void init(int n){
N = n; string str; cin >> str;
auto now = ptr[0] = root = new node(0);
for(int i = 1; i <= n; i++){
ptr[i] = now->r = new node((str[i-1] == '(' ? 1 : -1), now);
now = now->r;
}
ptr[n+1] = now->r = new node(0, now);
for(int i = n+1; i>=0; i--) update(ptr[i]);
splay(ptr[n>>1]);
}
void kth(int k){
node* x = root;
while(1){
push_flip(x);
while(x->l && x->l->sub_sz > k){
x = x->l;
push_flip(x);
}
if(x->l) k -= x->l->sub_sz;
if(!k--) break;
x = x->r;
}
splay(x);
}
node* gather(int s,int e){
kth(e+1);
node* tmp = root;
kth(s-1);
splay(tmp, root);
return root->r->l;
}
void flip(int s, int e){
node* x = gather(s, e);
x->flip ^= 1;
}
void ocflip(int s, int e){
node* x = gather(s, e);
x->ocflip ^= 1;
}
void qry1(int s, int e){
node* x = gather(s, e); push_flip(x);
ocflip(s, e);
}
void qry2(int s, int e){
node* x = gather(s, e); push_flip(x);
flip(s, e); ocflip(s, e);
}
void qry3(int s, int e){
node* x = gather(s, e); push_flip(x);
flip(s, e);
}
void qry4(int s, int e){
node* x = gather(s, e); push_flip(x);
cout << x->sum << '\n';
}
void print(node* x){
push_flip(x);
if(x->l) print(x->l);
if(x->key) cout << (x->key > 0 ? '(' : ')');
if(x->r) print(x->r);
if(x == root) cout << '\n';
}
} splay;
int main(){
cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
int n, Q; cin >> n >> Q; splay.init(n);
while(Q--){
int q, s, e; cin >> q >> s >> e;
if(q == 1) splay.qry1(s, e);
if(q == 2) splay.qry2(s, e);
if(q == 3) splay.qry3(s, e);
if(q == 4) splay.qry4(s, e);
//splay.print(splay.root);
}
}
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.