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
| #include <bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int maxn = 1e6 + 10;
const int INF = 0x3f3f3f3f;
#define mid ((l+r)>>1)
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1
int n;
int trmn[maxn << 2], trmx[maxn << 2], laz[maxn << 2];
void pushup(int rt) {
trmn[rt] = min(trmn[rt << 1], trmn[rt << 1 | 1]);
trmx[rt] = max(trmx[rt << 1], trmx[rt << 1 | 1]);
}
void pushdown(int rt) {
int& x = laz[rt];
if (x) {
trmn[rt << 1] += x;
trmn[rt << 1 | 1] += x;
trmx[rt << 1] += x;
trmx[rt << 1 | 1] += x;
laz[rt << 1] += x;
laz[rt << 1 | 1] += x;
x = 0;
}
}
void update(int x, int ql, int qr, int l, int r, int rt) {
if (ql == l && qr == r) {
laz[rt] += x;
trmn[rt] += x;
trmx[rt] += x;
return;
}
pushdown(rt);
if (qr <= mid)update(x, ql, qr, lson);
else if (ql > mid)update(x, ql, qr, rson);
else {
update(x, ql, mid, lson);
update(x, mid + 1, qr, rson);
}
pushup(rt);
}
int mn, mx;
void query(int ql, int qr, int l, int r, int rt) {
if (ql <= l && qr >= r) {
mn = min(mn, trmn[rt]);
mx = max(mx, trmx[rt]);
return;
}
pushdown(rt);
if (ql <= mid)query(ql, qr, lson);
if (qr > mid)query(ql, qr, rson);
}
int a[maxn];
int main() {
scanf("%d", &n);
int pos = 1;
for (int i = 0; i < n; i++) {
char op;
scanf(" %c", &op);
if (op == 'L') {
if (pos > 1)pos--;
}
else if (op == 'R')pos++;
else {
int od = a[pos];
int nw;
if (op == '(')nw = 1;
else if (op == ')')nw = -1;
else nw = 0;
a[pos] = nw;
update(nw - od, pos, n, 1, n, 1);
}
mn = INF, mx = -INF;
query(1, n, 1, n, 1);
if (mn != 0) {
printf("-1 ");
continue;
}
int ans = mx;
mn = INF, mx = -INF;
query(n, n, 1, n, 1);
if (mn != 0) {
printf("-1 ");
continue;
}
printf("%d ", ans);
}
printf("\n");
return 0;
}
|
