P5208 线段树
题意：好麻烦……自己看吧
不太了解大家的水平，所以尽量写得详细了一点，没听懂随时打断我问就好/fendou
我们先去看看部分分。
前两个点显然是傻瓜暴力，具体地你模拟一下流程就对完了。
我们考察 \(3,4\) 两个点怎么做。
我们有一个朴素的想法：针对每次操作，枚举每个线段树节点维护它在所有树上受到的影响，并计算增量，在查询时直接输出答案。
由于你有一个性质：一次线段树操作只会遍历到 \(O(\log n)\) 个点。
因此这个想法看起来就很方便优化，于是我们朝这个方向考虑一下。
我们考虑我们的一次区间操作究竟是什么，发现它本质只有 \(3\) 种操作（我们称奇数的树为新树）：
- 对于一个线段树节点 \(x\)，将它在全部新树上赋 \(0\)
- 对于一个线段树节点 \(x\)，将它在全部新树上赋 \(1\)
- 对于一个线段树节点 \(x\)，对于每棵新树，分别查询从根到它的路径上是否有 \(1\) 点，如果有，将它赋 \(1\)，否则不操作
你发现 \(1,2\) 都好做极了，我们只需要对每个点维护一下当前有几棵树 \(1\) 几棵树 \(0\) 就做完了，与树的形态无关。
具体的，对于情况 \(1\)，设在第 \(i+1\) 次操作前有 \(x\) 个 \(1\) 点（未倍增），则之后 \(1\) 点的个数仍为 \(x\)
对于情况 \(2\)，设在第 \(i+1\) 次操作前有 \(x\) 个 \(1\) 点（未倍增），则之后 \(1\) 点的个数为 \(2^i+x\)
然后你发现这个情况 \(3\) 怎么这么坏啊，因为它对树的形态有要求，于是我们不能仅维护一个 \(01\) 个数了事了。
这时通常的思路是去找性质，但你发现它的这种复制再操作一半的操作方式本质上是在操作序列中任选几个按顺序操作，你再感受也找不太到性质了。
那就尝试直接维护满足它形态要求的树的个数，对于一个线段树节点 \(x\)，考虑维护有几棵树从根到它的路径上有 \(1\) 点。
你发现非常坏的一点是，我们对于不 push_down 的部分，不是“赋 \(0\)”而是“不操作”，这使得我们的计算变得困难了。
于是我们将 \(x\) 本身也纳入这条路径中，这样就可以做到满足条件的全部赋 \(1\)，不满足条件的全部赋 \(0\)。
那么现在我们要维护的一共有两个变量，对于一个线段树节点 \(u\)，设 \(u\) 节点为 \(1\) 的树的个数为 \(x\)，从根节点到 \(u\) 存在 \(1\) 的树的个数为 \(y\)。
我们考察第 \(i+1\) 次操作。
对于情况 \(1\)：
对于情况 \(2\)：
对于情况 \(3\)：
然后我们考察那些没有被操作碰到的点，发现它们的 \(x\) 显然是翻倍，对于我们新设的 \(y\) 变量来说，不难发现未被遍历到的节点要么完全在操作内，要么完全在操作外。
在操作内的，\(y+=2^i\)。
在操作外的，\(y\) 翻倍
这里应该不难理解。
从这道题中，我们发现，我们不仅可以将线段树作为一个数据结构来看待，使得一个节点维护区间信息或懒标记，还可以将它作为一个简单的树形结构去看待，使得一个节点维护自己本身的信息。
最终代码实现里，线段树上应该会同时维护 tag 信息和自身的 \(x,y\) 信息，实现不难，建议写一写辅助理解。/qiang
代码：咕咕咕
ps. 实则是一直写这个要讲了没时间写了，如果真的很需要代码实现的话直接来找我我写一下也行/hanx，有没听懂的也直接来找我问就行
pps. 因为只有口胡没有实现所以可能会有误，如果发现问题那有可能是我写错了，但思路应该没问题