DQUERY - Online Solution
đã đăng vào 22, Tháng 8, 2022, 17:36Bài Toán
Tài liệu
VNOI - Persistent Segment Tree
Thuật toán
Xét một mảng ~a~ gồm ~7~ phần tử như sau:
~1, 2, 3, 2, 1, 3, 4~
Và một mảng ~prev~, với ~prev[i] = j~ biểu thị cho vị trí ~j~ gần nhất về phía bên trái đối với ~i~ mà ~a[i] = a[j]~ (Nếu ~a[i]~ xuất hiện lần đầu tiên, ~prev[i] = 0~)
Mảng ~prev~ của ~a~ sẽ có giá trị như sau:
~0, 0, 0, 2, 1, 3, 0~
Định nghĩa mảng ~F~ của bài toán
Xây dựng ~N~ phiên bản của một mảng ~F~. Ở phiên bản thứ ~k~, sẽ gồm ~k~ phần tử đầu tiên đã được xây dựng và có ý nghĩa như sau:
- ~F[i] = 0~, thể hiện rằng mảng a TỒN TẠI một vị trí ~j~ ~(i < j <= k)~ mà ~a[j] = a[i]~
- ~F[i] = 1~, thể hiện đây là vị trí ~j~ ~(j = i <= k)~ xa nhất và ~<= k~ về phía bên phải mảng ~a~ mà ~a[i]~ xuất hiện
- ~F[i] = {rỗng}~, thể hiện vị trí ~i~ chưa được xây dựng ở phiên bản hiện tại ~(i > k)~
mảng ~F~ xây dựng ở các phiên bản có thể hình dung như sau:
| a[] 1 2 3 2 1 3 4
| prev[] 0 0 0 2 1 3 0
----------|----------------------------------------------
Phiên bản |
1. | 1
2. | 1, 1
3. | 1, 1, 1
4. | 1, 0, 1, 1
5. | 0, 0, 1, 1, 1
6. | 0, 0, 0, 1, 1, 1
7. | 0, 0, 0, 1, 1, 1, 1
Để xây dựng được mảng ~F~ ở một phiên bản ~k~:
- ~+1~ vị trí ~k~ ở mảng ~F~ lên
- ~-1~ vị trí ~prev[k]~ ở mảng ~F~ xuống (Nếu ~prev[k] = 0~ thì không cần trừ)
Tính đúng đắn
Dưới góc nhìn trực quan
Thuật toán có đảm bảo mảng ~F~ hoạt động theo đúng định nghĩa ?
Ta thấy rằng mỗi lần cập nhật một vị trí ~k~ trong mảng ~F~ lên ~+1~ đơn vị, ta lại ~-1~ đi vị trí ~prev[k]~ đi một đơn vị (là vị trí GẦN NHẤT và phía BÊN TRÁI đối với ~a[k]~ mà ~a[prev[k]] = a[k]~)
-> Mảng ~F~ hoạt động theo đúng định nghĩa
Ý tưởng của cách làm này, đó là ta sẽ dồn sự xuất hiện của một số ~a[i]~ về phía bên phải nhất của mảng ~F~, đảm bảo ~a[i]~ chỉ được tính duy nhất ~1~ lần
Số phần tử khác nhau trong đoạn ~[L, R]~ là tổng mảng ~F~ ở phiên bản ~R~, đoạn ~[L, R]~
Ta thấy được ý nghĩa của mảng ~F~ ở phiên bản ~R~ trong khoảng ~[L, R]~ như sau:
- Mỗi số ~1~ xuất hiện trong mảng ~F~, sẽ đại diện cho ~1~ lần duy nhất phần tử ở vị trí đó được tính đúng ~1~ lần.
- Mỗi số ~0~ trong mảng, thể hiện rằng tồn tại một phần tử khác trong khoảng ~[L, R]~ cũng đã xuất hiện trong mảng rồi, nên không cần tính nữa
-> Điều phải chứng minh
Dưới góc nhìn quy nạp
Mình không chắc nên chứng minh như thế nào :Đ
Code - Persistent Segment Tree
#include <bits/stdc++.h> #define up(i,a,b) for (int i = (int)a; i <= (int)b; i++) #define ep emplace_back using namespace std; const int maxn = 2e5 + 10; const int LOG = log2(maxn)+2; struct Node{ int l = 0, r = 0; int sum = 0; }; Node T[maxn*LOG]; int n,q; int cnt = 0; int ROOT[maxn]; int a[maxn]; void build(int& nod, int l, int r){ nod = ++cnt; if (l == r){ T[nod].sum = 0; return; } int mid = (l+r) >> 1; build(T[nod].l, l, mid); build(T[nod].r, mid+1, r); } void push_up(int nod){ T[nod].sum = T[T[nod].l].sum + T[T[nod].r].sum; } void update(int& nod, int prev_nod, int l, int r, int pos, int val){ nod = ++cnt; T[nod] = T[prev_nod]; if (l == r){ T[nod].sum += val; return; } int mid = (l+r) >> 1; if (pos <= mid) update(T[nod].l, T[prev_nod].l, l, mid, pos, val); else update(T[nod].r, T[prev_nod].r, mid+1, r, pos, val); push_up(nod); } int query(int nod, int l, int r, int u, int v){ if (l > v || r < u) return 0; if (l >= u && r <= v) return T[nod].sum; int mid = (l+r) >> 1; int L = query(T[nod].l, l, mid, u, v); int R = query(T[nod].r, mid+1, r, u, v); return L+R; } int pre[1000001]; signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n; up(i,1,n) cin >> a[i]; build(ROOT[0], 1, n); up(i,1,n){ if (pre[a[i]]){ update(ROOT[i], ROOT[i-1], 1, n, pre[a[i]], -1); update(ROOT[i], ROOT[i], 1, n, i, 1); } else update(ROOT[i], ROOT[i-1], 1, n, i, 1); pre[a[i]] = i; } cin >> q; while (q--){ int l, r; cin >> l >> r; cout << query(ROOT[r], 1, n, l, r) << "\n"; } }