自动搬运

查看原文

来自洛谷，原作者为

	JiaY19 会走到属于我的完美时间线吗

搬运于2025-08-24 22:53:42，当前版本为作者最后更新于2023-12-25 17:38:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

思路

考虑扫描线。

如果此时新加了一个数。

那么以 $las_{a_i}+1\sim i$ 为左端点的区间的奇偶性都会发生变化。

使用线段树维护。

那么就是一个区间异或的操作。

至于求一个区间内的所有子区间的答案。

就是每个点的历史和。

那么问题就变成了区间异或和区间历史和。

考虑如何维护。

可以发现，这道题的正常序列只有 $1$ 和 $0$。

所以区间异或就相当于交换 $0$ 和 $1$ 的个数。

可以维护矩阵。

$$\begin{bmatrix} num_0&num_1&sum_1\\ \end{bmatrix}$$

表示 $0$ 的个数，$1$ 的个数，$1$ 的个数的历史和。

区间异或即乘上。

$$\begin{bmatrix} 0&1&0\\ 1&0&0\\ 0&0&1\\ \end{bmatrix}$$

叠加历史和即乘上。

$$\begin{bmatrix} 1&0&1\\ 0&1&0\\ 0&0&1\\ \end{bmatrix}$$

维护矩阵中的每一位，卡卡常就可以过了。

Code

AC记录。