2024.1 ~ 然后是 irony / 再见了 melody-526互联

QOJ2402

容易在 $O(\log x)$ 步内构造出一个只有 $x$ 的栈。

考虑从后往前构造，记录当前 + 的数量，假设是 $k$，那么我们构造一个 $x_i+k$ 出来即可。

QOJ4996

这么牛？？

考虑增量构造，每次插入一个点进来。

设当前的前后缀切换点为 $x$，当前点为 $y$，那么如果 $x,y$ 有连边就把 $y$ 放到 $x$ 的无连边一侧；反之放在有连边一侧。经过简单的分类讨论发现，这样一定是合法的。如果当前全部都是无连边或者有连边，直接插入到最后即可。

为了让 $1$ 当链顶，写起来会麻烦一点。

QOJ895

相当于每种颜色需要有 $L=\frac{m+1}{2}$ 个匹配。显然需要有 $2\mid (m+1)$。

考虑每种颜色当前可能是某些匹配和一些单点，假设有 $p$ 个匹配和 $n-2p$ 个单点，发现由于单点最后都得形成匹配，那么必须要有 $n-2p\le m-n+1$，也就是 $2n-2p\le m+1$。

如果这个限制已经不满足了，那么显然是无解的。否则考虑增量构造，每次从 $n\to n+1$，并维持此条件成立。容易发现当 $n=m+1$ 时，必有 $p=\frac{m+1}{2}$。于是我们只需要做到 $n\to n+1$ 即可。下面证明这时一定有解。

考虑建一张二分图，左边有 $m$ 个点代表 $m$ 种颜色，右边有 $n+1$ 个点。对于颜色 $i$，如果 $j$ 此时在图中不在 $i$ 的匹配内，就连边 $i\to j$；同时对每种颜色 $i$，设其当前匹配数为 $p_i$，就连 $m+1-2p_i-2n$ 条 $i\to n+1$ 的边表示 $i$ 不参与匹配。可以发现如果 $2p_i-2n=m+1$ 那么就不会连这条边，意思是必须被匹配。

这里 $n+1$ 号点我们认为其可以被匹配 $m-n$ 次，意思是至少有 $n$ 种颜色被加上。

现在我们需要证明左边的点都能匹配上。考虑左部点的出度，发现到 $1\cdots n$ 中恰好连 $n-2p_i$ 条，于是总的出度就是 $m-n+1$；再考虑每个右部点的入度，发现此时 $i$ 恰好在 $n-1$ 个匹配中，于是其入度恰好是 $m-n+1$；对于 $n+1$ 号点，不难算出其入度是 $m(m-n+1)-n(m-n+1)=(m-n)(m-n+1)$。那么只需要把这个点拆成 $m-n$ 个点，就得到了一个左右各 $m$ 个点的二分正则图。

由 Hall 定理可知二分正则图必存在完美匹配，于是就成功从 $n$ 扩展到了 $n+1$。

只需要跑 $m-n+1$ 次二分图匹配，使用 dinic，总复杂度为 $O(m^4)$。

LOJ3655

维护行的线段树，发现为了支持这个操作需要维护 $(mn,cnt,sum)$ 表示区间 min，区间 min 的个数，区间和。

对于标记维护 $add_1,add_2$ 表示区间 min 被加上了 $add_1$，然后这个区间全局加了 $add_2$。

同时每个节点维护一个 set，里面存这个点所有的 chkmin 操作。这里我们把这个 set 看成元素而非标记，或者是看成永久化的标记。那么一个点的实际 $mn$ 就是到根的一条链上的 set 里面最小值再取 min。

对于 chkmin 操作，我们在 $O(\log n)$ 个节点上插入这个东西并更新 $mn$，然后一路 pushup。这样可能会导致更深的子树里面的 $mn$ 出错，但考虑在做加法的时候，我们一路判一下当前到根的链上的 $mn$ 会不会导致当前的区间 min+ 变成区间整体 +，这样就没有问题了。

如果要撤销一次操作，找到这些标记覆盖到了哪些节点上，同理先下传 add，然后把这个点的标记删除，再 pushup。

