P8283 「MCOI-08」Dantalion 解题报告

P8283 「MCOI-08」Dantalion 解题报告：

最近好像有很多人做这道题，把这题题解发一下吧。

可能说的比较啰嗦，见谅。

题意

给定序列 \(a\)，\(q\) 次询问一个区间有多少个子区间在异或操作下封闭。

\(1\leqslant n\leqslant 6\times 10^5,1\leqslant q\leqslant 10^6\)。

分析

一个区间合法当且仅当颜色数量等于线性基张成空间大小，

首先有一个很显然的双 \(\log\) 做法是：从左到右移动合法区间的右端点，维护所有左端点到当前位置的线性基大小以及颜色数量，将颜色数量是 \(2\) 的次幂的左端点区间和线性基的左端点区间求交，最后做一遍二维数点。

优化到单 \(\log\) 有三个复杂度瓶颈：

• 维护线性基大小变化左端点位置：类似 CF1100F Ivan and Burgers 的单 \(\log\) 做法，维护前缀线性基，其中每个位只保留最靠后的位置，此时线性基内所有位置即为所求；
• 维护颜色数量是 \(2\) 的幂次的左端点区间：使用 \(\log\) 个指针表示答案，每次加入一个数字时找到其上一次出现位置，将其打上删除标记并将其后的指针暴力向后移动；
• 二维数点：对于一个线性基大小，在右端点向右移动时，左端点区间的左右端点均是单调的，将其差分可以得到很多个右端点单调的前缀加，这一问题可以线性解决。
  具体做法类似历史版本和，我们从下到上扫，维护每个位置被加入的时间，以及加入的时候对应的前缀和，以及这两个东西的前缀和，询问差分成只有上边界和右边界的 2-side 查询即可方便解决。

时间复杂度 \(O(n(\log n+\log a))\)。

代码

想要可以私信我。