Segment Tree

#pragma GCC optimize("O3,unroll-loops") #ifdef ONLINE_JUDGE #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #endif #include <bits/stdc++.h> int N; int str[1100000]; long long sum[1100000 * 4], min[1100000 * 4], max[1100000 * 4], lazy[1100000 * 4]; void push_down(int n, int l, int r) { if (r - l > 1) { int m = l + r >> 1; sum[n << 1] += lazy[n] * (m - l), min[n << 1] += lazy[n]; max[n << 1] += lazy[n], lazy[n << 1] += lazy[n]; sum[n << 1 | 1] += lazy[n] * (r - m), min[n << 1 | 1] += lazy[n]; max[n << 1 | 1] += lazy[n], lazy[n << 1 | 1] += lazy[n]; } lazy[n] = 0; } void update(int n, int l, int r) { if (r - l > 1) { sum[n] = sum[n << 1] + sum[n << 1 | 1]; min[n] = std::min(min[n << 1], min[n << 1 | 1]); max[n] = std::max(max[n << 1], max[n << 1 | 1]); } } void add(int n, int l, int r, int ql, int qr, int d) { push_down(n, l, r); if (ql <= l && r <= qr) { sum[n] += d * (r - l); min[n] += d; max[n] += d; lazy[n] += d; return; } int m = l + r >> 1; if (ql < m) add(n << 1, l, m, ql, qr, d); if (m < qr) add(n << 1 | 1, m, r, ql, qr, d); update(n, l, r); } int query_sum(int n, int l, int r, int ql, int qr) { push_down(n, l, r); if (ql <= l && r <= qr) return sum[n]; int m = l + r >> 1; int ans = 0; if (ql < m) ans += query_sum(n << 1, l, m, ql, qr); if (m < qr) ans += query_sum(n << 1 | 1, m, r, ql, qr); return ans; } int query_min(int n, int l, int r, int ql, int qr) { push_down(n, l, r); if (ql <= l && r <= qr) return min[n]; int m = l + r >> 1; int ans = 1E9; if (ql < m) ans = std::min(ans, query_min(n << 1, l, m, ql, qr)); if (m < qr) ans = std::min(ans, query_min(n << 1 | 1, m, r, ql, qr)); return ans; } int query_max(int n, int l, int r, int ql, int qr) { push_down(n, l, r); if (ql <= l && r <= qr) return max[n]; int m = l + r >> 1; int ans = -1E9; if (ql < m) ans = std::max(ans, query_max(n << 1, l, m, ql, qr)); if (m < qr) ans = std::max(ans, query_max(n << 1 | 1, m, r, ql, qr)); return ans; } int main() { scanf("%d", &N); int cur = 0; for (int i = 0; i < N; ++i) { char c; scanf(" %c", &c); if (c == 'L') { if (cur > 0) --cur; } else if (c == 'R') { ++cur; } else { int mod = (c == '(' ? 1 : (c == ')' ? -1 : 0)) - str[cur]; str[cur] += mod; add(1, 0, N, cur, N, mod); } if (query_sum(1, 0, N, N - 1, N) != 0 || query_min(1, 0, N, 0, N) < 0) { printf("-1 "); } else { printf("%d ", query_max(1, 0, N, 0, N)); } } }