Luogu5280 [ZJOI2019] 线段树

题意：维护线段树集合 。初始时， 中只有一颗 的线段树。

支持下列操作：

• 将每棵线段树复制两份，其中一份执行区间覆盖。

• 查询目前所有线段树中，有标记的节点个数。

，时限 。

---

显然不能真的维护多颗线段树。

思考区间操作对标记的影响，将点分为如下五类：

• 白色：部分被操作区间包含的点，其中的标记一定会被清空。

• 深灰色：操作区间拆分出的点，一定会得到标记。

• 浅灰色：深灰色点的子树，不会受到任何影响。

• 橙色：白色点的非深灰色儿子，可能会得到下推而来的标记。

• 黄色：橙色点的子树，不会受到任何影响。

设 表示考虑了前 个操作后，在生成的 棵线段树中， 点有标记的情况数。

对于所有点，若第 次选择不操作，方案数显然是 。

白，深灰，浅灰，黄 这四种颜色的转移都是固定的，唯有橙色“可能会得到下推而来的标记”，所以不能仅利用 就完成计算。

具体地，对于橙色点 ，若这一轮选择操作，那么 点能得到标记当且仅当 到根的路径上有某个点有标记。

于是记 表示考虑了前 个操作， 到根的路径上没有标记的情况数。 则为至少有一个标记的情况数。

下面对各类点写出转移：

• 白：白点的所有祖先也都是无标记的白点。

• 深灰：本身必有标记。

• 浅灰：本身的标记无影响，但一定存在一个祖先有标记。

• 橙：有标记当且仅当自己到根的路径上有。

• 黄：无论从 还是 的角度都不会受到影响。

用线段树维护上述转移，对于 白，深灰，橙 三色，点数是 级别的，可以暴力转移，对于 浅灰和橙，则使用懒标记（乘法标记）。

维护 的子树和即可回答询问。

复杂度 。