然后还需要写一个 ODT 来去除白 $\to $ 白，黑 $\to $ 黑。

2024.1.3

A

连边建图后如果有度数 $\ge 3$ 的点就无解。否则图一定形成环和链。

考虑一个环，其贡献一定是将答案 $\times 2$，然后自己内部就解决掉了。考虑一条链，发现选择方向后会贡献一个入点和出点。设长度为 $1,2,\ge 3$ 的链分别有 $A,B,C$ 条，那么首先方向的选择会贡献 $2^{B+C}$ 的系数。

接下来发现将出点和入点匹配的方案数是 $(A+B+C)!$，但是二元环在选择不同方向的时候自己匹配自己的情况会算重。考虑钦定二元环自己匹配自己，发现每匹配一个就会有 $\frac{1}{2}$ 的贡献。于是赋一个 $-\frac{1}{2}$ 的容斥系数即可。

B

把 $w_l+w_r$ 拆开分别算贡献，线段树简单维护

C

PGF 板子。

这里发现一个事情之前不是很明白啊，为什么需要去除 $S_i$ 是 $S_j$ 子串的情况？注意我们列方程的时候直接往后加上一个 $S_i$ 使其达到目标，然后去考虑实际的结束时间；但我们考虑实际的结束时间的时候总是认为是一段前缀和后缀叠一起，如果出现子串的情况就可能会出现在中间出现的情况。

QOJ4000

看到这种肯定就是要 bitset。操作分块，每 $B$ 个操作分一块。

考虑当前这一块内的操作影响到的边，一共只有 $O(B)$ 条，至多影响 $O(B)$ 个点。然后还有询问，但也只有 $B$ 个。称这些边和点为关键边和关键点，那么非关键边不会变化。对非关键边缩点，然后算出 $f_{i,j}$ 表示第 $i$ 个关键点能否通过非关键边到达第 $j$ 个关键点，这里可以使用 bitset 优化到 $O(n+m+\frac{(n+m)B}{w})$。

然后建一张新图，新图中有 $O(B)$ 个点，$i\to j$ 有边当且仅当 $f_{i,j}=1$。每次暴力加入新边，然后在图上 BFS/DFS 查询 $u$ 能否到达 $v$。这里也可以用 bitset 优化，具体来说考虑我们正常 DFS 是每个点 $u$ 维护一个 $vis[u]$，每次访问到 $u$ 就 $vis[u]\leftarrow 1$，然后走出边的时候只沿着 $vis[v]=0$ 的边 $u\to v$ 走。发现维护邻接矩阵每行的 bitset 之后相当于要对 $f_i\ \&\ vis$ 进行一个 Find_first，这个可以用 bitset 优化到 $O(\frac{B}{w})$。

于是就可以在 $O(\frac{B^2}{w})$ 的时间内完成 DFS 判断，清算一下复杂度，发现是

\[O\left(\frac{q}{B}\left(n+m+\frac{(n+m)B}{w}\right)+q\frac{B^2}{w}\right)=O\left(\frac{q(n+m+B^2)}{w}+\frac{q(n+m)}{B}\right) \]

取 $B=O(w)$，复杂度为 $O(\frac{q(n+m)}{w}+qw)$。

QOJ3998

相当于 $\sum_{i=1}^k f(i)\ge k\times E$。

考虑一个 $f(i)$ 咋算，发现已经需要背包了...

注意到对于一个 $l$，可行的最远的 $r$ 具有单调性，考虑双指针，发现背包不支持删除比较麻烦...

有一个东西叫 baka's trick 但是这个需要支持信息能快速合并

考虑整体二分，$\text{solve}(l,r,s,t)$ 表示确定了 $[l,r]$ 中的最远右端点都在 $[s,t]$ 中，然后取 $p=\lfloor(l+r)/2\rfloor$，考虑算一下 $p$ 的最短的可行区间。我们维护一个全局的背包，在 $\text{solve}(l,r,s,t)$ 的时候背包里面存的是 $[l,r]\cup[s,t]$ 外面的所有物品，这里可能有些是涨价前的有些是涨价后的但都无所谓，总之它们一定在背包内且价格恒定。

