Editorial for Bedao Mini Contest 24 - BRACKETQUERY
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Ta biến đổi xâu dãy ngoặc ~s_1, s_2, \ldots, s_n~ thành một mảng ~a_1, a_2, \ldots, a_n~ với quy ước: '('~ = 1~, và ')'~ = -1~. Điều kiện để xâu ~s_l, s_l + 1, \ldots, s_r~ là một dãy ngoặc đúng là:
~\sum_{i = l}^{t} a_i \ge 0~, ~(l \le t \le r)~.
~\sum_{i}^{r} a_i = 0~. (Độc giả tự chứng minh).
Subtask 1 ~(n, q \le 1000)~:
Với mỗi truy vấn ta duyệt từ vị trí ~x~ kiểm tra có thõa là dãy ngoặc đúng hay không và cập nhập độ dài dài nhất trong ~O(n)~.
ĐPT: ~O(n * q)~.
Subtask 2 ~(n, q \le 10^5)~:
- Dựng cây phân đoạn với nút quản lý đoạn ~[l, r]~ lưu giá trị nhỏ nhất của ~ps_i~ ~(l \le i \le r)~. Với ~ps_i = a_1 + a_2 + \ldots + a_i~.
Với thao tác đảo dấu ngoặc ở vị trí ~x~, ta thấy rằng nó sẽ ảnh hưởng tới những vị trí từ ~x~ tới ~n~. Ta cập nhập trên đoạn các vị trí thay đổi này.
Với thao tác tìm dãy ngoặc đúng dài nhất bắt đầu từ vị trí ~x~:
- Chặt nhị phân tìm kiếm vị trí ~r~ xa nhất sao cho ~min(ps_x, ps_{x + 1}, \ldots, ps_{r}) - ps_{x - 1} \ge 0~.
- Chặt nhị phân tìm kiếm vị trí ~l~ xa nhất sao cho ~min(ps_l, ps_{l + 1}, \ldots, ps_{r}) - ps_{x - 1} \le 0~.
- Như vậy đán án bài toán là ~l - x + 1~ nếu tìm được ~l, r~ thõa mãn.
- Ta chặt nhị phân mất ~\log\ n~, và trong mỗi lần chặt ta mất ~\log\ n~ để ~min~ trên đoạn. Do đó ta mất ~\log^2\ n~ để thực hiện thao tác tìm kiếm.
ĐPT: ~O(q * \log^2\ n)~.
Subtask 3 ~(n, q \le 5 * 10^5)~:
Tương tự như subtask ~2~, tuy nhiên ở thao tác tìm dãy ngoặc đúng dài nhất ta sẽ sử dụng Walk on Segment tree nhờ đó giảm độ phức tạp xuống ~log\ n~ cho mỗi lần tìm kiếm.
ĐPT: ~O(q * log\ n)~.
/* Tag: */ #include <bits/stdc++.h> #define ll long long #define ii pair<int, int> #define st first #define nd second #define endl "\n" #define all(v) v.begin(), v.end() #define Unique(v) v.erase(unique(all(v)), v.end()) using namespace std; const int oo = 1e9; class SegmentTree{ private: int n; vector<int> seg; vector<int> pref, lazy; void build(int id, int l, int r){ if (l == r){ seg[id] = pref[l]; return; } int mid = (l + r) >> 1; build(id << 1, l, mid); build(id << 1 | 1, mid + 1, r); seg[id] = min(seg[id << 1], seg[id << 1 | 1]); } void push(int id, int l, int r){ int &t = lazy[id]; if (t == 0) return; seg[id << 1] += t; seg[id << 1 | 1] += t; lazy[id << 1] += t; lazy[id << 1 | 1] += t; t = 0; } void update(int id, int l, int r, int ls, int rs, int val){ if (ls > r || l > rs) return; if (ls <= l && r <= rs){ seg[id] += val; lazy[id] += val; return; } push(id, l, r); int mid = (l + r) >> 1; update(id << 1, l, mid, ls, rs, val); update(id << 1 | 1, mid + 1, r, ls, rs, val); seg[id] = min(seg[id << 1], seg[id << 1 | 1]); } int get(int id, int l, int r, int ls, int rs){ if (l > rs || ls > r) return oo; if (ls <= l && r <= rs) return seg[id]; int mid = (l + r) >> 1; push(id, l, r); return min(get(id << 1, l, mid, ls, rs), get(id << 1 | 1, mid + 1, r, ls, rs)); } int upper(int id, int l, int r, int ls, int rs, int upperVal){ if (seg[id] >= upperVal) return oo; if (ls > r || l > rs) return oo; if (l == r) return l; push(id, l, r); int mid = (l + r) >> 1; int res = oo; // cout << l << " " << r << " " << seg[id << 1] << " " << seg[id << 1 | 1] << endl; if (seg[id << 1] < upperVal){ res = upper(id << 1, l, mid, ls, rs, upperVal); } if (res == oo){ res = upper(id << 1 | 1, mid + 1, r, ls, rs, upperVal); } return res; } int lower(int id, int l, int r, int ls, int rs, int lowerVal){ if (ls > r || l > rs) return oo; if (seg[id] > lowerVal) return oo; if (l == r) return l; push(id, l, r); int mid = (l + r) >> 1; int res = oo; if (seg[id << 1 | 1] <= lowerVal){ res = lower(id << 1 | 1, mid + 1, r, ls, rs, lowerVal); } if (res == oo){ res = lower(id << 1, l, mid, ls, rs, lowerVal); } return res; } public: SegmentTree(int _n, vector<int> &_pref): n(_n), pref(_pref), seg(4 * _n + 10), lazy(4 * _n + 10) {} void build(){ build(1, 0, n); } void update(int l, int r, int delta){ update(1, 0, n, l, r, delta); } int get(int l, int r){ return get(1, 0, n, l, r); } int upper(int l, int r, int val){ return upper(1, 0, n, l, r, val); } int lower(int l, int r, int val){ return lower(1, 0, n, l, r, val); } }; const int MAXN = 1e6 + 5; int n, q; string s; vector<int> pref; void prep(){ pref.resize(n + 1); for (int i = 1; i <= n; i++){ pref[i] = pref[i - 1] + ((s[i] == '(') ? 1 : -1); } } void PROGRAM(int _){ cin >> n >> q >> s; s = '+' + s; prep(); SegmentTree d(n, pref); d.build(); while (q--){ int type, x; cin >> type >> x; if (type == 1){ if (s[x] == '('){ d.update(x, n, -2); s[x] = ')'; } else{ d.update(x, n, 2); s[x] = '('; } } else{ int valOfX = d.get(x - 1, x - 1); int upper = d.upper(x, n, valOfX); if (upper == oo) upper = n; else upper--; int lower = d.lower(x, upper, valOfX); if (lower == oo) cout << 0 << endl; else cout << lower - x + 1 << endl; } } } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); int test = 1; for (int _ = 1; _ <= test; _++){ PROGRAM(_); } return 0; }
Comments
Mình muốn hỏi phần độc giả tự chứng minh, giới hạn của kí tự i bên dưới kí hiệu sigma là gì ạ
~\sum^{r}_{i = l}~ nha bạn, người viết lời giải chắc đã đánh nhầm.