Solutions of Balanced subarray

Select solution language

chithanhnguyen Created at 0 likes

Gọi $\texttt{pref}$ là mảng cộng dồn của dãy bit ban đầu, một đoạn con $[l, r]$ là đoạn đẹp nếu số bit $1$ bằng một nửa độ dài đoạn, hay: $$ \texttt{pref}[r] - \texttt{pref}[l - 1] = \frac{r - l + 1}{2}\\ \Leftrightarrow 2\times \texttt{pref}[r] - r = 2\times \texttt{pref}[l - 1] - (l - 1) $$ Gán giá trị cho các $i = 0\ldots n$ là $\texttt{val}[i] = 2 \times \texttt{pref}[i] - i$, mỗi truy vấn $[l, r]$ quy về đến số cặp có nhãn $\texttt{val}$ bằng nhau trong đoạn $[l -1, r]$. Đây là một bài toán cơ bản sử dụng Mo Algorithm. Để tránh việc mất $\log n$ chi phí nếu sử dụng $\texttt{std::map}$ để quản lý tần suất, bạn đọc có thể: - Sử dụng $\texttt{std::unordered_map}$ kèm custom hashing để tránh hash collision - Hoặc rời rạc hóa dữ liệu của mảng $\texttt{val}$ sau đó quản lý tần suất bằng một mảng đánh dấu.