NOIp 2022 全题解

总算有时间来补 NOIp 了。

T1

题意：给定一个 $n \times m$ 的 01 矩阵，问有多少个 1 组成的 C 和 F 图案，对 998244353 取模。 $n, m \leq 1000$ ， $T (T \leq 5)$ 组数据。

C 和 F 是类似的，这里我们只讨论 F 的做法。

注意到考虑枚举极长的竖段，加上两段向右的 1 连续段。可以先求出每个点向右最长的 1 连续段长度，然后在极长连续段上枚举下面横线的位置，动态维护上面所有向右 1 连续段长度和即可 $O (1)$ 计算。

枚举极长竖段的总复杂度相当于枚举每一个点，总复杂度就是 $O (n m)$ 的，可以通过。

T2

到这里看。

T3

题意：给出一个 $n$ 个点 $m$ 条边的无向联通图，选择一些点和一些边，问有多少种选法使得割掉任意一条未选中的边后选择了的点仍然联通，对 $10^{9} + 7$ 取模。 $n \leq 5 \times 10^{5}$ ， $m \leq 10^{6}$ 。

只割一条边，那么说明在一个强连通分量里面的是不会不连通的，那么缩点就一定是必要的。

无向图缩点过后会变成一棵树，现在每个点会有一个点权，如果选择他会乘上 $2^{s z} - 1$ ，要求选择点和边使得点联通（点不连通的话显然会被割掉）。强连通分量里面的边选不选都没有影响，可以最后乘。

剩下就是一个树形 DP 的过程了，方法比较多，就说一下我的 DP 办法。记 $f 1_{x}$ 表示在 $x$ 子树内部选择一些点和边（不能不选点），他们的 $lca$ 在 $x$ 并且联通的方案数， $f 2_{x}$ 表示 $x$ 子树内部选择一些点和边（不能不选点），他们和 $x$ 联通的方案数。注意定义的区别。

我们计算的时候假设 $f 2$ 是可以内部不选点的，新来了一棵子树 $v$ ， $f 2$ 是好更新的，如果内部有点，那么就乘 $f 2_{v}$ ，否则就是 $v$ 子树内部和 $(x, v)$ 共 $s z_{v}$ 条边都可以选择，是 $2^{s z_{v}}$ 。 $f 1$ 有两种更新方式，一种是从 $f 1_{x}$ 来，另一种是从 $f 2_{x}$ 和 $f 2_{v}$ 来。注意这个时候不能算重了， $f 2_{x}$ 需要去掉什么点都没选的情况和 $lca$ 已经在 $x$ 的情况。最后更新完所有子树过后， $f 2_{x}$ 再减去内部不选点的情况。更新答案的时候直接使用 $f 1_{x}$ 然后外部的边任意选即可。

具体实现可以到 https://loj.ac/s/1659416 看。

T4

题意：给定两个长度为 $n$ 的序列 $a$ 和 $b$ ，定义一个区间 $[l, r]$ 的权值为 $({max}_{i = l}^{r} a_{i}) \times ({max}_{i = l}^{r} b_{i})$ 。 $q$ 次给定一段区间，问这段区间的所有子区间的权值和，对 $2^{64}$ 取模。 $n, q \leq 2.5 \times 10^{5}$ 。

最值分治之类的可以过掉大部分随机的数据点，但显然正解不是这个。

考虑直接扫描线 + 线段树大力做。现在我们对左端点扫描线，对右端点记录历史和，这样的话查询的时候只要在对应左端点的时间查询区间内部的历史和即可。

单调栈可以动态维护每个节点的 $a$ 和 $b$ 的 $max$ ，那么现在扔给线段树的问题就是：

区间 $a$ 加一个数
区间 $b$ 加一个数
区间内部每个位置 $c$ 加上当前位置的 $a \times b$

改题的时候比较偷懒，就使用的是矩阵维护，具体来说，需要维护区间长度，区间 $a$ 和，区间 $b$ 和，当前区间 $a \times b$ 和，历史区间 $a \times b$ 和 5 个变量。3 种操作都是好用矩阵维护的，不过比较卡常，可能需要一定技巧才能通过，具体可以看 https://loj.ac/s/1659366。