Ad-Hoc

其实就是纯种思维题。

来锻炼一下吧。

P8866 [NOIP2022] 喵了个喵

相信大家都知道题意。

$k=2n-1,n\le 300,\sum m\le 10^6,T\le 1005$ 。

首先我们要秒掉 $k=2n-2$ ，然后考虑 $k=2n-1$ 。

还是提一嘴 $2n-2$ ：前 $n-1$ 个栈每个栈维护两种颜色，来一种不在场上的元素直接扔到未满的栈中，来一种处于栈上面的元素就直接扔上去然后消掉，来一种处于栈下面的元素扔到 $n$ 里面然后使用 $2$ 操作。

肯定不能用每个栈维护固定颜色编号的元素那种比较好写的写法来扩展，那样限制太大了，但我们仍然倾向于每个栈维护两个元素。

考虑还是使用 $n-1$ 个栈每个栈维护两个元素，留下一个栈用来辗转腾挪。

如果这 $n-1$ 个栈没全满，那肯定直接扔一个没满的栈里。

称位于栈上面的元素是 $\rm U$ ，下面的元素是 $\rm D$ 。

现在要处理 $n-1$ 个栈都满了，然后又来了一个不在场上的颜色 $\rm S$ 这种情况。

考虑操作序列中 $\rm S$ 和下一个 $\rm S$ （由于保证了有解，所以必定有下一个 $\rm S$ ）之间的这段：

如果全都是 $\rm U$ ，那第 $n$ 个栈肯定没用，直接利用第 $n$ 个栈消掉两个 $\rm S$ ，否则至少有一个 $\rm D$ 。
如果第一个 $\rm D$ 的前面没有它对应的 $\rm U$ ，那可以将 $\rm S$ 放在当前场上 $\rm U$ 的上面，然后遇到 $\rm D$ 的时候扔到第 $n$ 个栈中消掉 $\rm D$ ，否则操作序列一定形如所有 $\rm D$ 前面至少有一个对应的 $\rm U$ 。
考虑直接把 $\rm S$ 放在第 $n$ 个栈中，在遇到第一个 $\rm D$ 之前一定至少有一个对应的 $\rm U$ 且没有其他 $\rm D$ ，考虑把当前场上的那个 $\rm U$ 消完后剩下的 $\rm U$ 全部扔到 $\rm S$ 上面，然后遇到第一个 $\rm D$ 的时候扔到场上那个 $\rm D$ 的头上，就空出了一个新栈。

接下来就是怎么写的问题了。

需要维护每个队列，可以用 $\rm deque$ 省事。
需要找到一个没满的队列，可以线段树，也可以维护一个闲置队列，不过我比较喜欢 $\rm bitset$ ，预留的空栈用变量记录并在 $\rm bitset$ 中将其设置为已满状态。
需要维护每个元素是 $\rm U$ 还是 $\rm D$ 还是 $\rm S$ ，以及维护 $\rm U$ 和 $\rm D$ 的对应关系，这个直接数组搞定。
判断遇到 $\rm S$ 时是哪种情况只需要暴力往后扫看先扫到 $\rm S$ 还是一个 $\rm D$ 即可，然后处理掉中间的这段，这是朴素的。

（如果你使用线段树，你就可以在 $\cal O(m\lg m)$ 的时间内通过本题，达到题目名字的复杂度。）

P9479 [NOI2023] 桂花树

小 B 八年前看到的桂花树是一棵 $n$ 个节点的树 $T$ ，保证 $T$ 的非根结点的父亲的编号小于自己。给定整数 $k$ ，称一棵 $(n+m)$ 个节点的有根树 $T^{\prime}$ 是繁荣的，当且仅当以下所有条件满足：

对于任意满足 $1 \le i,j \le n$ 的 $(i,j)$ ，在树 $T$ 和树 $T^{\prime}$ 上，节点 $i$ 和 $j$ 的最近公共祖先编号相同。

对于任意满足 $1 \le i,j \le n + m$ 的 $(i,j)$ ，在树 $T^{\prime}$ 上，节点 $i$ 和 $j$ 的最近公共祖先编号不超过 $\max(i,j)+k$ 。

注意题目中所有树的节点均从 $1$ 开始编号，且根结点编号为 $1$ 。 $T^{\prime}$ 不需要满足非根结点的父亲编号小于自己。