然后这里算 $mp$ 发现如果正着扫需要进行一个背包删除，又寄了。解决方法是二分答案，先取 $mr=\lfloor (s+t)/2\rfloor$，然后把 $[s,mr]$ 中的物品涨价加入，$[mr+1,t]$ 中的物品正常加入，判断是否合法；如果要往一侧二分，那么就提前加入另一侧的物品。这样复杂度是 $T(n)=T(n/2)+O(n)=O(n)$，于是加入次数就是 $O(|s-t|)$。

然后我们算出来最短右端点 $q$ 之后要递归到 $\text{solve}(l,p-1,s,q),\text{solve}(p+1,r,q,t)$，额外加入多余的部分就行了。注意背包虽然性质很弱只能插入，但它可以和插入等时间地复制。

UOJ群

给一个长为 $n$ 的字符串和 $k$，你需要对其每个长为 $k$ 的子串算出来其最短整周期的长度。

$1\le k\le n\le 2\times 10^6$。

暴力：$O(n\times d(k))$。

考虑选一个 $m$，可以 $O(n)$ 算出来每个长为 $k$ 的子串的最短整周期是否为 $m$ 的约数。于是只需要对每个 $p^i\mid k$ 都去尝试 check 一下 $\frac{k}{p^i}$ 这个长度是否为其周期，就可以确定每个位置实际的最短整周期。

复杂度显然不会超过 $O(n\log n)$。

弱智群

如果要做循环卷积那就是直接 FFT，因为 FFT 本身就是循环卷积的过程。

平时对长度 $n,m$ 的序列卷积开到 $n+m$ 只是为了不让他循环。

这里其实就导出一个经典问题就是多项式快速幂，为什么不能先 DFT 然后每个位置快速幂再 DFT 回来呢？因为这样的话实际上就循环了，但是通常我们做的是 $\bmod x^n$ 也就截取 $n$ 位。

也就是说实际上我们 FFT 做的是 $\bmod (x^n-1)$ 而非 $\bmod x^n$。

Luogu6113

怎么这个还有板子题的

recall 一下 Tutte 矩阵：考虑 $\frac{n(n-1)}{2}$ 个变量 $x_{i,j}$（$i< j$），考虑如下矩阵

\[A_{i,j}=\begin{cases}x_{i,j}&,(i,j)\in E\land i<j\\-x_{j,i}&,(i,j)\in E\land i>j\\0&,(i,j)\not\in E \end{cases} \]

我们依次证明几个定理：

$G$ 存在偶环覆盖，当且仅当 $G$ 存在完美匹配。

其中偶环覆盖指的是用若干点不相交的大小为偶数的简单环覆盖整张图，这里二元环也算偶环。

考虑完美匹配可以看作若干二元环的覆盖，而对于一个偶环覆盖，将其中的每个偶环隔一个取一条边即可得到一个完美匹配，因此二者等价。

$G$ 存在偶环覆盖，当且仅当上面的矩阵 $A$ 的行列式不为 $0$。

考虑算行列式的时候会取到一个 $p$ 并附上 $\text{sgn}(p)$ 的系数，然后把 $A_{i,p_i}$ 相乘。

考虑一个使得 $A_{i,p_i}\neq 0$ 的排列 $p$，发现这相当于用若干环覆盖整张图。

我们发现只要存在一个奇环，

额咋证来着，好像是奇环的 $\sum \text{sgn}(p)$ 之和为 $0$ 啥的，反正这个是对的

$G$ 的最大匹配为 $\frac{1}{2}\text{rank}(G)$。

感性理解一下就是选出一个点集使得其存在偶换覆盖，也就是 $\text{det}\neq 0$。

那带着 $x$ 直接做高斯消元肯定不现实，但是我们有 S....-Zi... 定理，任取 $x_{i,j}=\text{rand}(0,p-1)$，那么就有 $1-\frac{n}{p}$ 的概率算对。多带几次把算出来的 $\text{rank}$ 取众数即可。

坏处是复杂度为严格 $O(n^3)$，过不去这个题...

QOJ4998

