Lời giải đầy đủ tại đây. Slides chữa bài của VNOI tại đây.

Tóm tắt đề bài

Cho dãy số ~A~ gồm ~N~ phần tử. Bạn cần phải giải quyết ~Q~ truy vấn, với truy vấn thứ ~j~:

• Gồm hai số nguyên dương ~U_j~ và ~V_j~, yêu cầu đếm số cặp số ~(L,R)~ sao cho:
  • ~U_j\le L\le R\le V_j~.
  • Không tồn tại hai giá trị ~p,q~ sao cho ~p\in [L;R],q\notin [L;R], A_p=A_q~.

Giới hạn và subtask

• ~1\le N,Q\le 3\times 10^5~
• ~1\le A_i\le 10^9~ với mọi ~i~ từ ~1~ đến ~N~
• ~1\le U_j\le V_j\le N~ với mọi ~j~ từ ~1~ đến ~Q~

Subtask 1: ~N,Q\le 50~

Subtask này đơn giản chỉ là làm theo yêu cầu của đề bài.

Mỗi truy vấn ta xét hết các cặp số ~(L,R)~ và kiểm tra xem cặp số đang xét có thỏa mãn điều kiện đề bài hay không trong ~O(N^2)~.

Độ phức tạp: ~O(Q\times N^4)~ (lưu ý hằng số rất bé).

Subtask 2: ~N\le 500~

Xét một phần tử ~A_x\ (L\le x\le R)~, để thỏa mãn điều kiện đề bài thì các phần tử còn lại có giá trị ~A_x~ đều phải nằm trong đoạn ~[L;R]~. Nếu gọi ~first_v~ và ~last_v~ là vị trí của phần tử đầu tiên và cuối cùng có giá trị bằng ~v\ (v\in A)~ thì ~L\le first_v\le last_v\le R~.

Ta dựng mảng ~first~ và ~last~ trước. Để kiểm tra đoạn ~[L;R]~, ta xét hết các phần tử ~A_x\ (L\le x\le R)~ và kiểm tra như trên trong ~O(N)~.

Để giải quyết truy vấn nhanh, có 2 cách làm:

• Cách 1 (prefix sum 2D): Lưu trước kết quả của đoạn ~[L;R]\ (1\le L\le R\le N)~ vào ~pref_{L,R}~ (~0/1~ nếu không/có thỏa mãn) và dựng mảng prefix sum 2D. Khi lấy kết quả, ta chỉ cần lấy tổng các phần tử trên vùng hình chữ nhật xuất phát từ hàng ~U_j~ đến ~V_j~ và từ cột ~U_j~ đến ~V_j~ trong ~O(1)~.
• Cách 2 (quy hoạch động): Gọi ~dp_{l,r}~ là đáp án bài toán cho trường hợp ~U_j=l,V_j=r~; hàm ~check(l,r)=0/1~ tương ứng với đoạn ~[L;R]~ không/có thỏa mãn. Khi đó ta có công thức:

$$dp_{l,r}=dp_{l+1,r}+dp_{l,r-1}-dp_{l+1,r-1}+check(l,r)$$

Độ phức tạp: ~O(N^3+Q)~.

Subtask 3: ~N\le 5000~

Ta có thể viết lại điều kiện kiểm tra đoạn ~[L;R]~ thành việc kiểm tra hai điều kiện như sau:

$$min(first_{A_L},first_{A_{L+1}},\dots,first_{A_R})\ge L$$

$$max(last_{A_L},last_{A_{L+1}},\dots,last_{A_R})\le R$$

Như vậy, việc kiểm tra có thể thực hiện bằng cách duy trì hai biến ~min\_first~ và ~max\_last~ và cập nhật chúng khi chuyển từ xét đoạn ~[L;R]~ sang đoạn ~[L;R+1]~, từ đó việc kiểm tra đoạn độ phức tạp chỉ còn ~O(1)~ mỗi đoạn.

Độ phức tạp: ~O(N^2+Q)~.

Subtask 4: ~Q=1;U_j=1;V_j=N~

