P9990 [Ynoi Easy Round 2023] TEST_90 题解

· · 题解

思路

考虑扫描线。

如果此时新加了一个数。

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

使用线段树维护。

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

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

就是每个点的历史和。

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

考虑如何维护。

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

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

可以维护矩阵。

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

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

区间异或即乘上。

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

叠加历史和即乘上。

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

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

Code

AC记录。