考虑每次 $1$ 操作相当于连边 $(l,r),(l+1,r-1),\cdots$，$2$ 操作是查询 $(a,x),(a+1,x+1),\cdots$ 是否都分别连通了。考虑直接维护连通块，那么合并次数至多为 $n-1$。我们要做的就是快速找到所有发生合并的位置。

考虑对每个点所在的连通块维护一个哈希值，然后线段树维护整体的区间哈希值。只需要在线段树上维护一个区间正着的哈希和反着的哈希即可快速得到所有合并的位置，在合并的时候使用启发式合并暴力更改小的那一侧的所有哈希值即可。总复杂度 $O((n+q)\log^2n)$。

区间哈希可以用树状数组实现，对完了

P9997

对树进行轻重链剖分。

对于查询，我们将贡献分为两部分：跨越重链的，以及在一条重链内部的。

对于跨越重链的，考虑枚举它经过了哪条轻边，那么对于一条轻边 $O(X)$ 种情况，这部分的复杂度 $O(X\log n)$。

对于重链内部的，考虑对每个满足 $u$ 到 $top_u$ 路径上至少有 $X$ 条边的点 $u$，维护 $u$ 上面 $X$ 条边正着下来或者倒着上去形成的字符串的哈希值 $f_u,g_u$。那么每次就是查询一条链上有多少个 $f_u=$ 给定字符串的哈希值。维护树状数组套哈希表即可。时间复杂度单次 $O(\log n)$。

考虑修改，发现一共只会经过 $O(\log n)$ 条重链，且至多只会影响一个重链内的一个长度为 $O(X)$ 的区间内的 $f,g$，重新计算这些 $f,g$ 即可。这样修改的复杂度也不超过 $O(X)$。

于是重链内部就是有 $O(mX)$ 次单点修改，$O(m)$ 次查询一条链上 $=v$ 的元素个数。离线下来容易解决。

总复杂度 $O(n+mX\log n)$。写起来比较繁杂，但各部分想清楚都不难实现。

2024.1.5

zkw 费用流：就是多路增广。在层数比较少，或者费用较小/图比较稠密的时候表现比较好。

其他时刻可能不如 EK。

dij 费用流

类似 Johnson 全源最短路进行重标号 $h$。

设 $d'[i]$ 表示 $w'(x,y)=w(x,y)+h[x]-h[y]$ 的边权下 $s\to i$ 的最短路，考虑每次增广一条最短路之后，对每条 $(i,j)$ 我们会加入 $(j,i)$，必有 $d'[i]+w'(i,j)=d'[j]\iff d'[i]+h[j]+w(i,j)-h[j]-d'[j]=0$。

于是令 $h'[i]\leftarrow h[i]+d'[i]$，我们新加入一条 $w(j,i)=-w(i,j)$ 之后的边之后，有

