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

Với một dãy số ~B~ gồm ~M~ phần tử, độ đa dạng của dãy bằng số lượng dãy khác nhau có thể tạo được bằng cách thực hiện không quá một phép đảo ngược bất kỳ đoạn con nào trên dãy.

Cho một 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~:

• Thực hiện xóa bỏ phần tử thứ ~p_j~ trong dãy ~A~. Các phần tử còn lại giữ nguyên vị trí ban đầu và tạo thành các đoạn con bị ngăn cách bởi các phần tử bị xóa.
• Xác định độ đa dạng của đoạn con có độ đa dạng lớn nhất trong tất cả đoạn con của dãy ~A~.

Giới hạn và subtask

• ~1\le Q<N\le 2\times 10^5~</li>
• ~1\le A_i\le 10^9~ với mọi ~i~ từ ~1~ đến ~N~
• ~1\le p_j\le N~ với mọi ~j~ từ ~1~ đến ~Q~
• Các phần tử trong dãy ~p~ đôi một phân biệt

Subtask 1: ~Q=1;N\le 200~

Với một dãy số ~B~ độ dài ~M~, có ~\frac{M\times (M+1)}2+1~ cách thực hiện thao tác khác nhau để tạo ra các dãy (~1~ cách không đảo ngược đoạn con và ~\frac{M\times (M+1)}2~ cách đảo ngược một đoạn con).

Xét bài toán xác định độ đa dạng của đoạn con/dãy. Cách làm đơn giản nhất là tạo ra tất cả dãy và đếm số dãy khác nhau bằng cày trâu. Tuy nhiên, độ phức tạp cho cách làm này là quá lớn kể cả với subtask 1.

Thay vào đó, ta sẽ sử dụng hash để nén các dãy số thành các số nguyên không âm, cách nén y hệt so với cách nén xâu:

$$hash=\left(\sum_{i=1}^M B_i\times base^{M-i}\right)\ mod\ MOD$$

Bằng cách này, bài toán giờ chỉ là đếm số lượng phần tử khác nhau của một dãy số nguyên không âm và có thể giải trong ~O\left(M\times S+S\times log(S)\right)~ với ~S~ là số lượng dãy khác nhau có thể tạo.

Trong ba subtask đầu, vì ~Q=1~ nên ta chỉ cần tính độ đa dạng của tối đa hai đoạn con trong dãy và xác định giá trị lớn hơn.

Lưu ý: Để chắc chắn, các bạn có thể cải đặt từ ~2~ giá trị ~MOD~ khác nhau trở lên.

Độ phức tạp: ~O(N^3+N^2\times log(N))~.

Subtask 2: ~Q=1;N\le 2000~

Ta có thể cải tiến cách tính giá trị ~hash~. Ta tạo hai mảng lưu trữ các giá trị ~hash~ tiền tố của mảng ~B~ và mảng ~B~ theo thứ tự ngược lại.

Ta tính trước giá trị ~hash~ của toàn bộ dãy. Khi đảo ngược đoạn ~[L;R]~, ta dùng hai mảng vừa tạo để trừ ~hash~ của đoạn và cộng lại ~hash~ của đoạn sau khi đã đảo ngược. Vì thế nên độ phức tạp cho việc tính giá trị ~hash~ trong các trường hợp đảo ngược đoạn chỉ còn ~O(1)~, độ phức tạp cho việc tính độ đa dạng của mảng đã cải tiến xuống ~O\left(S\times log(S)\right)~.

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

Subtask 3: ~Q=1~

Ta không thể thực hiện cày trâu như hai subtask trên nữa. Liệu có cách nào để xác định độ đa dạng của dãy một cách nhanh chóng hay không?

Nhận xét: Độ đa dạng của dãy số ~B~ độ dài ~M~ bằng số cặp số ~(x,y)~ ~(1\le x<y\le M)~ sao cho ~B_x\ne B_y~ cộng ~1~.</p>

Chứng minh:

• Dãy gốc được tính là một dãy do ta có thể không thực hiện đảo ngược hoặc đảo ngược đoạn chỉ gồm ~1~ phần tử.
• Xét mọi cặp số ~(x,y)~ có ~B_x\ne B_y~, khi đảo ngược đoạn ~[x;y]~ sẽ luôn tạo ra một dãy mới.
• Tại sao? Giả sử ta chỉ quan tâm vị trí phần tử đầu tiên và phần tử cuối cùng bị thay đổi, nếu cặp vị trí mà khác nhau thì hai dãy tạo được cũng sẽ khác nhau. Rõ ràng khi đảo đoạn ~[x;y]~ thì hai vị trí đầu và cuối bị thay đổi sẽ là ~x~ và ~y~. Từ đó có thể suy ra điều vừa nói ở trên.
• Xét mọi cặp số ~(x,y)~ có ~B_x=B_y~, dễ dàng nhận thấy khi đảo ngược đoạn ~[x;y]~ hay đoạn ~[x+1;y-1]~ thì đều như nhau. Như vậy việc đảo ngược đoạn ~[x;y]~ với mọi cặp số trong trường hợp này đều không tạo ra dãy mới.

Từ những điều trên ta suy ra điều cần chứng minh. Như vậy bài toán đã đơn giản hơn rất nhiều.

Ta có thể thay đổi cách tính bằng công thức ~\frac{M\times (M-1)}2-S+1~ với ~S~ là số cặp số ~(x,y)\ (1\le x<y\le M)~ sao cho ~B_x=B_y~. Bài toán giờ trở về bài toán đếm số cặp phần tử bằng nhau cơ bản.</p>

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

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

Có ~2~ cách làm cho subtask này.

Cách 1: DSU+Small to large

Ta có thể đảo ngược cách thực hiện truy vấn. Giả sử ta có dãy sau khi thực hiện các truy vấn, mỗi bước ta thêm lại một phần tử vô dãy. Khi đó, một số đoạn con sẽ gộp lại trở thành đoạn con lớn hơn. Tới đây ta thấy bài toán có thể giải quyết bằng thuật toán DSU.

Mỗi đoạn con ta duy trì một CTDL lưu trữ số lần xuất hiện của các phần tử và số cặp phần tử bằng nhau trong đoạn con đó.

Khi gộp hai đoạn con, số cặp phần tử bằng nhau mới tạo được sẽ bằng ~\sum_{x\in S}cnta_x\times cntb_x~ (~S~ là tập các phần tử phân biệt trong đoạn con thứ nhất, ~cnta_x~ và ~cntb_x~ là số lần xuất hiện của ~x~ trong đoạn con thứ nhất và hai).

Để cải tiến, ta áp dụng kỹ thuật small to large: Thực hiện cập nhật từ tập hợp bé sang tập hợp lớn.

Cuối cùng, ta dùng một std::multiset để duy trì độ đa dạng của các đoạn con và lấy giá trị của số lớn nhất trong tập.

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

Cách 2: Mo's algorithm

Khi ta xóa một phần tử, một đoạn con của dãy sẽ bị chia làm tối đa hai đoạn con khác nhau. Điều này tương đương với việc sau mỗi truy vấn, sẽ có thêm tối đa hai đoạn con khác nhau cần phải xác định độ đa dạng. Có tối đa ~2Q+1~ đoạn con cần xét.

Tới đây thì bài toán lại đưa về dạng như sau:

Cho dãy số ~A~ gồm ~N~ phần tử và ~Q~ truy vấn, mỗi truy vấn gồm hai số nguyên dương ~L,R~. Với mỗi truy vấn, hãy đếm số cặp số ~(x,y)\ (L\le x<y\le R)~ sao cho ~A_x=A_y~.</p>

Đây là một bài toán sử dụng Mo's algorithm điển hình. Phần còn lại của bài toán chỉ là dùng một std::multiset để duy trì độ đa dạng của các đoạn con và lấy giá trị của số lớn nhất trong tập.

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