Ta coi một đoạn ~[x;y]~ tương ứng điểm ~(x,y)~ trên mặt phẳng tọa độ. Bây giờ, ta sẽ thực hiện cấm một số điểm, tương đương với việc đoạn con đó không thỏa mãn.

Ta sẽ xây dựng các vùng cấm có dạng hình chữ nhật.

Đầu tiên, ta sẽ cấm các điểm có tọa độ ~(x,y)~ mà ~x > y~ do đây không phải đoạn con. Ta tạo ra ~N~ vùng cấm.

Sau đó, ta duyệt qua từng phần tử ~A_i~. Lúc này:

• Nếu đoạn ~[x;y]~ chứa phần tử ~A_i~ thì đoạn cũng phải chứa vị trí ~first_{A_i}~ và ~last_{A_i}~. Như vậy ta tạo ra hai vùng cấm:
  • Vùng cấm có dạng ~x\in[first_{A_i}+1;i],y\in [i,N]~: Cấm các đoạn chứa ~i~ nhưng không chứa ~first_{A_i}~.
  • Vùng cấm có dạng ~x\in[1;i],y\in [i,last_{A_i}-1]~: Cấm các đoạn chứa ~i~ nhưng không chứa ~last_{A_i}~.

Sau khi đã xây được các vùng cấm, ta sẽ cần đếm số điểm trên mặt phẳng mà không bị vùng nào cấm. Ta có thể giải bằng thuật toán Sweep Line, tương tự bài AREA.

Độ phức tạp: ~O\left(N\times log(N)\right)~.

Subtask 5+6: Không có ràng buộc gì thêm

Cách 1: Xor hash+Mo's algorithm

Ta sẽ thay đổi cách tiếp cận của bài toán: Với mọi giá trị ~v~ xuất hiện trong dãy ~A~, gọi ~p_1,p_2,\dots,p_k~ là các vị trí trong dãy có ~A_{p_i}=v~, ta gán cho mỗi vị trí một giá trị ngẫu nhiên ~value_{p_i}~ sao cho:

$$value_{p_1}\oplus value_{p_2}\oplus \dots\oplus value_{p_k}=0$$

Như vậy ta có thể xác định tính thỏa mãn của đoạn ~[L;R]~ bằng điều kiện sau:

$$value_L\oplus value_{L+1}\oplus \dots\oplus value_R=0$$

Áp dụng tính chất của phép toán XOR, nếu gọi ~pref_i=pref_{i-1} \oplus value_i~ thì điều kiện có thể viết lại thành ~pref_R\oplus pref_{L-1}=0~, hay ~pref_R=pref_{L-1}~.

Tới đây thì bài toán lại đưa về dạng đếm số cặp phần tử ~(L,R)\ (U-1\le L<R\le V)~ sao cho ~pref_L=pref_R~. Đây là một bài toán đếm số cặp phần tử bằng nhau kinh điển có thể giải quyết bằng thuật toán Mo's algorithm.</p>

Độ phức tạp: ~O\left((N+Q)\times \sqrt N\right)~.

Cách 2: Sweep line+Walk on Segment Tree+Mo's algorithm

Nhận xét: Nếu đoạn ~[a;b]~ và đoạn ~[b+1;c]~ đều thỏa mãn thì đoạn ~[a;c]~ cũng thỏa mãn.

Ta có ý tưởng giải quyết bài toán như sau:

• Với mọi giá trị ~i\ (1\le i\le N)~, ta tìm giá trị ~nex_i~ nhỏ nhất sao cho đoạn ~[i;nex_i]~ thỏa mãn điều kiện của đề bài.
• Khai thác từ nhận xét ở trên, ta chia các đoạn ~[i;nex_i];[nex_i+1;nex_{nex_i+1}];\dots~ làm một nhóm. Khi đó nếu truy vấn ~(U,V)~ có ~k~ đoạn trong nhóm này hoàn toàn trong đoạn ~[U;V]~ thì đáp án sẽ tăng lên ~\frac{k\times (k+1)}2~.