\[w'(j,i)=h'[j]+w(j,i)-h'[i]=h'[j]-w(i,j)-h'[i]=h[j]+d'[j]-w(i,j)-h[i]-d'[i]=0 \]

于是对于新加入的那条最短路上的边，这个不等式仍然成立。对于原图中的边，考虑三角不等式：

\[d'[i]+w'(i,j)-d'[j]\ge 0\\\iff d'[i]+h[i]+w(i,j)-h[j]-d'[j]\ge 0\\ \iff h'[i]+w(i,j)-h'[j]\ge 0 \]

所以直接令 $h'[i]\leftarrow h[i]+d'[i]$，就是一个合法的新的重标号。

于是我们就可以跑 dij 啦

最小费用可行流

一直增广直到新的增广路的费用 $>0$。最大费用同理。

由于费用流的费用关于流量成凸函数所以就是这样。

有负环最小费用流

对于每条负边 $(u,v)$，容量为 $c$，费用为 $d<0$，先把 $c\times d$ 加到答案里，然后连边 $s\to u,v\to t$，上下界都为 $c$，再连边 $v\to u$，上下界 $[0,c]$，费用 $-d$。然后跑有源汇上下界最小费用流。

P9999

写一下代码...

考虑维护这样一个 FHQ Treap，维护若干个点，其中 dfn 为比较关键字，同时每个点额外记录 $d$ 表示这个点到其重链链顶的距离，每个点还需要维护子树中 $d$ 的最小值。

现在考虑将所有点向 $u$ 移动一步。先考虑 $u$ 到根链上的点，这部分会有 $O(\log n)$ 次重链交换，依次考虑每条重链，这上面的 dfn 是连续的，可以找到哪个点需要下来，然后改一下这个点，同时给这段区间打一个 $\text{DFN}+1,d+1$ 的标记。

再考虑链外面的点，发现仍然是 $O(\log n)$ 段 DFN 的连续区间，但 $d=0$ 的位置需要暴力重新计算。那就把这些点先 split 出来之后，别的地方打标记，把 $\text{DFN}-1,d-1$。

平面图两点可达性

对于每个点，把其出边对面的点按照和他连线的斜率排序，第一次 DFS 正着扫，第二次倒着扫，然后分别算出两次的 DFS 序 $p,q$，那么 $x$ 能到 $y$ 当且仅当 $p_x<p_y,q_x<q_y$。

但是这个不能处理环，需要缩点。动态咋做呢，我也不太会

哎这不是我们 [CEOIxxxx] Traffic 吗，zzyz 模拟赛都有

2024.1.6

A

钦定完 $k$ 个点后，一个点的贡献形如 $a_i\times \left(\binom{k}{2}-\sum_{j}\binom{cnt_j}{2}\right)$。

$f_{u,j}$ 表示 $u$ 子树内放了 $j$ 个点，此时的最大贡献即可。

B

打表找规律发现所有可能的 $a_i$ 满足：

$a_1=0/1,a_n=0/1$
$|a_i-a_{i+1}|\le 1$
不存在 $2\le i\le n-1$ 使得 $a_{i-1}=a_{i+1}=0,a_i=1$。

对着这个 DP 即可。

C

先补全成三角剖分，然后按照 2023.3 zzyz 模拟赛 xxx 题目的方式分治即可。

注意这里带边权，分治下去的时候如果选的是 $(u,v)$，那么 $u\to z,v\to z$ 的边权都要重新赋值为当前 $u,z$ 或者 $v,z$ 两点间的最短路。

2nd Ucup Stage.17 : Jinan

这部分是场上写的。

D

$r_a-l_a+1\ge 10,r_b-l_b+1\ge 10$ 的时候答案是 $9$；否则暴力。

K

令 $a_i\leftarrow a_i-i$，考虑对一个区间咋算答案，发现是取中位数，把别的都挪到中位数。

双指针，权值线段树维护第 $k$ 大和区间 $\sum a_i$ 即可。离散化一下。

B

根号分治，取阈值为 $B$。$k\le B$ 直接 DP：$f(u,j)$ 表示 $u$ 子树内挂一个大小为 $j$ 的连通块的方案数。

转移的时候考虑新的边要不要割掉即可。考虑 $k>B$ 的时候，我们的问题是不知道 $u$ 这个连通块的大小。

考虑直接记录 $g(u,x,y)$ 表示 $u$ 子树内已经划分出去 $x$ 个 $k$，$y$ 个 $k+1$ 的方案数，这样就可以直接知道 $u$ 所在连通块的大小；而 $x+y\le n/B$，并且感觉上要保持 $u$ 所在连通块大小 $\le k+1$，这个 $x+y$ 状态数不会很多。

复杂度不知道是啥。但是取 $B=n^{\frac{2}{3}}$，复杂度已经不超过 $O(n^{\frac{5}{3}})$；而且感觉 $g$ 的状态卡不满，应该能过！过了。

E

最小点覆盖比较好考虑。判断每个点能否在最小点覆盖内，然后如果一条边 $(u,v)$ 两端点有一个可以在任意一个最小点覆盖内就不合法，否则显然一定合法。只需要判断每个点能否在最小点覆盖内。

建图，$s\to L_i,R_i\to t$，这些边的边权为 $1$；$L_i\to R_j$，这些边边权 $\infty$。在残量网络上考虑，一条边 $u\to v$ 是可行边当且仅当 $u$ 无法在残量网络上到达 $v$；是必须边当且残量网络上仅当 $s$ 能到 $u$，$v$ 能到 $t$。当然还要满流。

注意也不需要有向图两点可达性，因为 $u\to v$ 满流所以一定存在 $v\to u$ 这条边，只需要判是否在同一 scc 内。

日为什么 TLE 啊？？怎么能 $O((n+m)\sqrt{n+m})$ 跑不过 1e5 的

cnm 边数开小了 666666666666666666666666666666666

M

$R$ 一定是凸包。$Q$ 应该是枚举一条边 $AB$，把然后加一个点 $C$，改成 $AC\to CB$ 这样子。

那么相当于判断 $\triangle ACB$ 内部是否有一个点。考虑两个点 $C_1,C_2$，发现这里由于 $C_1,C_2$ 在 $AB$ 的同侧（是凸包），因此 $C_2$ 在 $\triangle AC_1B$ 内当且仅当 $\ang C_1AB>\ang C_2AB,\angle C_1BA>\angle C_2BA$。极角排序即可。

L

相当于区间内全是 $1$ 就有一些收益，对每个 $k$ 求最大收益。

考虑 DP，$f(i,j)$ 表示前 $i$ 个位置放了 $j$ 个 0，转移的话如果这里放 $0$ 就 $f(i,j)\leftarrow f(i-1,j-1)$，否则枚举一个极长的 $1$ 的连续段，转移到 $f(p,j)+\text{cost}(p+1,i)$，其中 $\text{cost}(l,r)$ 是 $[l_i,r_i]\subseteq [l,r]$ 的所有 $v_i$ 之和。

考虑线段树维护 cost，这样有一个 $O(n^2\log n)$ 的做法，按 $j$ 从小到大转移，这样好像空间就是 $O(n)$ 了。

但是这个显然过不去吧！！！唉唉会不了一点

Hello 2024

E

首先我们在 $p$ 中插入一个 $0$，现在就等价于要将 $p$ 进行排列，使得 $p_0=0$，且 $|p_i-p_{i+1}|=1$。

这个题 $n\le 5000$，考虑直接枚举 $p_n=s$，然后从小到大依次放入每个数，维护当前还需要插入的空位个数。

考虑如果当前形成了 $x$ 个空位，我们现在要插入 $y$ 个数进去，且每个空位内至少插入一个数，考虑插板法，那么方案数就是 $\binom{y-1}{x-1}$。然后考虑新的空位有多少个，发现是 $y-x$ 再加上两端是否还要插入新的数。由于已经枚举了起点和终点，因此两端是否已经成段是唯一确定的，可以直接算出新的段数。

F

考虑当前水量 $x$ 以及被限流的水量 $y$。

一开始 $x=0$，每次先 $x\leftarrow \max(0,x+a_i-b_i)$，然后如果 $x>c_i$，就令 $y\leftarrow y+x-c_i,x\leftarrow c_i$。

答案就是 $\sum a_i-x-y$。

将操作离线，扫描线扫序列维，数据结构维护每个时刻当前 $x,y$ 的值。这些都可以用 segtree beats 简单维护。

2nd Ucup stage 17: Jinan

唉来补个题

L

看眼复杂度，$O(n(n+m)\alpha(n))$ 是什么玩意阿

还是考虑 DP，那么相当于有 $O(nm)$ 次前缀 $+v$，$O(n^2)$ 次求全局 max。

考虑维护 $p_i$ 表示 $[1,i]$ 的前缀 max 的位置，那么相同的 $p_i$ 会形成若干极长的连续段，并且从前往后看的话每个连续段对应的值是递增的（就是这个连续段中最靠前的一个此时的值）。维护 $q_i$ 表示这一段和上一段的差，那么每次相当于给某个连续段的 $q_i$ 减去一个值，然后如果 $q_i<0$ 就和上一段合并，再接着看下一段是否需要合并。

由于加的都是正数，所以只会有合并，没有分裂。现在考虑我们还需要快速找到这个点在哪一段内，并查集维护即可。这样复杂度就是 $O(n(n+m)\alpha(n))$。

关于空间：按照 $i$ 从小到大转移即可。