杂题20250909-

20250909 杂题

CF961F k-substrings

binary search hashing string suffix structures *2700

对于每个 k-substrings，求出最大奇数 border。

肯定要尝试从其他 k-substrings 推出现在的结果。

注意到：若 \([i,n-i+1]\) 的答案是 \(x\)，\([i+1,n-i]\) 的答案最小是 \(x-2\)。也即：

\[X_{i+1} \geq X_{i}-2\\ X_{i} \leq X_{i+1} + 2 \]

势能分析可知 \(O(n)\)。

CF620F Xors on Segments

data structures strings trees *2800

首先区间和变成前缀和没啥好说的。

特别的，这个前缀和其实可以 \(O(1)\) 求。

ds

考虑只有一个询问咋做？

一个简单的想法是，按照值大小将 \(s_{a-1}\) 加入 Trie 中，容易做到 \(O(n\log{V})\)。

考虑多个询问。要维护 Trie，不好扫描线了，考虑莫队。

还有一个问题是要保证 \(a\) 的大小关系。

考虑在 Trie 树上插入 \(s_{a-1}\) 时记录最小 \(a\)。

另开一个 Trie 插入 \(s_a\)，记录最大 \(a\)。

但记录 \(a\) 就不好删除了，所以写回滚莫队即可。

\(O(n\sqrt{n}\log{V})\)。

dp

\(O(n^2)\) 是可行的。我们可以求出两两的结果，然后再做个区间扩展之类的东西就好。

但发现空间太大了。

考虑扫描线消去一维即可。

CF468D Tree

graph matchings *3100

首先考虑最大答案是多少。

将 \(\operatorname{dis}\) 的贡献拆开摊到每一条边上，就是在求 \((i,p_i)\) 分别在子树两边的个数。

可以知道答案应该有一个上界：假设断掉边 \(e(u,v) \in E\) 后形成的两个连通块分别为 \(e_1,e_2\)，则答案不超过 \(2\sum_{e \in E} \min(|e_1|,|e_2|)\)。

我们把一个点 \(i\) 拆开成两个点 \(i\),\(i'\)，\(p_i=j\) 等价于 \(i\) 和 \(j'\) 匹配。想要达到这个答案上界，当且仅当对于每一条边来说，其较小的那个连通块内部不存在匹配。

为了更好的表示出每个边的较小连通块，我们将重心视为树根，这样子每个边的较小连通块就是深度较大的那个。如此，前面的要求就可以更为简单的表示为与根相连的子树内部不存在匹配。可以视为每个点只能和对应子树外的点进行连边，是否存在完美匹配。

根据 Hall 定理，二分图存在完美匹配当且仅当对于任意点集其邻域点数更多。考虑到这张图同一个根子树内点具有相同的邻域，且选择任意两个不同根子树的点邻域为全集，可以表示为对于任意根子树 \(sz_u \leq n-sz_u\)。

由于重心满足 \(sz_u \leq \lfloor\frac{n}{2}\rfloor\)，所以图一定有完美匹配。也即一定能达到答案上界。

考虑构造字典序最小的答案，点只能与根子树外的点连接，我们考虑何时贪心会出错。

还是 Hall 定理，我们将匹配视为同时删去两个点，判断剩下的点是否还有完美匹配。

考虑无论和时左右部点的个数是相等的，我们只需要对每个根子树考察是否满足 \(\text{树内左部点} \leq \text{树外右部点} = \text{剩余点数}-\text{树内右部点}\)。如果某棵树满足 \(\text{树内左部点} + \text{树内右部点} = \text{剩余点数}\) 就必须选这棵树了。（这里的剩余点数是左（或右部点）总点数）

CF891D Sloth

dfs and similar dp graph matchings trees *3100

断开后两种情况：

• 两块各自匹配

• 连接点是一个匹配

先考虑断边被确定了怎么做。对于断边后的两个连通块各自跑一遍 DP 求出有多少个点删去后有完美匹配 \(f\) 以及整个图是否有完美匹配 \(g\)。

若 \(g_u \wedge g_v\) 则答案是 \(sz_u \times sz_v\)，否则是 \(f_u \times f_v\)。

考虑到转移方便，我们具体的设 \(f_{u,i,j}\) 表示 \(u\) 为根的子树，\(u\) 是否匹配，子树内（不算根）有无未匹配点的选点方案数。

转移时先将子树接到 \(u\) 上再进行合并，也就是枚举是否连向根。这样子合并的后两维是 \(\bmod x^2y^2\) 的转移形式，是交换，结合的。是交换，结合的就可以换根。

贡献类似最开始的 \(f,g\)。

CF442E Gena and Second Distance

geometry *3100

极角，二分，随机增量法。先咕着。

CF786E ALT

data structures flows graphs trees *3200

网络流，优化建图。先咕着。

LGP2423 HEOI2012 朋友圈

图论 网络流 二分图 省选/NOI−

咕咕咕。

AGC004F Namori

基环树 >4000

可能不太严谨。

• 树

将树进行奇偶染色。原图中的白点在新图中和深度的奇偶性相同，黑点和深度的奇偶性相反。

问题变为通过交换树上两点使得树上所有点颜色取反。

所以有解条件就是黑白点个数相同。