Ta áp dụng Sweep Line như đã mô tả ở subtask 4 và sử dụng Walk on Segment Tree để tìm ra các giá trị ~nex_i~. Khi đã tìm được các giá trị trên, ta cũng có thể áp dụng Mo's algorithm để giải quyết phần còn lại của bài toán.

Độ phức tạp: ~O\left((N+Q)\times \sqrt N+N\times log(N)\right)~.

Cách 3: Sweep line+Lazy Segment Tree

Nhắc lại các vùng cấm ở subtask 4:

1. Vùng cấm có dạng ~x\in[1;i],y\in [i,last_{A_i}-1]~:

Giữ ~y~ cố định, tất cả các vùng cấm dạng này sẽ cấm một đoạn prefix theo trục ~x~, vì luôn bắt đầu từ ~x=1~.

Ta gọi ~C_y = max(i)~ mà ~i\le y<last_{A_i}~. Lúc này, đoạn ~[x; y]~ muốn thỏa mãn phải có ~x > C_y~.</p>

2. Vùng cấm có dạng ~x\in[first_{A_i}+1;i],y\in [i,N]~:

Tương tự, đặt ~R_x = min (i)~ mà ~first_{A_i} < x \le i~, nếu không có thì ~R_x = n + 1~.

Như vậy, đoạn ~[x; y]~ muốn thỏa mãn phải có ~y<R_x~.</p>

Ta đã chuyển được về hai điều kiện 1D khá đơn giản. Để đoạn ~[x; y]~ thỏa mãn thì ~x \le y, x > C_y, y < R_x~.

Ta có thể dựng mảng ~C~ và mảng ~R~ bằng cách sweepline kết hợp với std::priority_queue khá đơn giản.

Khi này, ta cần trả lời câu hỏi: cho ~u,v~, đếm số cặp ~(x, y)~ thỏa mãn ~1 \le x \le u~, ~x \le y \le v~, và ~(x, y)~ thỏa mãn điều kiện trên. Ta sẽ trả lời các câu hỏi này offline.

Nếu gọi ~f(u,v)~ là đáp án bài toán trên với ~u,v~ tương ứng thì đáp án cho truy vấn ~[U_j;V_j]~ sẽ bằng ~f(V_j,V_j)-f(U_j-1,V_j)~.

Nhắc lại điều kiện:

• ~y < R_x \rightarrow~ với mỗi ~x~, chỉ xét ~y \in [x; R_x-1]~.
• ~x > C_y \rightarrow~ với mỗi ~y~, nó chỉ được phép từ thời điểm ~x = C_y + 1~ trở đi.

Ta thấy:

• Mỗi ~y~ có thời điểm kích hoạt: $$ act_y = C_y + 1 $$
• Khi sweep tới ~x~, ta activate tất cả ~y~ có ~act_y = x~.
• Sau đó ta muốn thêm 1 điểm ~(x,y)~ cho mọi ~y~ đã active trong đoạn: $$ y \in [x;R_x-1] $$
• Đồng thời ta cần truy vấn nhanh: $$ f(x,b) = \sum_{y=1}^{b} cnt_y $$ trong đó ~cnt_y~ là số ~x' \le x~ sao cho ~(x',y)~ hợp lệ

Như vậy, ta có thể dùng segment tree lưu:

• ~cntActive~ trong node (bao nhiêu ~y~ đã active)
• ~sum~ = tổng ~cnt_y~ của các ~y~ active trong node
• range add ~+1~ chỉ cộng lên các ~y~ active ~\rightarrow~ ~sum:= sum + 1 \times cntActive~. Ta cần lưu thêm một biến ~cntAdd~ lưu số lần range add chưa đẩy xuống các con, khi đẩy xuống thì ta tăng ~sum~ của các con lên ~cntActive_{child}\times cntAdd~.

Lưu ý thứ tự sweepline, ta có thể làm như sau:

1. Activate tất cả ~y~ trong bucket ~act[x]~.
2. ~U = R_x-1~. Nếu ~U \ge x~: ~rangeAdd([x; U], +1)~.
3. Trả lời các event tại thời điểm ~x~: ~querySum([1; b])~.

Độ phức tạp: ~O\left((N+Q)\times log(N)\right)~.