小 B 想知道有多少棵 $(n+m)$ 个节点的树是繁荣的，认为两棵树不同当且仅当存在某一个节点在两棵树上的父亲不同。你只输出方案数在模 $(10^9+7)$ 意义下的值。

对于所有测试数据保证： $1 \le t \le 15,1 \le n \le 3 \times 10^4,0 \le m \le 3000,0 \le k \le 10,1 \le f_i \le i - 1,500\rm ms$ 。

第一个条件很明显，就是说原树所有的祖先关系都不变，你可以在原树的节点上挂点也可以把边拆开挂点。

第二个条件就比较耐人寻味了，也是本题的难点。

不妨先思考一些特殊情况：

$k=0$ 。

可以得出一些基本的结论：每个节点至多存在一个子树的最小编号 $<x$ 。

进一步地，该树的自上而下树链上至多存在一个下降子序列（表述并不严谨）。

用更严谨的说法：最后的树上除了一条直链上可以任意编号，剩余的点必须满足严格的上面 $<$ 下面，如果没有任意编号的那条链，则答案就是每个未确定的点选一个比它小的点当父亲即可。

你可能会想到 $\rm dp$ ，设 $f_{x,i,0/1}$ 表示 $x$ 子树内添加了 $i$ 个点，不允许/允许新点乱序的方案数，背包合并。

但你发现我们并不方便处理选一坨点代替一条边的情况，这坨点的方案数实在太多。

这种时候就需要换个角度看问题：将 $\max(i,j)$ 拆开，我们令更大的那个元素为主语，则条件二变成：

对于节点 $i$ 和所有比它小的元素 $j$ ，它们在树上的 $\rm lca$ 编号 $\le i$ 。

你发现 $\rm lca$ 不允许是更大的元素，我们一个一个将节点插到树的一个点或一条边中刚好符合这个条件，每次插完点后点数边数都 $+1$ ，答案是 $\prod_{i=1}^m (2i+2n-3)$ 。

$m\le 2$ 。

$m=0/1$ 都是平凡的，你发现 $m=2$ 时除了一个一个插进去，我们还有更多的选择。

更多的选择当然是一个大的挂着一个小的插到一条边中，这是唯一没有覆盖的情况，我们可以枚举每个插入位置判断合法性。

其实只要 $k\ge 1$ ，这种情况就是合法的。

经过了特殊情况的处理，你惊人地发现你已经获得了 $70$ 分，我感觉主要难点是 $k=0$ 的另一种视角。

考场上看到这种分的特别特别细的题千万千万千万别闷头想正解，部分分打出来就能区分同水平选手。

然后我们来想正解。

不难看出，经过上面的启发，第一个条件就是 $[1,n]$ 的虚树就是原树，第二个条件就是 $[1,i]$ 的虚树上最大的节点 $\le i+k$ 。

所以我们可以设计出一个状态： $f_{i,S}$ 表示已经处理完前 $i$ 个节点， $S$ 中的元素还没有插进去的方案数，由于 $k$ 比较小所以我们只关心最近的 $k$ 个元素。

我们在转移的时候其实就是要么不插摆烂加入 $S$ （之后它必须作为一个比它大的元素的下属，否则会算重），要么插到一条边中并捎带上 $S$ 中的若干元素，后者的方案数其实就是插点方案乘上 $s$ 个点的有标号无根树方案 $s^{s-2}$ 。

值得注意的是树的形态上仅仅只有这个点插进去了，然后下面挂了一些东西，如果不是这样的话会算重的，虽然我们并不关心树形态。

复杂度是 $\cal O(m3^k)$ ，很难通过。

后记：不知道我这里在写什么。

考虑优化，你发现一个子树很难选，但是每个点只有一个父亲，考虑设 $f_{i,S}$ 表示处理完前 $i$ 个节点， $[i+1,i+k]$ 这些点中的哪些被加入了当前的树。

这样我们在处理到 $i$ 时，如果它的父亲要从之后选，就从 $\overline S$ 中选一个不在图中的点加入图，并把这俩插到一条边上，不新增一个父亲的情况也要把总点数加上 $|S|$ 。

（这个题跟原树形态无关，很可恶。）

复杂度 $\cal O(mk3^k)$ 。

另一种状态设计的思路：如果钦定要在非原图上找一个爹，那先虚空找一个爹， $S$ 里面记录的是哪些节点发生了虚空找爹这个请求。

然后每个点可以选择成为这个虚空的位置，把贡献延后计算了。

这个就是 $\sim 2^k$ 了。