考虑每条边的贡献。记黑点为 \(1\) 白点为 \(-1\)，这条边的交换次数就是子树权值和的绝对值。（一次交换应当使得子树内实际权值和变化 \(2\)，而我们希望令子树权值取反）

• 基环树

对于偶环基环树，仍然是二分图可以黑白染色。

视作把若干棵树的根串成一个环，先对每一棵树独立求解树权值。

然后有一些环上移动。记 \(x_i\) 表示 \(i\) 树向 \(i \bmod len + 1\) 传递的黑点数量，则应该有：

\[\begin{cases} A_1 = x_1 - x_n\\ A_2 = x_2 - x_1\\ \vdots\\ A_n = x_n - x_{n-1} \end{cases} \]

注意到这里的线性无关方程数目为 \(n-1\) 也即有一个自由元。我们钦定为 \(x_1\)，则：

\[\begin{cases} x_2 = A_2 + x_1\\ x_3 = A_3 + A_2 + x_1\\ \vdots\\ x_n = \sum_{i=2}^{n}A_i + x_1 \end{cases} \]

需要最小化 \(\sum|x|\)，根据初中知识我们取 \(-\sum_{i=2}^{x}A_i(1 \leq x \leq n)\) 的中位数即可。

具体实现上，我们将断边后的根视为 1，底视为 2，那么就是除开根以外的环点贡献 A，根贡献 0.

还有就是奇环基环树。不满足二分图性质所以不能直接用上面的做法。要更细致的考察。

还是黑白染色，我们考察连接同色点的边，进行一次操作相当于创建/删除两个黑点。所以其存在意义就是改变两种点的个数使他们平衡。贡献是 \(A/2\)。

总而言之，结合上面的三种情况，得到了做法：

• 跑一遍树形 DP 求出 A

• 如果是偶环基环树，将环上 A 取出得到中位数，将环上加上这个数。

• 如果是奇环基环树，根据总树的 A 操作断边。

• 对 A 绝对值求和。

• 注意判无解。
  ​

UOJ#164 清华集训2015 V

线段树

• 区间加 \(a\)

• 区间减 \(a\)，有下界

• 区间推平为 \(a\)

• 单点查询

• 单点查询历史最值

历史最值线段树问题。

我们发现操作都可以表示为 \(x \mapsto \max(x+a,b)\)（等价于 max+ matrix），这个操作有结合律，于是设计 Tag 对应上面的操作。

信息是当前值和历史最值，记作 \((0,x,y)\)，考虑操作：

• 区间加 \(a\)

\[\begin{pmatrix} 0 & -\infty & -\infty\\ -\infty & a & a\\ -\infty & -\infty & 0\\ \end{pmatrix} \]

• 区间减 \(a\)，有下界

\[\begin{pmatrix} 0 & 0 & -\infty\\ -\infty & -a & -\infty\\ -\infty & -\infty & 0\\ \end{pmatrix} \]

• 区间推平为 \(a\)

\[\begin{pmatrix} 0 & a & a\\ -\infty & -\infty & -\infty\\ -\infty & -\infty & 0\\ \end{pmatrix} \]

矩乘经典问题：空间太大，常数太大。

观察到只有右上角四个数变了，推导一下：

\[\begin{pmatrix} 0 & a_1 & b_1\\ -\infty & c_1 & d_1\\ -\infty & -\infty & 0\\ \end{pmatrix} \begin{pmatrix} 0 & a_2 & b_2\\ -\infty & c_2 & d_2\\ -\infty & -\infty & 0\\ \end{pmatrix}= \begin{pmatrix} 0 & \max(a_2,a_1+c_2) & \max(b_2,a_1+d_2,b_1)\\ -\infty & c_1+c_2 & \max(c_1+d_2,d_1)\\ -\infty & -\infty & 0\\ \end{pmatrix} \]

确实没变。维护四个位置即可，常数大大减小。

小心 -inf 溢出！！！

小心 -inf 溢出！！！

小心 -inf 溢出！！！

小心 -inf 溢出！！！

小心 -inf 溢出！！！

小心 -inf 溢出！！！

在每次操作完对 -inf 取 max。

LGP2611 ZJOI2012 小蓝的好友

平衡树 深度优先搜索 DFS 栈 省选/NOI−

简单题。

至少包含一个点的矩形的数量，显然转化为不包含点的矩形数量。

先扫描线确定矩形左边界。

此时假设确定了上下边界，答案就是范围内最靠左的点的横坐标减去左边界坐标。

于是我们考虑构建每一列已扫描最靠左的点的笛卡尔树。

注意到位置为随机生成，树高不会超过 \(O(\log{n})\)。

直接类似 FHQ Treap 维护并动态统计答案即可。

问题在于如何动态确定点的区间数。

这个应该是和 \(l,r\) 有关的二元多项式，仔细分析可以发现下层只会加上来，所以次数不会发生变化，\(\operatorname{deg}(F) \leq 2\)。

还有个问题是初始化系数出现了 \(\frac{1}{2}\)，于是我们维护 \(2\) 倍的多项式，最后答案除一下就好了。

\(O(n\log{n})\)。

额外题

ARC087F Squirrel Migration

CF468D Tree 的同结论计数题

CF468E Permanent

没什么说法