## Ý tưởng thuật toán
Ta sẽ trả lời các truy vấn offline, theo thứ tự $r$ tăng dần. Tại một $r$ nào đó, gọi $f_i$ là số
đoạn thỏa mãn với $l=i$ và đầu phải không vượt quá $r$, kết quả của một truy vấn chỉ là $f_l +
f_{l+1} + \dots + f_r$. Khi đó bài toán quy về việc duy trì dãy $f$ một cách hiệu quả.
Khi chuyển từ $r-1$ sang $r$, $f_i$ chỉ tăng lên $1$ nếu số phần tử phân biệt trong $[i,r]$ là lẻ.
Việc duy trì số phần tử phân biệt trong đoạn dễ hơn. Gọi $d_i$ là số phần tử phân biệt trong $[i,r]$,
$p[x]$ là vị trí gần nhất của $x$, thì ta có phép cập nhật: $d_j := d_j + 1$ với mọi $j \in
\left[ p[a_r]+1, r \right]$. Do ta chỉ quan tâm tính chẵn lẻ của $d_i$ nên ta duy trì nó là một dãy bit,
phép tăng đoạn tương đương với việc flip dãy bit liên tiếp.
## Cấu trúc dữ liệu
Thế khung thuật toán hiện tại của ta nhìn như sau. Duyệt $r$ từ $1$ đến $n$:
+ flip đoạn $\left[ p[a_r]+1, r \right]$ trên $d$;
+ cập nhật $p[a_r] := r$;
+ với mọi $i$ mà bit $d_i$ bật, gán $f_i := f_i + 1$;
+ trả lời các truy vấn với $r$ này.
Việc này có thể giải quyết hiệu quả bằng một lazy segment tree. Do thao tác tăng $f$ nên trước mắt,
mỗi đỉnh của cây ta cần lưu $s$ là tổng $f$ của đoạn, và $c$ là số bit bật trên $d$ trong đoạn. Về phép lazy, ngoài
việc lưu một biến $\texttt{flip}$ kiểu $\texttt{bool}$ để cho biết đoạn có bị flip không, ta cần biết tổng lượng tăng
phân biệt với các $d_i=0$ và $d_i=1$, gọi lần lượt là $\texttt{add0}$ và $\texttt{add1}$. Để đẩy tag
lazy thì ta đẩy biến $\texttt{flip}$ trước rồi mới đến $\texttt{add0}$ và $\texttt{add1}$.
Tổng độ phức tạp thời gian của thuật toán là $\mathcal{O}\left( (n+q) \log n \right)$.
Note: Nếu chỉ lưu tổng lượng tăng với $d_i=1$, ta sẽ bị trường hợp như thế này: một đỉnh được tăng biến
lazy, sau đó, đỉnh đó được flip. Khi biến tăng lazy được đẩy xuống, ban đầu nó phải tăng các $d_i=1$
lên, nhưng sau khi flip, các vị trí đó biến thành $0$ nên việc cập nhật tổng sẽ bị sai.
tuongll
Created at
1 likes