Solution Set - NOIP2022

枚举 C 或者 F 最左边的那一竖，考虑对于每一个这一竖上的全 \(0\) 区间 \([l,r]\) 求答案。

记每个点向右延伸最多延伸到 \(L_{i,j}\)，对于 C 的情况，枚举列 \(k\)，枚举 \(i,j\)，方案数为：

\[\sum_{i=l}^r\sum_{j=i+2}^r (L_{i,k}-1)(L_{j,k}-1)
\]

容易前缀和优化，F 类似做即可。

首先做 \(k=2n-2\)，考虑选定一个为空的栈为缓冲栈，称这个栈为 \(p\)。

对于前 \(n-1\) 个栈，每个栈放置两个不同种类的卡片的话，接下来无论进来哪种颜色我们都有能力删除，解决 \(k=2n-2\)。

考虑 \(k=2n-1\) 的情况，此时会存在一个额外的颜色，我们讨论如何处理这个颜色，注意这里的处理一定满足了前 \(n-1\) 个栈各有两个不同的颜色：

记 \(p_x\) 表示某一个物品下一个与之相同的编号，若存在栈 \(i\) 中的物品 \(x,y\)，\(x\) 为栈顶，\(y\) 为栈底，满足 \(p_y<p_x\)，则可以将 \(p\) 放入当前栈，因为 \(y\) 一定会比 \(x\) 先被消除。
如不存在，将下一个颜色 \(p\) 放置于缓冲栈，考虑下一个是栈底或者是 \(p\) 的颜色，是 \(p\) 可以直接做，若对应栈顶颜色在这个位置之前出现了奇数次则需要将某一个元素放置于缓冲栈，否则同样直接做。

首先缩边双，因为删边双内部的边没有意义，故边双内部的边可以随便乱选，剩下的问题转到树上。

下面的做法有一、复杂。

记 \(f_{u,0/1,0/1/2}\) 表示某个边双选了点 / 没选点，儿子的子树中有 \(0\) 个 / \(1\) 个 / \(\ge 2\) 个内部选了点。

记 \(h_u\) 表示上述答案状态中 \(f_{u,0,1}\) 但是子树中被选定的点的最高点向上的每一条边都被钦定选择的方案数。

可以分类讨论转移，做到线性。

考虑猫树分治，对于每个询问拆成若干个跨越区间中点的询问。

对于右半边，我们预处理出 \(a\) 的前缀最大值和 \(b\) 的前缀最大值，枚举左半边的每一个位置并动态求出最大值，则此时右半边的最大值变化是一个分段函数。

可以用树状数组维护，好像很口胡，可以看看 https://www.cnblogs.com/jz-597/p/13933566.html

还有另一种做法是 https://www.luogu.com.cn/blog/rqy/noip-t4-sol ，大概思路是扫描线维护历史和。

巴特西