Bài Toán

DQUERY

Tài liệu

VNOI - Persistent Segment Tree

Thuật toán

QUORA

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";
   }
}