wangyisong1996的博客值此NOI来临之际，我们优化了评测鸭在线 https://duck.ac/ 的各方面体验：
欢迎积极到评测鸭用户群（群号 781384211）反馈使用体验，你的一份支持将是我们最大的动力！也欢迎来 GitHub 围观我们的开源仓库，提提 Issue 和 PR，详见 https://github.com/JudgeDuck
最近在学信号处理课，学到了DFT和FFT，想起多项式乘法这个题，来卡一卡常数（雾）。
代码：http://uoj.ac/submission/206573
（未完待续）
题面：http://uoj.ac/contest/32/problem/218
有$n$个栈，区间压数，单点弹栈，求区间栈顶和。
看到此类区间修改，区间询问的题目，我们很容易想到线段树这样的数据结构。
我们可以通过对线段树打标记来实现区间修改。在访问线段树的每个结点时，我们还需要进行标记下传。
这种做法要求标记能快速合并，并且有结合律。
这题的修改操作为“区间压数”，即对区间的每个栈压一个数进去。 所以我们可以考虑用一个序列来表示标记，该标记的意思为对于这个线段树区间里的每个栈，都要将这个序列按顺序压进去。 于是合并两个标记的时候就只要将这两个序列连接(join)。
在区间压数操作中，我们找到对应的区间后，给该区间打上一个只有一个元素的序列的标记。
在单点弹栈操作中，我们将跟该点有关的标记全部下传之后，需要将该点的标记里的序列中第一个数删掉（即“弹栈”），并更新该点的答案。
由于有询问区间和的操作，我们在线段树上还需要维护区间和，只要在标记下传的时候维护即可。
除了需要维护一个“序列”以外，线段树上所有操作的复杂度都是$O(\log n)$的。
这个序列需要支持：
以上操作都要求完全可持久化。
在一次题目的操作中，会有至多$\lceil 2 \log n \rceil$次序列连接操作，和至多一次生成序列或者删除第一个元素的操作。
我们可以使用可持久化平衡树（如AVL或treap）来维护这些序列，复杂度为严格或期望$O(\log n)$单次序列操作。
这样题目中每次操作的复杂度为$O(\log ^ 2 n)$，并不是很优美，而且平衡树常数很大，代码也很难写……
我们可以用一种不知名的二叉树来维护这个序列。
对于一个长度为$k$的序列，对应的二叉树上有$2k-1$个结点，其中根节点的值为该序列的第一个元素的值。
我们可以这样递归定义这种二叉树以及其连接操作：
可以证明这样构造的二叉树满足其定义。
在序列中删除第一个元素的时候，我们从根开始，一直向左走直到叶结点，则这个叶结点一定表示序列中第一个元素。
我们将这个叶结点的父结点替换为这个叶结点的父结点的右儿子，并更新父结点到根路径上的每个结点的值。
对于该叶结点没有父结点的情况，说明是只有一个元素的序列，直接返回空树即可。
生成序列、序列连接都是$O(1)$的，删除第一个元素是$O(表示序列中第一个元素的结点的深度)$的。
注意到在线段树上，打标记会使该深度变为1或2，每次标记下传会使该深度加一。
由于线段树的深度不超过$\lceil \log n \rceil$，所以该深度不会超过$\lceil \log n \rceil + 1$。
另外注意到每个元素的深度可以单独分析，于是在删除了第一个元素后，第二个元素的深度也满足上述条件。
所以删除第一个元素的复杂度为$O(\log n)$。
综上，这个做法在题目中单次操作的复杂度为$O(\log n)$，可以AC此题。
用带标记的线段树这一经典数据结构和二叉树的有关知识，给出了一个简单的算法， 然后通过观察线段树标记下传的性质，证明该算法的复杂度为每次操作$O(\log n)$。
...妈妈我终于会做未来程序·改了！
$ $
然而代码有102557B，交不上来
UPD: RE了，大家再见
UPD: A掉辣
鄂公网安备 42010202000505 号Server time: 2024-11-21 13:13:35
