NOI2024 赛前训练记录(2) - IPS99技术分享

标签：赛前 log 训练复杂度位置 NOI2024 区间考虑 dp

5.1

P9662

首先可以设 $dp_{i,j}$ 表示考虑了前 $i$ 个数，当前在开头位置的是原来排第 $j$ 的数的答案。转移如果 $j$ 仍然合法，那么只需要转移到 $dp_{i+1,j}$。否则要转移到 $i+1$ 这个数在 $1$ 或者 $m$ 位置的情况。时间复杂度 $O(n^2)$。

考虑优化这个东西，发现转移除了不动就会转移到下一个数在 $1$ 或者 $m$，所以可以设 $dp_{i,0/1}$ 表示前 $i$ 个，当前 $i$ 在 $1$ 还是 $m$ 的答案。转移去找到下一个不是不动的转移，暴力去找的话时间复杂度 $O(n^2)$，用主席树二分优化就能做到 $O(n\log n)$。但是空间限制 $256M$，所以需要离线下来用线段树二分解决。时间复杂度 $O(n\log n)$，空间复杂度 $O(n)$。

qoj1084

首先考虑容斥，钦定 $i$ 个位置满足条件的容斥系数是 $(-1)^i$。设 $dp_{i,j,0/1}$ 表示上一次钦定在 $i$ 位置，相等的值是 $j$，钦定了奇数/偶数个位置的方案数。

考虑一个从 $dp_{a,b}$ 向 $dp_{c,d}$ 的转移，考虑 $[a+1,c]$ 这一段能填什么，必须有 $b,d$ 并且在 $[b,d]$ 之间，所以这个系数就是 $(d-b+1)^{c-a}-2(d-b)^{c-a}+(d-b-1)^{c-a}$。暴力转移即可做到 $O(n^2V^2)$。

考虑把转移系数的几项拆开计算，然后就是一个 $(d-b)^{c-a}$ 的形式，可以枚举 $b,d$，然后记录 $dp_{a,b}(d-b)^{-a}$ 的前缀和，加进答案的时候乘上 $(d-b)^c$ 即可。这样就能用前缀和优化到 $O(nV^2)$。

答案是关于 $k$ 的 $n$ 次多项式，拉格朗日插值就可以只考虑值域为 $n$ 的情况，时间复杂度 $O(n^3)$。也可以用组合数容斥来压缩值域。

CF1728F

好题。将 $b_i$ 互不相同这个条件转化为二分图匹配。对于每个 $a_i$ 建立左部点 $a_i...na_i$，与右部点 $i$ 连边，左部点与 $s$ 连边有边权，答案就是二分图最小费用最大匹配。

暴力的复杂度是 $O(n^5)$ 的，显然过不去。考虑每次增广从 $t$ 开始 dfs，找到能到达 $t$ 的左部点，这些都是没有费用的。然后代价从小到大枚举左部点，判断这个左部点是否与 $t$ 联通，如果联通就增广过去，然后反转这条路径上边的可用性。每次 dfs 的复杂度是 $O(n^2)$ 的，一共进行 $O(n)$ 次增广，总复杂度 $O(n^3)$。

当图大部分都没有费用的时候，可以用 bfs 来代替 spfa 进行找增广路减少复杂度。

5.11

AGC041F

神仙 AGC F。对于这个结构，每次找到最小的位置，然后下面的一块处理之后劈成两半，这两半就是独立的了。所以说可以套路的考虑笛卡尔树。

考虑选择一些列有棋子（其他列没有棋子），那么对于被划分出来的一块，如果有选出来没有棋子的列，那么每一行必须都有一个棋子。所以设 $dp_{u,i}$ 表示笛卡尔树上第 $u$ 个节点有 $i$ 个选择有棋子的列，转移树形背包，然后去选择当前这一列有没有棋子，如果当前有没有棋子的列，当前行必须选择，那么转移系数是 $2^i-1$，否则是 $2^i$。交上去可以获得一发罚时。

刚才的做法错误的原因在于，我们并不能保证所有有棋子的列在转移之后真的有了棋子。所以还需要再容斥一次。除了选择有棋子的列为 $S$ 以外，去钦定 $T$ 表示被选择应该有棋子，但是实际上没有棋子的列，容斥系数为 $(-1)^{|T|}$。转移的时候看起来需要记录 $S$ 中的个数，$T$ 中的个数，复杂度 $O(n^4)$。但是发现其实只需要记录 $|S|-|T|$，这个是转移系数上指数上的东西。另外记录一个 $0/1$ 表示是否需要 $-1$，就是是否有不在 $S$ 中的即可。复杂度 $O(n^2)$。

5.15

CF1616H

把所有数插到 trie 树上，在 trie 树上 dp。设 $f_u$ 表示在 $u$ 子树里面选点的方案数。如果这一位是 $0$，那么不能同时选两个子树内的，所以两边是独立的，各自求出来然后加起来就行了。如果这一位是 $1$，发现两边之间有限制，各自内部没有限制，所以需要改写 dp 数组为 $g_{x,y}$ 表示在 $x$ 子树内和 $y$ 子树内都选择的方案数。

虽然这个看起来很不靠谱，但是考虑一下这个递归过程，发现每个节点同时只会和一个点相互限制。所以每个点只会被考虑到一次，所以复杂度是对的。注意讨论一下有一边为空的情况。复杂度 $O(n\log n)$。

CF1515H

其实是比较套路的，但是一直在想一些错误做法，很快把正确做法否掉了。

首先如果只有 3 4 操作，并且 3 操作对于全局的，那就维护一棵 trie 树，每次就是交换左右儿子，然后打标记下传即可。如果 3 操作不是全局的，有些不好处理，因为交换左右子树之后可能会和一些本来存在的部分合并，所以考虑类似于线段树分裂和合并的操作。每次把需要修改的部分线段树分裂出来，每次分裂只会新增 $O(\log n)$ 个节点。然后对分裂出来的部分打个标记，然后合并回去，每次有效的合并都会用 $O(\log n)$ 的复杂度减少一个节点，所以总的复杂度就是 $O(n\log^2 n)$。

考虑加入 $1,2$ 操作，发现 $1$ 操作能够简单转化为 $2$ 操作和 $3$ 操作，所以只需要考虑 $2$ 操作，其实做法是一样的，这样可以少写一个函数。对于 $2$ 操作，对于两个子树只有一个有的情况，可以直接进行交换或者不操作。如果两个子树都有，就把左子树给右子树，这里可以直接暴力递归，因为每次这种操作会减少一个 trie 树上的节点。但是这里需要注意，如果子树内都只有两个子树只有一个的情况，那么这里就要打标记停止递归，这样才能保证复杂度。两个标记之间的合并手玩一下是容易操作的，复杂度 $O(n\log^2 n)$。

CF1268E

首先对于树的情况，有一个简单点分治做法，但是它并没有什么优化前途。需要考虑一些其他树的做法，从大到小扫边，每次合并两块，设 $f_u$ 表示 $u$ 能到达的点数量，每次合并一条边 $(u,v)$，发现把每一个点对在边权最小的边的位置计算的话，操作就是简单的 $f_u'=f_v'=f_u+f_v$。时间复杂度 $O(n+m)$。

对于仙人掌的情况，套用过来之后，如果合并的边 $(u,v)$ 是环边，那么会有一些点对会被重复计算。考虑这个环的最大的边，如果这个环是满足单峰单谷的，那么对于通过最大边的点对，这些点原本就 $u,v$ 都能到，这次还会被合并，会计算重复，减掉算重的部分就行了。复杂度 $O(n+m)$。

5.20

40+100+16=156

不会计算几何。

A

这个题本来是有大样例的，可是为什么我没有见到呢？

首先 $O(n^2)$ 的做法就是暴力 check 由于一个碗的限制另一个碗的最低高度是多少。分别 check 一下底对底，底对腰，腰对腰的限制即可。

考虑优化，发现很多是不会有限制的，用一个栈维护当前可能有限制的，栈中从中间变得靠边，碗最高高度从低到高。每次判断两个之间的限制之后，如果使得当前高度变得更高就要弹出造成限制的这一个。如果不能使得当前高度变得更高那么后面的也不会造成限制。复杂度 $O(n)$。

B

设 $dp_{i,j}$ 表示两个序列分别删到 $i,j$ 的方案数，转移枚举下一个删哪一边。但是发现这个很显然会算重，因为对于不同的操作序列可能得到相同的 $c$ 序列。那么考虑什么时候会算重，初始的时候如果 $a_1=b_1$ 就会算重，然后如果当前一共删去 $i$ 个，第一个序列删去 $j$ 个和 $k$ 个会算重，由于是个排列，可以归纳得出，一个 $c$ 序列对应第一个序列删除的长度不超过两种。

所以可以设 $dp_{i,j,k}$ 表示一共删去 $i$ 个，第一个序列删去 $j$ 个和 $k$ 个对应相同 $c$ 序列个数，复杂度 $O(n^3)$。毛估估一下状态数大概是 $O(n^2)$ 的，记录一下有效状态就能通过。

C

太困难了。

5.21

100+25+25=150

A

可以用若干次在线二维数点求出分出来的一块的答案，用主席树可以在线维护。设 $dp_i$ 表示上一次划分在 $i$ 的答案，转移具有决策单调性，可以二分栈优化。复杂度 $O(n\log^2 n)$。

B

大概看懂了。但是太难写了，狗都不补。

考虑对于每个子串求出合法的 $a$，首先把原来的方程转化一下，除了中心位置之外，其余位置可以通过对差分数组进行归纳，转化为 $s_j-as_i=s_{j-1}-as_{i+1}$。

注意到，如果 $[1,n]$ 是 $(p,q)$ 好的，$[l,r]$ 是 $(a,b)$ 好的，$[n-r+1,n-l+1]$ 就是 $(a,b')$ 好的。可以通过一系列代数变形得到 $s_{n-r+1}=as_{n-l+1}+c$，其中 $c$ 是用 $a,b,p,q$ 表示的常数，题解里面有写，不再细说。

发现这个形式类似于 manacher 的过程，所以类似 manacher 求出每个可能合法的子串 $a$ 需要满足的同余方程。如果可以就从前面继承过来，注意继承的时候要弹掉不在区间内的。然后暴力每次加入一个方程，进行同余方程的合并，可以用 EXCRT 实现直到无法合并。由于每次合并模数至少会变成两倍，所以对于每个中心至多有 $O(\log p)$ 个不同的同余方程。维护每个同余方程满足的形式 $a\equiv w(\bmod x)$ 和这个方程出现的长度。对于每个位置是 $O(\log p)$ 的。合并方程至多会进行 $O(n)$ 次，所以这一部分的复杂度就是 $O(\log p)$ 的。

对于每个同余方程，它的模数 $x$ 必然是 $p$ 的因子，所以对于每个模数 $x$，用哈希表维护每个 $w$ 对答案的贡献。第一类查询的时候枚举 $p$ 的每个因子，查询在哈希表里面对应 $x\bmod p$ 位置有多少个合法，复杂度 $O(qd(p))$。

对于第二类查询，从第一类查询的同余方程和中心位置的初始方程可以推出一个 $b$ 需要满足的同余方程，同样用哈希表维护，复杂度 $O(n\log p+qd(p))$。

C

对于 $k=-1$ 的情况，考虑 $i^{i-1}$ 的组合意义，是 $i$ 个节点的有标号有根树计数。建立超级根节点 $0$，那么要求 $0$ 在 prufer 序列的出现次数必须是 $m-1$。剩余部分的 prufer 序列随便，这部分答案是 $\binom{n-1}{m-1}n^{n-m}$。同时需要钦定这 $m$ 个树在原序列中的顺序，所以答案就是 $\binom{n-1}{m-1}n^{n-m}m!$。

剩下的部分过于逆天了。

gym102354B

看到 $\gcd$ 需要想莫反啊，感觉这种题还是做少了。

想了一个魔怔折半发现折不动，两边都有一万多。考虑莫反，虽然 $\max$ 的条件很不能莫反，但是可以二分，转化为求 $|a_i-b_j|\geq mid$ 的 $(i,j)$ 个数，这样就可以莫反了。枚举 $d$，然后常规莫反，得到 $\sum_{k=1}^{\frac{n}{d}}\mu(i)\sum_{i=1}^{\frac{n}{kd}}\sum_{j=1}^{\frac{n}{kd}}[|a_{ikd}-b_{jkd}|\geq mid]$。对于后半部分，枚举 $kd$ 双指针预处理，复杂度 $O(n\log^2 n)$，枚举 $d$ 二分莫反的复杂度是 $O(n\log n\log V)$，可以通过。

qoj1432

简单题，假设 $x\geq y$，那么最小的最长连续段长度为 $\frac{x+y}{y+1}$。枚举最长连续段长度之后容易 $O(n^2)$ dp。复杂度 $O(n^3)$。

但是 dp 两维中较小的那一维大小不会超过 $O(\frac{n}{d})$，所以复杂度是 $O(n^2\log n)$ 的。有点卡空间，最好离线一下。

CF1149D

观察一些性质。如果两个点能够只通过 $a$ 边联通，那么在这两个点路径上的任意两个点的 $b$ 边都不会出现在最小生成树上。

另一个性质是，只保留 $a$ 边将原图划分为若干联通块，那么在最小生成树上的边一定不会从一个联通块出去又进来，根据上一个性质容易说明这个是必要的。

我们猜想满足这两个条件的 $1$ 到 $i$ 距离最短的边一定在最小生成树上。这个是对的。所以设 $dp_{s,i}$ 表示当前走过了 $s$ 的联通块，到达 $i$ 的最短路。用 dijkstra 进行 dp 转移，同时判断条件是否合法。复杂度 $O(2^nnm)$。

发现另一个性质。大小 $\leq 3$ 的联通块不需要被考虑，因为一进一出需要两条 $b$，内部走至多需要两条 $a$，所以不需要限制就不会出现不满足上面性质的情况。只考虑大小 $\geq 4$ 的联通块，复杂度 $O(2^{\frac{n}{4}}nm)$。

5.22

100+100+40=240

A

看到每次保留峰值位置，考虑笛卡尔树上 dp。设 $dp_{i,j,0/1}$ 表示一个长度为 $i$ 的排列，用 $j$ 次就能够删完，两边是否有一边没有东西的方案数。注意这里状态应该设为删完而不是剩下一个峰值位置，否则不好进行转移。

考虑这个 dp 的转移，枚举峰值位置，剩下两边的大小如果是如果两边需要删完的次数是 $i,j$，两边都有东西，那么新的需要次数为 $\max(i,j)+[i==j]$，如果有一边没有东西，设为 $i$ 这边，那么新的需要次数是 $\max(i,j+1)$。前缀和优化转移，复杂度 $O(n^3)$。

注意到这个转移形式，$m$ 的大小不会超过 $O(\log n)$，否则无解，复杂度 $O(n^2\log n)$。

B

把表达式树建出来，不难发现每个子树内部最后的值是一段区间 $[l,r]$。两个子树向上合并的时候容易讨论出来两个区间合并之后的结果，复杂度 $O(n)$。

C

神秘 AGC 题。首先观察到 $n=\frac{S-1}{2}$。因为显然选择后面的 $\frac{S-1}{2}$ 个元素是合法的，并且 $i$ 和 $n-i$ 只能选择一个，所以 $n=\frac{S-1}{2}$ 是充要的。

然后再观察性质，如果 $a,b\in A,a+b<S$，那么 $a+b\in A$。否则的话 $S-a-b\in A$，与 $a,b$ 就能组合出来 $S$，与条件矛盾。

考虑贪心，从小到大考虑每个数尝试加入 $A$，如果能够加入就加入，正确性显然。那么对于 $k=1$ 的情况，答案就是第一个不是 $S$ 因子的数，设为 $m$，可以观察到 $m\leq 43$。

因为 $m$ 很小，所以考虑一些和 $m$ 有关的做法，判断一些数的线性组合是否能得到 $S$ 容易想到同余最短路，同余最短路的点数是 $O(m)$ 的。考虑加入点的过程，维护 $f_i$ 表示当前能到达的最小的 $x\bmod m=i$ 的 $x$，我们只需要考虑加入主动加入的点，不需要考虑因为第二条性质被动加入的点。主动加入的点对于每个 $i$ 显然至多会有一个点，所以加入的点数量是 $O(m)$ 的。每次加入的时候暴力去更新所有同余最短路，复杂度 $O(m^2)$，所以这一部分的复杂度是 $O(m^3)$，下面需要考虑怎么找到这 $O(m)$ 个点。

显然每次需要找到的是最小的加入它合法的点。对于一个 $i$ 考虑求出最小的 $x\bmod m=i$ 的 $x$ 能加入，假设这个为 $qm+i$，那么需要满足 $j(qm+i)+f_{(S-ij)\bmod m}>S$ 对于任意 $j\in [1,m-1]$ 成立，因为 $j\geq m$ 的情况可以用 $j\in [1,m-1]$ 的情况表示，暴力 check 一下最小的合法的 $j$ 即可。

然后查询答案的时候，因为不能构造出整个序列，所以考虑二分答案，求出在 $x$ 以下的点有多少，枚举 $i$ 计算出来余数为 $i$ 的时候的 $x$ 以下点个数即可。复杂度 $O(T(m^3+m\log S))$。

CF799F

随机化，会不了一点。乱搞，会不了一点。

感觉不应该去跟着题解走随机化的，我一开始的扫描线思路完善一下再调一车细节就对了。考虑扫描线 $r$ 这一维，维护 $l$ 这一维的合法性。同时维护合法的 $l$ 个数和合法的 $\sum (l-1)$，这样就能计算答案了。

考虑神秘的条件对合法性的限制，首先这个奇偶性肯定要分两棵线段树维护下标为奇偶的位置的答案。第一个限制看起来就没啥用，对于一个 $r$，它只能限制 $l$ 必须在一段前缀里面选择，可以简单求出。下面只考虑第二条限制给的约束。

设 $x$ 为扫描线的右端点。对于 $x\in [l,r]$ 的区间，如果 $x$ 和 $l$ 奇偶性不同，那么 $[1,l-1]$ 都不合法，并且在 $[l,x]$ 区间内和 $l$ 奇偶性相同的位置也不合法。找到这种区间里面 $l$ 最大的一个约束条件是最强的，在线段树上处理一下。对于 $x$ 和 $l$ 奇偶性相同的区间，对于 $[1,l-1]$ 没有限制，对于 $[l,x]$ 区间内和 $l$ 奇偶性相同的位置不合法。找到 $l$ 最小的约束条件最强，线段树上维护。

还有 $r<x$ 的区间需要考虑。这些区间内部有一些位置是不合法的，并且如果区间长度是偶数，那么 $[1,l-1]$ 都不合法，在线段树上修改。注意到这种修改是有后效性的，但是前一种只对于当前的 $x$ 存在，需要用完删除影响。时间复杂度 $O(n\log n)$。

qoj1263

过于神秘了。观察性质，将一个对 $(a,b)$ 考虑为在一个初始为 $1\sim n$ 的排列上交换值 $a$ 和值 $b$。那么每次交换的必须是没有交换过的在排列上相邻的位置。考虑归纳证明，对于 $n=3$ 显然成立。对于 $n>3$ 的情况，把每组 $a<b<c$ 拉出来考虑，都需要满足 $n=3$ 的限制，所以整个全局也需要满足这个性质。

有了这个非常人类智慧的性质之后，发现最后的结果一定是 $n\sim 1$ 的排列，将排列计入状态，每次能交换的就是相邻两个 $a<b$ 的数。并且不能同时满足 $a_i$ 在 $b_i$ 以前，$c_i$ 在 $d_i$ 以后，复杂度 $O(n!(n+m))$。

qoj1833

首先有一个简单的 $O(n^3)$ dp，设 $dp_{i,j}$ 表示将 $[i,j]$ 这段区间合并需要的最小最大值。转移枚举一个中间点 $k$ 合并 $[i,k]$ 和 $[k+1,j]$ 两段区间，或者合并 $(i,j)$ 这两个点。复杂度 $O(n^3)$。

发现需要求的是最小化最大值而不是最小化和，所以可以二分答案，然后记录 $dp_{i,j}$ 表示是否可以把 $[i,j]$ 删空，用 bitset 优化 dp。复杂度 $O(\frac{n^3\log n}{w})$，大概率还是过不去。

考虑继续优化这个过程，二分不是必要的，考虑从小到大扫权值，每次加入一个合法的点对 $(i,j)$，会导致一些 dp 值从 $0$ 变成 $1$，设法尽可能快速维护出这些变化的位置，因为只有 $O(n^2)$ 处，所以复杂度是对的。

用 bitset 来维护，每次有一个 $dp_{i,j}$ 从 $0$ 变成 $1$ 的时候，考虑它会带来的变化。一种是会改变 $dp_{i-1,j+1}$，这个容易 $O(n^2)$ 维护。另一种是左边或者右边拼上一段，以左边为例，需要找到右端点为 $j$ 不合法，右端点为 $i-1$ 合法的左端点集合，并且改变这个集合里面 dp 值。这个可以用 bitset 方便的维护，找到所有需要改变的值用 _Find_next() 函数维护即可。复杂度 $O(\frac{n^3}{w})$。

5.23

0+两个省集原题。

A

傻波 128M。傻波 128M。

先求出最大答案，然后最大化能够节省的代价。

每次选择的一定是一对叶子，考虑设 $f_u$ 表示 $u$ 子树里面选择了一个叶子，子树内部边上的第一类贡献和子树内部的第二类贡献的最大值。在 LCA 处合并答案。

考虑 $f_u$ 的转移，选择一个叶子 $f_v$ 转移，那么贡献有 $(u,v)$ 这条边的贡献，可以 $O(1)$ 计算。和其他子树内部的第二类贡献和以及其他子树之间的第二类贡献，预处理所有的和减去这棵子树即可，有一些细节，但是不是很麻烦。

考虑在 LCA 处的合并。设 $sum_u$ 表示 $u$ 子树里面的和，那么如果选择两个儿子 $v_1,v_2$ 合并，分别减去两个儿子对应的第二类贡献之后，算重的部分是 $sum_{v_1}sum_{v_2}$，用李超树维护即可。复杂度 $O(n\log n)$。

B.C

山东二轮省集 Day1 T2T3

CF1530H

首先考虑时间倒流，任意时刻填完的是一个区间。考虑 dp，设 $f_{i,j,k}$ 表示当前填了 $i$ 个数，区间长度为 $j$，LIS 长度为 $k$ 对应 LIS 序列中最大值最小是多少，$g_{i,j,k}$ 记录最小值最大是多少，转移枚举下一个填入序列的数，分它加入 LIS 和不加入 LIS 分别转移，复杂度大概是 $O(n^4)$。

观察性质，发现 $a_n$ 一定会被选入序列中，对于其他的，如果它不选入 LIS，可以通过不动这种操作使得它也不在最终序列中出现。所以分 $a_n$ 是否在序列中讨论，就可以不记录 $j$ 这一维，复杂度 $O(n^3)$。

另一个性质是排列是随机的，对于随机排列，它的 LIS 长度是 $O(\sqrt n)$ 级别，所以 $k$ 这一维只需要记录到 $O(\sqrt n)$ 级别，复杂度 $O(n^2\sqrt n)$。

状态已经不太好优化了，考虑优化转移。发现 $f$ 对 $f$，$f$ 对 $g$，$g$ 对 $f$，$g$ 对 $g$ 的转移在 $k$ 这一维一定是转移到 $k+1$，另一维是一个二维偏序的形式，用树状数组维护前缀 $\max$ 就能做到 $O(\log n)$ 转移，复杂度 $O(n\sqrt n\log n)$。

P4184

之前做过了。

每一行的合法位置是一段区间 $[l,r]$，并且 $l,r$ 都单调，扫描线一个上边界，维护每一个下边界的区间和这个上边界的交即可，这个是好做的。复杂度 $O(n)$。

梦熊 R16 A

感觉这场码量很大啊，三个题都不是啥好写好调的东西。

首先发现单点修改就是假的，因为能到达的范围是一段区间 $[l,r]$，这一部分就是单点修改区间求最大值，线段树维护即可。

考虑怎么求出 $[l,r]$ 的范围，以 $l$ 为例说明。考虑倒着扫操作序列，每次如果碰到一个包含 $l$ 的区间，那么把 $l$ 更新为当前区间左端点。考虑快速维护这个东西。

对于跳 $l$ 之后，下一次跳到的区间是确定的，可以用线段树维护。那么如果找到跳到的第一个区间之后，就可以倍增跳 $l$ 跳到最后一个在询问操作序列区间范围内的操作。找到第一个区间也可以线段树维护，复杂度 $O(n\log n)$，注意卡常。

梦熊 R16 B

太厉害了这个题。首先可以考虑怎么 check 合法性，设 $dp_{i,j}$ 表示前 $i$ 个，子序列最后一个是 $j$ 能带来的最大长度，转移 $dp_{i,a_i}=\max_{j\in[a_i-k,a_i+k]} dp_{i-1,j}+1$。其他位置不变。用线段树优化转移做到 $O(n\log n)$。

先对前面的部分跑这个 dp，设辅助数组 $f_{i,j}=\max_{p\in [j-k,j+k]}dp_{i,p}$，那么在后面新加一个 $a_i$ 对应在 $f$ 上的转移是 $f_{i,j}=\max(f_{i-1,j},f_{i-1,a_i}+1)$。所以每次的贪心策略就比较显然了，每次找到 $f$ 最小的位置添加在序列后面。考虑如何维护这个东西。

设 $f$ 的最小值位置集合为 $S$，那么 $S$ 一定构成若干段区间 $[l_i,r_i]$，我们要用最多的步数使得这些区间内每一个 $+1$。我们可以发现 $r_i+2k< l_{i+1}$，因为每一次修改操作的赋值范围是 $2k+1$，所以一段连续的不是最小值的位置长度一定 $\geq 2k+1$。有了这个结论，每个区间就独立了，它的贡献就是 $\lceil \frac{r_i-l_i+1}{k+1} \rceil$，每次加入区间开头位置即可。

扫描线一遍，动态维护最小值位置区间即可，用 ODT 维护。正着扫倒着扫都行，倒着扫好写一点。复杂度 $O(n\log n)$。

梦熊 R16 C

首先可以断环为链，复制两边之后区间 dp，设 $f_{i,j}$ 表示在 $i,j$ 联通的情况下把 $[i,j]$ 连成一个联通块的代价，$g_{i,j}$ 表示 $[i,j]$ 构成联通块的代价。$f$ 的转移枚举一个位置和 $i$ 或 $j$ 连边，$g$ 的转移要么从对应你的 $f$ 转移过来，要么枚举一个中间点拼起来，复杂度 $O(n^3)$。

预处理完这些东西之后就可以 dp 了，选择若干段，每一段选出来一个点和中心连边，复杂度大概 $O(qn^2)$，我大概只会这些东西。

考虑观察一些性质，减少 $q$ 上的复杂度。注意到，选择的区间段数不超过 $2$。因为如果有两段选择的和 $h_0$ 大小关系相同，那么它们连边之后肯定不会变劣。对于选择一段，$h_0>h$ 的情况，可以预处理出来每一段选择每一个点连边的情况，可以贡献到一段 $h_0$ 的后缀。$h_0<h$ 的情况贡献到一段前缀。选择两段的情况需要额外处理辅助数组 $dp_{i,j}=\min_k dp_{i,k}+dp_{k+1,j}$，然后枚举两个向中心连边的点和边界之后也可以预处理出来。查询只需要离散化后二分位置即可，复杂度 $O(n^3+q\log n)$。

5.24

100+100+10=210

dwt 拜谢。dwt 拜谢。

A

简单题，但是 std 过不去现在给的操作次数上界，怎么会是呢。

发现操作次数的级别是 $O(n\log n)$。考虑分治。把 $1\sim \frac{n}{2}$ 的元素放在后面，然后再把 $\frac{n}{2}+1\sim n$ 的元素放在前面。这样的话会先操作前面的部分，然后用一次长度为 $n$ 的操作交换前后，然后操作后面的部分。两部分递归处理即可。操作次数级别 $O(n\log n)$。

B

原题 qoj4887。

因为管道的收益只有 $1$，所以显然没有必要去绕路来获得管道收益，这样一定是不优秀的。考虑先求出来不使用管道的代价，再减去通过管道能减少的代价即可。

只处理左下到右上的情况，左上到右下是类似的。离散化，预处理出来 $dp_{i,j}$ 表示从第 $i$ 个管道开始到达第 $j$ 个管道最多能经过多少个管道。然后枚举左边界，扫描线右边界的过程中维护一个二维矩形的信息表示上下边界分别为 $l,r$ 的时候的收益。扫描线遇到新的管道的时候考虑以它为终点能够造成的最大收益，是 $O(n)$ 个下边界对应的一段上边界对 $x$ 取 $\max$。随便找个数据结构维护一下就能做到 $O(n^3\log n)$。但是出题人并没给这档分。但是因为数据是随机的，所以这个做法可以直接通过。

考虑另一个做法。预处理 $dp$ 数组之后预处理 $f_{a,b,i}$ 表示从 $(a,b)$ 这个节点开始到达 $i$ 这个管道的最大管道数。转移大概从 $f_{a+1,b,i},f_{a,b+1,i}$ 转移，还可以枚举一个起点在这个位置的矩形 $k$ 从 $dp_{k,i}$ 转移。可以滚动数组做到空间 $O(n^2)$。对于每一个 $(a,b)$，去处理以它为起点的收益。考虑处理出有多少终点满足 $f_{a,b,i}\geq t$，将这些拿出来之后需要处理一个 2-side 的二维数点，可以做到 $O(矩形个数)$。这里注意到 $t-1$ 对应的范围一定是包含 $t$ 对应的范围的，所以只需要处理 $f_{a,b,i}=t$ 的位置即可。由于每个起点矩形个数是 $O(n)$ 的，总复杂度就是 $O(n^3)$ 的。

C

纯纯一个给波特做的题。所以 ysy 是不是波特呢。

首先考虑如果确定 $w,b$ 怎么做，不妨假设 $w\geq b$。设 $S$ 表示所有 $w$ 个点的联通块的公共点集合。一个点在 $S$ 中当且仅当这个点的所有子树大小都 $<w$。如果 $S$ 非空，那么答案就是把 $S$ 中点删去，剩下的联通块中大小 $\geq b$ 的个数。这些状态白点都不能出来，所以它们都本质不同。

如果 $S$ 为空。如果能找到一个点它有两个大小 $\geq w$ 的子树和一个大小 $\geq b$ 的子树，那么所有状态本质相同，因为必然可以通过移动将所有白点放在哪个大小 $\geq b$ 的子树里，把黑点放到其中一个大小 $\geq w$ 的子树里。反之，由于 $S$ 没有公共点，那么必然存在两个大小 $\geq w$ 的联通块无交。此时答案是 $2$，两种本质不同的状态分别是把黑点放在两个不同联通块里。

考虑统计答案，首先对于 $S$ 不为空的情况，枚举每个点在 $S$ 中的情况，它的一个相邻点不在 $S$ 中，这里对应的 $w$ 是一段区间，找到相邻点的 $siz$ 之后 $b$ 也是一段区间，可以 $O(n)$ 处理。

对于 $S$ 为空的情况，枚举 $w$，可以预处理出来每个 $w$ 对应的 $b$ 的范围分别对应 $1$ 个答案或者 $2$ 个，也可以 $O(n)$ 处理。注意不要写递归函数，复杂度 $O(n)$。

5.25

CF833E

好题。离散化之后先求出来在每个时刻之前最多能产生多少个时刻有阳光。然后二分答案即可。

考虑怎么求，离散化，如果这一段时间没被区间覆盖，那么一定能产生贡献。如果被超过两个区间覆盖，肯定不会产生贡献。所以只需要考虑被一个区间或者两个区间覆盖的段。记录 $f_i$ 表示当前位置以前只被 $i$ 区间覆盖的段长度，如果删掉一个区间或者两个不相交的区间，贡献用 $f_i$ 表示。如果删掉两个相交的区间，还需要记录 $h_{i,j}$ 表示同时被 $i,j$ 覆盖的长度，记录辅助数组 $g_i=\max f_j+h_{i,j}$。显然 $h_{i,j}$ 只有 $O(n)$ 个位置有值。

如果当前被一段覆盖，那么更新 $f_i$，从 $f_i$ 更新答案。如果是两个不相交，这个是后一个，那么用一个线段树维护一下前缀最大值。如果两个相交从 $f_i+g_i$ 更新答案。

如果当前被两段覆盖，就从 $h_{i,j}+f_i+f_j$ 更新答案，同时更新 $g_i$ 和 $g_j$。这种处理如果更新完 $h_{i,j}$ 之后先后更新了 $f_i$ 和 $f_j$ 就会算错，因为 $g_j$ 没有随之更新，但是手玩一下就会发现这种情况显然不会出现。所以这样就对了，复杂度 $O(n\log n)$。

5.26

100+100+30=230

A

想了 2h 线段树分治状物，发现不是被卡常了，是复杂度完全假掉的。

建出一棵随机的 dfs 树，对每个节点用线段树维护返祖边能指向的深度集合，一路线段树合并上去即可。这部分复杂度为 $O(n\log n)$。然后去考虑每条边能不能删去。

如果这条边是树边，设为 $u,v$，需要 $u$ 除了 $v$ 以外的子树都能到 $u$ 以上，$v$ 的所有子树都能到 $u$ 以上，线段树预处理一下并查询一下即可。

如果这条边是非树边，是类似的，注意这里要分别判断 $v$ 以下的部分能不能到达 $u,v$ 之间的一段和 $u$ 以上的部分，和 $u,v$ 之间的部分能不能到达 $u$ 以上的部分，后者差分，前者因为 dfs 树随机所以期望次数也是 $O(n)$ 的。总的期望复杂度就是 $O(n\log n)$。

B

二轮省集 Day5T1

C

赛时其实考虑的差不多了，但是有一个东西处理不了。

建出正反串 AC 自动机，设 $dp_{i,l,r,t}$ 表示当前从两边到中间填了 $i$ 个，两个 AC 自动机上匹配到 $l,r$，成功匹配了 $t$ 次的方案数。复杂度 $O(nm^2)$。

但是这个 dp 不能处理从中间拼上的情况，我赛时就不会这个。枚举一个位置和一个串，考虑能拼上就要求两边的 $l,r$ 都在 fail 树的一个子树里面。但是这样会算重，所以直接先做这个 dp，然后再判断 $t=1$ 的情况能不能造成贡献。用二维差分二维前缀和预处理出来能造成贡献的位置，然后单点查询即可，奇偶需要一些不同的分类讨论。

有效状态只有 $O(nlm)$，可以通过。

5.27

CF1034D

首先求出这个第 $k$ 大的值。二分答案，然后 check。对于每个 $r$，合法的 $l$ 是一段区间并且左端点递增。所以可以双指针扫过去，问题在于快速求出一段区间并的大小。扫描线 $r$，用一个 ODT 来处理每一个位置对应的最大左端点，同时用一个 BIT 处理每个左端点对应的位置个数。就可以做到 $O(n\log n)$ 扫一遍并且计算答案 $\geq mid$ 的区间个数有多少。

得到这个之后就能得到每一个右端点对应的左端点范围。扫描线右端点，用两个 BIT 分别维护每个左端点对应的位置个数，和它乘上左端点的值。查询对于 $l$ 以后的位置在第一个 BIT 上查询，以前的在第二个 BIT 上查询。这部分 $O(n\log n)$。总复杂度 $O(n\log^2 n)$。

考虑优化复杂度。首先 ODT 的部分可以放在二分外面，能减小很多常数。然后发现扫描线的部分，是单点修改查询区间和。查询的区间左右端点都递增。可以单点修改就直接修改，如果在区间内就修改和的答案。然后加入一个点或者删除一个点的值，可以做到 $O(n)$。总复杂度 $O(n\log n)$。

qoj7412

简单题。首先求出来 $val_s$ 表示 $s$ 集合形成一个环的方案数，容易做到 $O(2^nn^3)$。

然后由于是边仙人掌，一个点是可以在很多环中的。考虑处理这部分，枚举一个点，然后合并两个环，这里细节需要处理一下，注意别算重算漏答案。复杂度容易做到 $O(3^nn)$。

然后就是把一堆环连成一棵树形结构，枚举一条边然后枚举子集合并。复杂度 $O(3^nn^2)$。

loj510

神题。首先对于 $n\leq 2\times 10^5$ 的部分，可以将 $x$ 连一条边到 $x+lowbit(x)$，形成一个森林的结构。然后修改就是将一个点到根的链异或一个数，查询 $O(\log n)$ 次单点值，可以用 BIT 做到 $O(n\log^2 n)$。

考虑 $n$ 很大怎么做。第一想法是建出虚树，但是这个虚树我建不出来。所以只能退而求其次，建出虚树上一些重要的部分，暴力处理其他部分。发现它的部分分里面有一档 $k$ 为奇数。发现 $k$ 为奇数的时候 $lowbitv(x)$ 一直不会变。所以可以处理出来每次当 $lowbit(x)$ 这一位以上的位变化的时候，如果这一位是 $x$ 会变成的数 $y$。处理这个东西的逆数组也就是往前跳得到的东西。处理出来逆数组的倍增数组，找到每个 $x$ 对应的开头的位置，每个开头位置对应一组东西，在这一组上 $x$ 这个位置单点修改，查询就是查询前缀异或和，可以用动态开点线段树，复杂度 $O(q\log^2 n)$。

考虑偶数的情况，类似的找到最低的值为 $1$ 的二进制位。首先可以暴力跳到这一位并且进行暴力修改，暴力的次数不超过 $O(\log_{2}k\times \log_{k}n)=O(\log n)$ 次，每次会增加一个因子 $2$。然后再进行奇数的操作即可。

AGC030E

感觉到晚上状态就不太好了，这个题就不太想动脑子了。

发现能改变的位置至少要左右两边一个是 $0$，一个是 $1$，所以想改变一个位置应该是需要改变一段连续区间才能实现。将 $01$ 之间画上交替的红线和蓝线。然后要求两条线之间长度不超过 $2$，每次修改一个位置就相当于移动一条线的位置。特别的，让两头有无数条交替的红蓝线。

枚举线的匹配方式，发现知道了对应关系之后，移动一定不会交叉。所以最优的移动方式一定是对应的两个位置差的绝对值。并且容易手玩发现这个一定能达到，暴力模拟这个过程，复杂度 $O(n^2)$。

5.28

CF983E

简单题。首先发现如果跳不到 LCA 的话是优先尽可能向上跳，倍增预处理出来从 $i$ 开始尽可能往上跳跳 $j$ 步后的位置。然后从另一边往下跳不好处理，对称一下，也变成往上跳，然后在 LCA 出合并。

跳到两边下一步就到 LCA 的位置 $x,y$ 以后，只需要判断 $x,y$ 之间有没有路径联通。相当于矩形查询有没有点，用主席树实现即可。复杂度 $O(n\log n)$。

CF1728G

$m$ 很小，考虑 $2^m$ 容斥。枚举一些位置钦定不被覆盖，那么 $n$ 个东西都有一些限制。而这些限制的种类可以分为 $O(m)$ 段，每一段都能前缀和预处理。这部分预处理的复杂度为 $O(nm)$，容斥的复杂度为 $O(2^mm)$。

考虑处理询问，新加入的点在序列中两边的关键点情况只有 $O(m^2)$ 种，预处理这 $O(m^2)$ 种情况的贡献和，新加入的这个点对相同情况的点的新贡献是相同的，复杂度 $O(qm^2)$。

AGC048E

太牛了。首先感觉这个条件莫名其妙，涉及到的东西非常多，就算 $A$ 序列已知都很难处理。第一个性质，注意到只有 $x_1\sim x_{i-1}$ 合法，那么一定有一个 $x_i$ 使得 $x_1\sim x_i$ 合法。设 $p=x_i,q=-p+\sum[A_j+Tx_j<A_i+Tp]$。$q$ 在 $p=0$ 时一定 $\geq 0$，在 $p=i-1$ 时一定 $\leq 0$，又因为每次变化最多减少 $1$，所以一定会有一个时刻 $q=0$。

再观察一些性质。设 $z_i=A_i+Tx_i$。当 $p=x_i$ 时 $q=0$，当 $p=x_i+1$ 时一定有 $q<0$，否则同理能证明有更优的解。所以说明此时 $[z_j<A_i+Tp]$ 没有发生任何变化。所以说不存在 $z_j\in [z_i,z_i+T)$，所以说不会有 $z_i\in(A_1-T,A_1]$，因为 $A_1=z_1$。

下面要进行一些神秘操作，我们删去 $A_1$，对于 $z_i>A_1$ 的将 $x_i$ 减一。发现这样之后 $z_i$ 的大小关系不变，$x_i$ 的最优性也不变。所以就可以 dp 从 $2\sim n$ 位推向 $1\sim n$ 位。

枚举关心的位和这一位初值，然后设 $dp_{i,j}$ 表示填了 $i\sim n$，有 $j$ 个的 $z_i$ 比关心的位小。转移枚举下一位的值，复杂度 $O(n^3k^2)$。

51nod1048

考虑一个二维矩形，每一行表示 $2^i$，列表示 $2^i$ 的个数二进制这一位是否存在。那么对应到最后答案第 $i$ 位的就是一条对角线。设 $dp_{i,j}$ 表示从低到高填了前 $i$ 位，有 $j$ 个进位的方案数。转移枚举这条对角线有多少是 $1$，系数是组合数，注意这一位需要满足条件。复杂度 $O(\log^5 n)$。高精度傻波。

51nod1556

枚举终点之后是简单格路计数。

5.29

被构造题整破防弃赛了。

A

傻波构造题。傻波构造题。

猜想答案能达到上界 $\sum_{i=k-1}^{2k-2} p^i$，考虑递归构造。首先从 $k-1$ 的答案让最高位全部相同能构造出来这个式子的除了最后一项的其他项。对于最后一项，它是 $(p^{k-1})^2$。考虑根据这个的构造。枚举第一项除了最高位的值，然后再枚举模意义下的间距 $d$。由于 $p$ 是质数，所以这样可以证明是对的。

B

每个位置会贡献一些 $b_i<b_{i-1}$ 或者 $b_i>b_{i-1}$ 的条件。与两边完全没有限制的位置两边显然是独立的。所以只需要考虑每一段连续的位置，设 $dp_{i,j}$ 表示前 $i$ 位，第 $i$ 位是第 $j$ 大的方案数，前缀和优化转移即可。复杂度 $O(n^2)$。

C

首先确定了 $x$ 之后，每个位置一定操作次数不超过 $2$。对于最高位和 $x$ 相同的，如果能一次就一次，不能一次就两次，其他的一次一定能完成。问题就变成选一个 $x$，让 $\sum[a_i\leq x]-x$ 最大。

这个东西考虑匹配（不知道为啥能想到匹配），每个 $a_i$ 匹配一个 $j\leq a_i$，那么这个值就是失配的点数。那就是要求一个区间内 $a_i$ 的最大匹配。这个东西是比较经典的问题，做法也比较经典。

扫描线 $r$，尽可能匹配靠右的位置。维护匹配的点的状态，加入 $a_r$ 之后，因为 $r$ 最大一定会被匹配，所以 $r$ 就加进了匹配。根据 Hall 定理，需要满足 $w_i=i-\sum_{j\in S}[a_j\leq i]$ 是非负的。再维护一下 $w_i$，如果当前会导致有 $w_i<0$，那么就需要从匹配中删除匹配一段前缀值的位置，找到最前面的位置删掉。这些都可以用线段树实现。复杂度 $O(n\log n)$。

5.30

P3771

感觉还是想太复杂了啊，以为要分类讨论之后用线段树维护。

二分答案，结论是新加的边在直径上。然后对于不合法的对 $(i,j)$ 必须需要用新的边让它合法。把绝对值拆了之后双指针扫 $O(1)$ 遍分类讨论。复杂度 $O(n\log n)$。

loj6185

简单题。

qoj990

咕了。

5.31

100+40+40=180

A

看到这个形式去向 prufer 序列。推一推式子。类似于 prufer 序列推论的推法。

\[\sum_{d_i\geq 1,\sum_{d_i}=k-2}\binom{k-2}{d_1,d_2...d_k}s_i^{d_i+1}(d_i+1)! \]

\[(k-2)!\sum_{d_i\geq 1,\sum_{d_i}=k-2}s_i^{d_i+1}(d_i+1) \]

这个形式就可以 dp 了，设 $dp_{i,j}$ 表示前 $i$ 个，$\sum d_i=j$ 的方案数。复杂度 $O(k^3)$。

$s_i^{d_i+1}$ 这一项可以拆开处理，拆成 $s_i^{-j}$ 和 $s_i^{j+p}$。然后只需要转移 $d_i+1$ 这一项，这一项可以用类似等差数列的方法前缀和处理。复杂度 $O(k^2)$。

B

为什么都会啊？我觉得一点也不简单。

设 $dp_{i,x,y}$ 表示考虑了前 $i$ 个，$B$ 序列中最大值为 $x$，$C$ 序列中最小值为 $y$ 的答案。暴力显然是不行的，考虑优化。发现 $x$ 和 $y$ 的大小关系是先 $x<y$ 再 $x>y$，考虑对这个转折点进行处理。这个转折点将 $B,C$ 分成两部分。一共有四部分分别位于二维平面上分界点分开的四个位置。

考虑扫描线扫左上角的线的 $y$ 坐标，也就是值。不妨假设右上角线的 $y$ 坐标比它大。那么这两部分的答案都是可以提前预处理出来的，预处理每一个位置往上走的答案。分别是一个 LIS 和一个单调栈。用一个线段树维护右上角线的横坐标选择方案对应的除了左上以外三条线的答案。

每次扫一个左上的时候，这个就不能被选择为右上了，在线段树上删掉。然后需要维护左下和右下的答案。左下的情况，需要动态维护一个单调栈，里面每个元素对 $[x,n]$ 的线段树位置有 $1$ 的贡献，容易维护。对于右下的情况，稍微有些复杂。每次动态加入一个元素，维护每个位置以后的 LDS。先求出以它为结尾的 LDS。然后考虑需要求的是线段树上的点代表起点在它之后的 LDS 最大值。用一个 set 维护一段区间的点以后开头的 LDS 最大值。加入这个点的时候类似于 ODT 修改一下，因为 set 内值递减，把所有不如当前值的变成当前值就行了。总复杂度 $O(n\log n)$。

5.31

A

只会 $70$，但是为什么赛时过的五个代码全都是错解啊。

首先考虑把正方形变成长方形，就不会重复覆盖了，代价是较长的边的平方。设 $dp_i$ 表示填完前 $i$ 个的最小代价，枚举下一段矩形的两维转移，复杂度 $O(n^3)$。

发现矩形两维的大小都是 $O(\sqrt m)$ 级别的，所以可以把复杂度优化到 $O(nm)$，进一步用单调队列优化到 $O(n\sqrt m)$，没冲过去。

发现实际每个位置能转移的大小不会超过 $x\in [i-2\sqrt m,i]$ 范围内点的数量级别，这个对应的 $l$ 满足 $\sum l^2=O(m\sqrt m)$，可以分析出来 $\sum l\leq O(m^{1.25})$，然后这样是不能维护单调队列的，复杂度不可避免 $O(n\sqrt m)$，所以考虑决策单调性优化，矩形一维变大的时候另一维肯定也变大。转移的复杂度是 $O(m^{1.25}\log n)$。

注意前缀和处理的时候，只能处理需要处理的位置，就是这些变成为 $l$ 的正方形的并，这个也是 $O(m^{1.25})$ 级别的。所以总复杂度 $O(m^{1.25}\log n)$。

B

对于特殊性质，第三个包是一棵树，求 LCA 即可。第四个包需要猜一些充要条件，发现每走一步 $x+y$ 会增大 $1$，直观感觉每一个 $x+y$ 两个能到的分别是一段区间。因为 $(1,1)$ 能到所有点，所以如果不是一段区间的话，空出来的那个 $(1,1)$ 一定到不了。这个结论是对的。维护倍增数组，二分 $x+y$ 之后倍增跳到这个位置判断区间是否有交即可。

没有特殊性质的话，考虑处理 $mn_{x,y}$ 表示能到 $(x,y)$ 的最靠前的位置的横纵坐标之和。那么如果两个能到达的区间的交有一个 $mn_{x,y}$ 比这两个所在的位置都小的话，那么就是对的。必要性显然，充分性考虑类似特殊性质，取出来一个子矩形的情况。用 ST 表维护，复杂度 $O(n\log n+q\log^2 n)$。

C

首先这个魔怔的操作要想办法用线段树实现区间修改区间查询。用两棵线段树，第一棵维护每个位置当前的值，同时维护一个 $tag$ 表示当前位置的值经过改变之后是否被放到另一棵线段树上过。修改的时候要把这个 $tag$ 的值变成 $0$。每次查询的时候如果没被下放过两个儿子都被下放过了或者是叶子节点，就把当前节点下放到另一棵线段树上，另一棵线段树就维护历史 max 即可。然后再递归合并上去即可。会了这个之后就能做一些特殊性质，有 $44$ 分。

注意到重点在于 dfs 序和重链剖分的 dfs 序之间的矛盾，考虑怎么解决这种矛盾。对于一棵树，找到根节点所在重链，将这条重链旁边的所有儿子按照 dfs 序来排序递归处理，最后处理重链。这样显然链操作是拆成 $O(\log n)$ 个区间的。对于 dfs 序操作考虑差分，每次修改一段前缀。从节点 $x$ 开始跳重链，每次这条重链旁边的儿子 dfs 序是连续的，所以可以二分出来需要修改的一段范围，还需要修改这段重链本身。同时在轻重链切换的位置需要进行一些特殊处理。也是 $O(\log n)$ 个区间。复杂度 $O(n\log^2 n)$。

6.2

A

怎么就不会呢/fn/fn/fn

在全局上看，每一步两个有四种情况，都向下，都向右，和两个不同。两个不同的两种情况数量一定是相同的，不然无法到达同一个终点，设两个相同的次数是 $x$，需要对于每个 $x$ 求出剩下两个安排的方式使得距离之和不超过 $k$ 的方案数，再乘上安排顺序的组合数。

对于 $k$ 小的情况，可以直接 dp，$dp_{i,j}$ 表示考虑了 $i$ 步两个相同的情况，两个相距 $j$ 的方案数。复杂度 $O(nk)$。

对于 $k$ 大的情况，枚举 $x$ 之后可以转化为网格图走路，不能碰到 $x-y=k$ 和 $x-y=-k$ 两条线，枚举碰到几次线，对称一下就是组合数，复杂度 $O(\frac{n^2}{k})$。总复杂度 $O(n\sqrt n)$。

B

首先对于根是 $1$ 的情况，维护每个点上合并的次数，设 $siz_u$ 表示 $u$ 子树内的游客数量。那么如果查询点在 $x$，答案就是 $\sum_{u\in subtree(x)}u(siz_u(siz_u-1)-\sum_{v\in son_u} siz_v(siz_v-1))$。化简一下能得到 $\sum_{u\in subtree(x)}(u-fa_u)siz_u(siz_u-1)+fa_usiz_x(siz_x-1)$，用线段树维护 $siz_u$ 和 $siz_u^2$ 即可。复杂度 $O(n\log^2 n)$。

对于根不是 $1$ 的情况，如果 $LCA(rt,x)\neq x$，那么和根是 $1$ 的情况是一样的。否则用第二棵线段树维护 $(fa_u-u)siz_u(siz_u-1)$，用第一棵线段树全局答案减去 $1\sim x$ 链上的情况，再加上第二棵线段树 $1\sim x$ 链上的答案。然后还需要减去 $x$ 包含 $rt$ 子树的答案，这样就能求出第一部分答案了。第二部分一个 BIT 就好了。复杂度 $O(n\log^2 n)$。

6.3

ARC179D

简单题。赛时没写完。对于确定根节点的情况，有一个简单的 dp，设 $f_{u}$ 表示 $u$ 子树内全部染黑，并且要回到根节点的答案。$F_u$ 表示 $u$ 子树内全部染黑，不需要回到根节点的情况。转移 $f_u=\min(f_v+2,2siz_v-mx_v)$，$F_u$ 就从 $f_u$ 中选择一个变成 $F_v+1$ 转移上来，复杂度 $O(n^2)$。

可以换根 dp，在记录 $g_u,G_u$ 表示 $u$ 子树外的情况，然后拼起来就行了，复杂度 $O(n)$。

ARC179E

简单题。扫描线右端点，维护两个 set 表示合并完的 $x=h_r$ 的和 $y=w_r$ 的集合 $l$ 位置和另一维大小。然后如果 $h_{r-1}=h_r$，那么第一个 set 全部保留，另一维大小全局加，否则全部删掉。还需要在 $x$ 这个 set 里面二分一下有没有能放进 $y$ set 的元素，全局加打一个 tag 就行了。复杂度 $O(n\log n)$。

CF1550E

二分答案。然后预处理出来每一段能不能达成 $x$，设 $dp_s$ 表示 $s$ 集合的状态凑出来需要的最小右端点。然后枚举一个专一即可，复杂度 $O((nk+k2^k)\log n)$。

qoj5637

这个条件需要转化一下。首先肯定是不断地操作 $1$ 的不同子树，这样 LCA 一直是 $1$，直到只剩一个子树里面有元素，然后就递归到这个子树里面解决问题。

设 $dp_{u,i}$ 表示 $u$ 子树里面剩下 $i$ 个，并且不确定是哪 $i$ 个的方案数。那么 $dp_{u,i}$ 就从 $dp_{v,j}$ 转移过来。转移的时候对于其他子树，每个子树内的元素都看成一样的，就是要求每次填的元素子树标号不同。如果固定每个子树内的元素数量的话，可以容斥解决。但是我们不知道每个子树内元素数量，所以在背包的同时进行容斥。设 $f_{i,j,k}$ 表示考虑了前 $i$ 个子树，选了 $j$ 个元素，被钦定了 $k$ 个相邻的相同。每次枚举这个子树有多少元素，钦定多少相邻的相同，转移系数就是一些组合数。枚举选的哪个子树递归下去，这个子树里面有多少东西，然后进行其他子树的 $f$ 转移之后，再转移这个子树剩下的东西，然后贡献到 $dp_u$ 的一个位置。复杂度大概是 $O(n^6)$，跑的很快。

qoj4217

$\binom{14}{7}\geq 3000$，给每个元素分配一个大小为 $7$ 的两两不同的集合，$u\rightarrow v$ 的边就给一个 $s_u$ 有 $s_v$ 没有的颜色。

6.4

87+20+40=147 rk5

A

fst 了 13pts。难过。多测一定要全部清空。并且结构体里面塞一堆函数的话，里面最好用 vector 开动态数组而不是开静态数组，在数据组数多 $n$ 小的时候区别很大。好像是寻址问题。

简单写一下做法。按照 $w$ 排序之后加入当前 $w_x$ 对应的距离为 $x$ 的边。类似优秀的拆分，每隔 $x$ 放一个关键点，每两个关键点之间通过求 LCP 和 LCS 就可以知道一段连续的区间有边。

考虑把这些边中有用的加进去，用类似萌萌哒这个题的做法，建立一个形如 ST 表的并查集。每次合并的部分能够类似于 ST 表分成两个长度为 $2^k$ 的区间。每次如果已经合并过就返回。否则递归下去合并，在叶子节点合并的时候加入答案。时间复杂度 $O(n\log n)$。

B

第一步就没想到，喜提暴搜分。

记录每个位置需要被操作的次数 $c_i=b_i-a_i$。将区间操作差分到两个端点上考虑，然后记录 $c_i$ 的差分数组 $d_i$。差分之后就能网络流了，选择一个区间 $l,r$ 减一，就是 $l\rightarrow r+1$ 连边，然后将 $d_i\geq 0$ 的连起点，反之连终点，跑一遍最大流，如果最大流能满流就是有解。期望得分 $40$ 分。

将每个点拆成三个点，其中 $u_2\rightarrow u_1,u_3\rightarrow u_1$ 连边，然后 $u_2,u_3$ 分别连出一条正着的和反着的链，就可以前后缀优化建图网络流。期望得分 $60$ 分。

考虑优化这个东西。以前没见过这个套路，这个图是一般图很难模拟网络流，所以想办法把这个图变成二分图。二分图肯定是 $d_i\geq 0$ 的在一边，$d_i<0$ 的在一边。每个左部点连接的右部点应该是一段前缀和一段后缀。考虑求出这个前后缀1的位置。如果是一个 DAG 发现是好做的，拓扑排序一遍就行了。所以缩掉强联通分量之后再拓扑排序一遍就能知道每个 $x$ 对应的一段前缀 $[1,l_x]$ 和一段后缀 $[r_x,n+1]$。

知道了这个之后，考虑 Hall 定理，每个右部点的一段前缀和一段后缀的并都对应一个左部点集合，这个左部点集合与 $s$ 连接地流量不能超过这个右部点集合与 $t$ 连接的流量。剩下的就是简单数据结构问题，扫描线 $l$，维护每个 $r$ 位置右部图的流量减去左部图的流量的区间最小值。每加入一个合法的位置对应一个区间修改，线段树维护区间加区间最小值即可。复杂度 $O(n\log n)$。

C

数论题差不多得了。

6.5

100+20+10=130

太喜欢指数级暴力了。

A

想了很久神秘贪心。难过。

考虑从一个起点出发的两条点不相交的路，它们会形成一个方程这些边的边权和为 $0$。有这样一堆方程之后用线性基求出极大线性无关组，用 $m$ 减去这个数就是可以自由选择边权的边数，答案就是 $2$ 的这么多次方。

枚举起点 $u$ 和终点 $v$，以任意顺序不断取出一条 $u$ 到 $v$ 的路径，然后两两之间建立方程组。这样就是对的，因为点不相交的路径在这里一定会统计到，适当使用当前弧优化就能做到 $O(n)$ 这一部分。然后在线性基里面插入方程的部分用 bitset 优化做到 $O(\frac{n^4}{w})$。

B

构造题差不多得了。

C

首先有一个性质，左上和右下都只有一个或者左下和右上都只有一个。以前者为例。如果右上有超过两个，那么缺的那个角一定是由左下来负责，否则一定删去一个更优。这样左上和右下都剩下一个互相独立的矩形，显然只需要一个能包含这个矩形的矩形。

这样就可以枚举左下第一个选的哪一个，然后右上第一个要在满足左上能被覆盖的情况下尽可能把 $x$ 放小，然后不断扩展，扩展都是一维有条件另一维最大化或者最小化，直到右下能被完全包含。预处理之后可以 $O(n)$ 做。总复杂度 $O(n^2)$。记忆化一下状态，复杂度 $O(n)$。

6.6

这场模拟赛质量好高啊

75+80+16 我真的一道题都不会做

A

首先我先想了挺久笛卡尔树上嗯 dp 的，但是发现很难做到 $O(n^5)$ 以下的复杂度。所以就考虑用期望线性性拆掉贡献，考虑两个点 $i,j$ 满足 $i$ 是笛卡尔树上 $j$ 的祖先的概率加起来。

不失一般性的，设 $i<j$，那么条件显然是任意 $k\in [i+1,j],a_{k}<a_i$。枚举 $a_i$ 所属的区间，然后暴力 $O(n^2)$ dp，总复杂度 $O(n^4)$，尝试卡常卡过去无果。

首先可以发现这个 dp 是每次乘上一个一次多项式 $(ax+b)$ 的形式，然后要求出每个位置的系数。这里很厉害的一点，我们并不关心 $i,j$，只关心系数，所以可以只考虑多项式来解决。分治，每次处理 $i,j$ 分别在两边的情况，然后将多项式乘起来，加进一个桶里面最后统一贡献答案。复杂度分析出来是 $O(n^3)$。

B

首先把这个一堆函数分别用一棵李超树维护，每次区间加入函数，查询单点最大值即可。复杂度 $O(n\log^2 n)$。

对于 $a_i+d_i\geq n$ 的情况，不会出现增的那段二次函数，所以把一次函数和开口向下的二次函数全局加入并不会使得假如比原答案更大的答案。这样就能得到 $80$ 分了。

对于没有特殊性质的情况，我们强行创造一个特殊性质。发现问题出在开口向上二次函数对称轴左边的那一部分，所以我们直接让那一部分是一个常函数，值为顶点值，这样创造了一个分段函数。这样一个分段函数是可以用李超树维护的，所以变成全局加入这个分段函数，复杂度 $O(n\log n)$。

C

很神仙的题目。

这个行列式肯定不能直接算的，考虑用一些东西转化。和行列式有关的东西大概只有 LGV 引理了。LGV 引理是对于有向无环图的路径计数，这里套路地把矩阵看做二分图的邻接矩阵。这样考虑每次变化就是一个动态的二分图。但是动态处理二分图边权是一个很麻烦的事情，我们考虑把图变成一个别的形式，比如网格图。起点看做红点，终点看做绿点，每次加入一个操作的时候，就加入一行点，然后建立对应的竖着的边，边权为 $d_k$。然后在这一行上 $l\sim r$ 这段区间加入横着的边，因为那个 $c^{i-l}$ 的形式很好看，所以每条边边权都是 $c_k$，然后路径权值视作乘积（满足 LGV 引理）的时候恰好就是正确的方式。

然后那个要求的东西就转化为从 $n$ 个红点出发，选择 $n$ 条终点为绿点的路径，这些路径的权值是边权积，所有方案路径权值和的和。发现 $s$ 很小，也就是每一列有出边的点很小，考虑用这个来状压 dp。设 $dp_{i,s}$ 表示考虑了前 $i$ 列，第 $i$ 列有入度的点里面被路径覆盖的点的集合是 $s$ 集合的方案数。每次枚举转移的时候对于一个有入度的集合 $s$，它会转移到一个有出度的集合 $t$，先转移到字典序最小的集合 $t$，这个 $t$ 是唯一的，并且不能有 $s$ 里两个元素转移到 $t$ 里同一个元素。确定了这个 $t$ 之后，可以把 $t$ 里面被选择的元素往下移动，这个操作类似于高维后缀和，一次对每一维考虑即可。注意需要对红点和绿点做出一些特殊处理。复杂度 $O(m2^ss)$。题解还说了很多卡常技巧。

6.10

A

首先如果确定选哪些之后，按照 $a_i+b_i$ 排序之后逐个选择是最有可能把这些都选进去的。按照 $a_i+b_i$ 排序之后反悔贪心。每次能选进去就选进去，不能选进去就找一个 $a$ 最大的看看能不能替换掉，如果能替换掉替换掉它，用优先队列维护，复杂度 $O(n\log n)$。

B

题意就是内向基环树森林本质不同染色方案数。首先先算一下有根树的方案数。如果没有本质不同这个限制，那么方案数就是 $m^n$。但是如果一个点有两个完全相同的子树，就有可能出现重复状态。用树哈希判断子树是否相同，对于每种子树彼此之间独立。对于一种子树，如果子树方案数是 $x$，有 $k$ 个这种子树，那么方案数就是 $\sum_{i=1}^k\binom{k-1}{k-i}\prod_{j=0}^{i-1}(x-j)\frac{1}{i!}$。考虑枚举 $i$ 作为染色方案不同的子树数量，容易在 $O(k)$ 时间内计算，这部分复杂度为 $O(n)$。

再考虑一个环上的情况，对于多个基环树之间用类似于合并子树的方式合并一下即可。环上每棵树都有一个哈希值，求出来这个哈希值形成的序列的最小周期 $T$。分别考虑染色后周期为 $T,2T...$ 的方案数。首先需要满足环长 $L$ 有 $L\bmod kT=0$ 才有可能做出贡献。对于这种情况，我们只需要考虑一个周期内的情况。我们容斥周期恰为 $kT$ 的方案数，容斥系数是莫比乌斯函数，对于这种情况，方案数是容易计算的，注意最后由于是环，要钦定字典序最小，乘上一个 $\frac{kT}{L}$。复杂度 $O(n\log n)$。

C

首先容易转化为求区间子区间的最大值的和。这个可以容易用一些二维偏序的东西做到 $O((n+q)\log n)$ 或者 $O(n\sqrt n+q)$。

考虑优化这个东西，找到 $[l,r]$ 这个区间里面最大值的位置 $p$，那么对于两个端点在 $p$ 两侧的情况，最大值就是 $a_p$。然后可以分到两边考虑。以右边为例，考虑以每一个固定为右端点的情况，不断向左走跳到下一个比当前点大的位置，除了首尾位置，每一个位置的贡献都是 $a_x(x-fa_x)$，这个东西是可以预处理的，可以预处理出来每个点到树根的链的这个东西的和。那么这部分贡献就是 $sum_r-sum_p$ 这种类似的东西，对于 $sum_r$ 的这一部分前缀和处理，$sum_p$ 的这部分只有一项，可以简单处理。复杂度 $O(n\log n+q)$。

6.11

A

考虑将 $\max$ 拆掉，按照 $x-y$ 为关键字建立线段树。这样每一段就能选择确定的 $x$ 或者 $y$ 造成贡献了。线段树叶子结点维护 multiset，然后答案是区间可合并信息。复杂度 $O(n\log n)$。赛时没注意到可合并，写了个线段树分治嗯卡过去了。

B

本质上就是个 FWT 板子。因为 FWT 每位是独立的，所以可以将每一位按照 FWT 的形式进行一个相互独立的变换。然后这 $n$ 次复合上的东西是一样的，所以 FWT 之后对点值快速幂，然后 IFWT 回去就行了。复杂度 $O((m+\log n)2^m)$。

C

首先对于最长公共后缀，可以二分哈希，也可以建出后缀自动机，然后找到 parent 树上的 LCA。对于最长公共前缀，一个暴力是暴力建出一个节点规模为 $O(n^2)$ 的 trie 树，然后经典操作加上链和，然后链上加一。复杂度 $O((n^2+q)\log n)$。

考虑减小 trie 树的规模，首先发现进行加入的本质不同串只有 $O(n)$ 个，因为只有 SAM 上每个节点代表的最长串有可能被加入。考虑如何快速建出 trie 树。对于 SAM 上每个节点，尝试找到它在 trie 树上的父亲。它在 SAM 上的每条入边都对应它的一个祖先，它的父亲就是其中最长串长度最大的那一个，这样枚举 SAM 上每条边就能快速建出这个 trie 树，然后就树剖之后转化为链加链和了。复杂度 $O((n+q)\log^2 n)$。

6.12

37+30+5=72 emo 了。

A

出题人傻逼。出题人傻逼。出题人傻逼。

首先假做法为什么能过那个大样例的。其次非得给一个 $p_i$ 是想让大家挂分吗。

二分一个 $mid$，满足 $mid$ 是最小的只保留 $1\sim mid$ 的边能够 $dis(S,T)\leq D$ 的数。然后 $mid$ 这条边补上 $D-dis(S,T)$，$<mid$ 的边就是本身，$>mid$ 的边给一个 $\infty$。复杂度 $O(n\log^2 n)$。

B

这玩意都不会？这玩意都不会？这玩意都不会？

不要关注过程，直接关注最后的结果序列，唯一的限制就是不能有一段连续的值长度 $<k$ 并且两边都比它大。直接对着这个 dp 就行了。设 $dp_{i,j,0/1}$ 表示前 $i$ 个，$i$ 这一段长度为 $j$，是否要求右边比它小的答案。转移枚举下一段的长度，下一段的值就确定了，然后考虑从 $i$ 对应的哪个 $j$ 转移过去，发现如果是大于它是一段 $j$，小于它是一段 $j$，对应这一段的贡献是一样的，所以可以前缀 $\max$ 优化。复杂度 $O(n^2)$。

考虑优化，可以简单假定每一段的长度 $\leq k$，因为 $>k$ 的段显然可以拆成两段，答案不会发生改变。所以第二维的大小和转移需要枚举的长度都 $\leq k$，复杂度 $O(nk)$。

6.13

A

应该是 SD 2023 二轮省集那个打表题。

首先对于中间的白点，两边必须都是黑点，并且两边互相独立。这样就转化为求长度为 $n$ 的序列，头是 $1$ 的概率了。

这个概率可以枚举第一次操作的位置之后递归到子问题 dp 的，前缀和优化即可做到 $O(n)$。

B

很厉害的字符串题。首先建出来 SAM，然后线段树合并 endpos 集合维护出一个后缀位置集合，这个节点对应的 $len$ 就表示这个后缀集合对应的最长串长度。那么就要求选择的串的长度 $x$ 是要 $\geq $ 这些点之间的最长距离。然后还要考虑头尾的情况，头上是好处理的，考虑 border。$x$ 需要比这个前缀 $\geq \frac{len}{2}$ 的最短 border 大或者比 $len-$ 这个前缀 $<\frac{len}{2}$ 的最长 border 大。这个东西是可以预处理的。关键在于后缀的问题。

假设最后一个位置为 $p$，串长为 $n$，那么长度 $len$ 需要满足 $border(p-len)\geq n-p$，对于前面的限制，$len$ 有一个范围限制，这又是一个限制，所以是一个二维偏序的形式，用主席树维护一下二维偏序。对于长度和字典序最小，在主席树上二分找到长度最小的，判断字典序预处理一个 SA 即可。复杂度 $O(n\log^2 n)$，精细实现可以做到 $O(n\log n)$。

C

题解有问题/fn/fn/fn

首先对于 $x$ 确定的时候，逐个选择的时候肯定要先把低位弄完，这时候高位不会因为低位发生变化，不然直接变化高位更优。所以可以逐位 dp，设 $f_{i,0/1}$ 表示前 $i$ 位一样了，后面的位是全 $0$ 或者全 $1$ 的答案。转移 $f_{i+1,0}=\min(f_{i,0},f_{i,1}+1)+k),f_{i+1,1}=\min(f_{i,1},f_{i,0}+1)+2^{s_{i+1}-s_i}-1-k$。但是这个转移是有些细节问题的，或者要给一个合适的初值才能没有细节问题。

目前只是确定了 $x$ 的情况，观察这个 dp，容易发现要使答案比较大的话，$k$ 要尽可能接近 $2^{s_{i+1}-s_i}$ 的一半，这时候 $f_{i,0}$ 和 $f_{i,1}$ 也是很接近的，设 $a_i=f_{i,1}-f_{i,0}$ 表示 $f$ 的差值。再设一个 $b_i=1-(f_{i,1}+f_{i,0})+\sum_{j=0}^{i-1} 2^{s_{j+1}-s_j}-1$，这个 $b$ 大概表示的就是因为取 $\min$ 浪费掉的贡献。移项之后可以看出来 $f$ 的和加上 $b$ 是定值，所以 $b$ 表示的就是浪费掉的值。

可以根据 $f$ 的转移推出来 $a,b$ 的转移，$a_{i+1}=2^{s_{i+1}-s_i}-1-2k+\min(a_i,1)-\min(a_i+1,0),b_{i+1}=b_i+\max(a_i-1,0)+\max(-a_i-1,0)$，发现可以始终保持 $|a_i|\leq 1$，也就可以保持 $b_i=0$，所以不会浪费，就可以简单得到第一问的答案，事实上第一问也可以直接猜结论。

对于第二问，容易发现 $|a_i|,b_i$ 的合法范围都是 $O(1)$ 的，因为如果过大的话，浪费的就会很多，所以直接把这个压进状态里面 dp 套 dp 即可。复杂度 $O(m)$。

但是 $f$ 的转移有点小问题，目前不知道怎么修/ng

6.14

100+70+20=190 挂了 20 分/ng

A

简单题。设 $dp_{i,j}$ 表示考虑了前 $i$ 个，用了 $j$ 个填前缀的操作的方案数。转移考虑这一个填后缀还是前缀，容易算出有多少后缀能填，填后缀的方案数是好算的。如果填前缀，考虑先不确定填哪一个，等到来了一个前缀必须填进去的时候，在已经被填但不确定的位置中选择若干个填进去，方案数是排列数。复杂度 $O(n^2)$。

B

枚举直线的斜率向量 $(x,y)$，只有 $\gcd(x,y) =1$ 的能被统计进答案，然后知道 $(x,y)$ 之后的方案数是可以 $O(1)$ 算的。常规莫反一下 $\gcd$，就能得到一个式子。我赛时的式子很丑，不能做。别人莫反出来的式子只有 $\phi(i),\phi(i)i,\phi(i)i^2$ 这几项，都可以杜教筛，复杂度 $O(n^{\frac{2}{3}})$。

C

答辩。CF1305H。

首先对于 $b_i,a_i$ 确定的问题，是二分图匹配问题。只需要考虑二分图是否能够满匹配。题解大部分考虑的最小割，我赛时考虑的是 Hall 定理，将 $a,b$ 排序之后，对于一个 $a$ 的集合，它对应的 $b$ 的集合大小只和这个集合的元素个数有关。所以只需要考虑 $a$ 的一段后缀，它能匹配 $b$ 的集合大小可以双指针，这样就能判断是否合法。同理，如果 $b$ 不知道，可以得到一个数组 $lim_i$，需要满足 $\sum_{j=1}^i b_j\geq lim_j$。

对于 $a_i$ 不确定的问题，可以贪心地转化为 $a_i$ 确定，由于 $a_i$ 肯定是越靠近越优，所以只分成贴下界的，贴上界的，$a_i=p$ 或 $a_i=p+1$ 的。可以二分得到 $p$，这样就转化为 $a_i$ 确定，$b_i$ 有一个 $lim_i$ 的限制。

考虑二分答案，最大值个数满足可二分性。如果这一段范围里面有确定的 $b_i$，那么这一段就确定的，前面的在满足限制的条件下贪心前面尽可能大。否则的话直接贪心前面尽可能大，后面有可能会出现有些是 $x$，有些是 $x+1$，就从前面贪心去靠后的位置把后面都弄成 $x+1$。然后判断是否满足 $lim$ 的条件即可。对于第二问同理可以二分，check 几乎没有区别。有一车细节。复杂度 $O(n\log n)$。

6.15

P7216

JOISC 总是出神仙题啊。会不了一点。

首先对于 $K\leq 3$ 的情况发现部分分给的特别少，要想一想原因，应该会是很简单的。对于一维的情况，可以直接贪心扫过去。对于二维的情况尝试类比，扫一下找到 $l$ 左边必须有的最小的 $l$，另外几个边界类似。如果 $l>r$ 或者 $u>d$，那么可以直接转化为一维的情况，否则的话四个边界围成了一个矩形。因为 $K\leq 3$，所以至少要选择一个矩形顶点，然后递归解决问题即可。复杂度 $O(4^Kn)$。

对于 $K=4$ 的情况，还有可能四个边界分别选一个，不需要选择顶点。这种情况，对于一个矩形，可能和这个边界矩形的若干条边有交。如果有至少三条边有交，那么一定是合法的，不需要考虑。如果只有一条边有交，那么就是对于这条边上能选择的位置有一个限制。下面只需要考虑与两条边有交的情况。

两条边这个东西可以想到 2-SAT，建立两个点分别表示选择哪条边。然后对于在矩形的一条边上的 2-SAT 节点一起考虑，对于两个没有交点的区间对应的 2-SAT 节点是不能同时被选择的。按照一个端点排序之后建立一些辅助节点进行前后缀优化建图，然后跑 2-SAT 求出每个边界最终的范围，在合法的范围里随便选一个点就行了。复杂度 $O(n\log n)$。

loj540

太唐了。构造若干个完全图，然后连在一起就行了。

loj2759

一个简单的 dijkstra 变式，关键在于别想的太复杂。对于特殊性质，每次一定不会额外向上走，因为这样还有可能导致跳不到下一棵树。所以每次的高度都是 $0$，所以可以在 dijkstra 的同时算上向上爬的贡献即可。

对于没有特殊性质的情况，其实是类似的。对于还没下到底的时候，在 dijkstra 的同时加上可能会存在的向下爬的贡献。这里当前的高度 $h$ 满足 $h+dis_u=x$，所以可以简单算出当前高度，在高度变成 $0$ 之后用特殊性质做法即可。

6.16

100+60+35=195

谁让你把傻逼三合一数据结构扔 T3 的？

A

先用 $n+n$ 次操作问出来 dep，然后逐层确定父亲即可。逐层确定只要让上一层点的值不同，容易做到。

B

赛时的做法和正解貌似没有什么相关性，也记一下吧。

赛时的想法是对值域分块，然后扫描线 $r$，维护每个值域的位置减去值比它小的数的大小，然后对每一块维护一个排序后的结果。如果询问的左端点是 $1$，那么就可以直接在每个块二分出来有没有这个值是 $0$ 的位置。复杂度 $O(n\sqrt n\log n)$。对于左端点不是 $1$ 的情况，就要减去这一部分的位置贡献和值的贡献。位置贡献是好处理的，直接全局减去 $l-1$ 即可。对于值的贡献，在每一块的值是差不多的，具体来说，每一块的值的贡献两个端点之差不会超过 $O(\sqrt n)$。所以可以直接把这部分贡献的区间当做贡献，二分找到有可能做出贡献的最小位置。从这个位置开始一个一个暴力跳，直到这个位置不可能做出贡献为止。由于数据随机，每一块里面的值是均匀分布的，所以每一块有可能做出贡献的位置期望是 $O(1)$ 的。对于二维偏序的部分，随便找个数据结构维护一下，总的复杂度仍然是 $O(n\sqrt n\log n)$。

在线的话就可持久化这个分块就行了。复杂度仍然是 $O(n\sqrt n\log n)$，但是寻址常数很大。卡了很久寻址和数据结构部分的常数也只能卡过 5e4，8e4 最后也差一点。

官方的做法很厉害，考虑一个递归，设 $f(l,r,L,R)$ 表示全局考虑下下标在 $[L,R]$ 之间的点，对应需要满足值域在 $[l,r]$ 之间，具体排位未确定的答案。每次找到值域中点 $mid$，在整个询问区间找到有多少值位于 $[l,mid]$，然后递归到 $f(l,mid,L,L+num-1),f(mid+1,r,L+num,R)$ 两边处理，直到只有一个位置，那么就合法了。

这个东西看起来复杂度很不靠谱，但是加上一个剪枝，就是减掉下标区间和值域区间完全不相交的情况，这样就对了。分析一下，设值域区间的长度为 $len$，那么一个递归区间合法的概率是 $\min(\frac{len^2}{n},1)$。将 $len$ 按 $\sqrt n$ 分类考虑，两部分均不超过 $O(\sqrt n)$。

这样递归次数就是 $O(n\sqrt n)$ 的了，用可持久化分块 $O(1)$ 求出 $num$ 即可做到 $O(n\sqrt n)$。

C

傻逼三合一。

首先询问拆成四条到根的链，这样方便一点。

对于第一部分的贡献，考虑定期重构。对于不是这一块的贡献，可以在重构的时候 $O(n)$ 前缀和预处理出来。对于是这一块的贡献，把 $i$ 对 $x$ 到根的路径有贡献这种形式记录下来。最后 dfs 一遍，处理出来当前从跟到链的情况，然后区间查询即可。用分块可以平衡到 $O(n\sqrt n)$。

对于第二部分，暴力单点加，区间查询，同样可以用分块平衡到 $O(n\sqrt n)$。

对于第三部分，分 $d\leq \sqrt n$ 和 $d>\sqrt n$ 讨论，后者沿用第二部分做法。前者只需要预处理每个 $d$ 加了多少，预处理出来每个点路径上有多少 $d$ 的倍数，暴力即可。复杂度 $O(n\sqrt n)$。

6.17

A

首先二分答案。然后每个点两种情况，考虑 2-SAT，对于两个不同颜色的点，如果距离 $<mid$ 就需要建一组 2-SAT 边。暴力建边跑 2-SAT check 的复杂度是 $O(n^2\log n)$。

考虑优化建图，需要建图的边是值在一个区间内，颜色不同的位置。这个是一个二维偏序的形式，颜色不同可以看做颜色小于这个和颜色大于这个并起来。用主席树优化建图。复杂度 $O(n\log^2 n)$。

B

建出来虚树，然后 dfs 两边求出来每个虚树结点最近的关键点位置。对于每条虚树边，可以倍增求出来两个端点分别负责的部分。然后旁边的子树到这个节点的各种值都可以前缀和预处理。没啥思维难度，代码感觉不好写。复杂度 $O(n\log n)$。

C

长剖，然后做完了。复杂度 $O(nk)$。

6.18

P9333

简单题，容易转化成求与一个集合 $S$ 交集大小最小的 $|a_i\&S|$。可以先做一遍 $a_i$ 的高维前缀和代表交是这个数。然后做一遍高维后缀和就能维护出每个 $S$ 的答案。注意不能 $i=j$，可以维护最大值和次大值。复杂度 $O(nm+m2^m)$。

P9334

首先有 dp 做法可以简单做到单次 $O(n\log n)$，但是没有前途。

考虑贪心，注意一个结论，在最优情况下，小段的长度都是 $1$，这时候大段需要满足 $\sum_{i=l}^r a_i>\max(a_{l-1},a_{r+1})$。可以继续猜测这个条件在小段长度不为 $1$ 也是成立的，证明可以调整。所以可以对于每个 $r$ 求出最大的 $f(r)=l$ 满足 $[l,r]$ 是合法的大段。然后选择 $x$ 为一个大段的右端点之后找到 $nxt(x)$ 表示左端点 $>x$ 时最小的下一个右端点位置。找 $nxt(x)$ 就可以从 $x+2$ 开始，找到一个满足条件的位置。然后每次询问的时候就可以把所有好的大段按照右端点排序之后贪心。只保留 $f(r)$ 对应的这一个显然就是够用的。复杂度 $O(nq)$。

对于没有修改的部分，可以建出来这棵树然后在上面倍增。这部分是简单的。复杂度 $O((n+q)\log n)$。

考虑有修改的情况。看起来很难处理，但是继续观察性质。一个性质是 $nxt(x)-x=O(\log V)$。证明考虑找到 $x$ 右边的随便一个位置，向左跳如果不满足条件那么 $a_{l-1}\geq sum$，这样 $sum$ 至少变为 $2$ 倍，向右边跳同理，所以 $nxt(x)-x\leq 2\log V$。

有了这个结论，每次修改只会修改 $O(\log V)$ 个位置的 $nxt$ 数组。对于知道 $nxt$ 数组之后的情况，可以直接用一个线段树来维护起点在这个区间前 $O(\log V)$ 个位置，跳出这个区间之后跳出的长度和跳的次数分别是多少。这个信息是区间可合并的。合并的复杂度是 $O(\log V)$。注意到修改的是一整个区间，所以不需要逐个修改，被覆盖的区间个数只有 $O(\log V)$，总的复杂度为 $O(n\log V+q\log^2 V)$。注意要讨论一下边界是否为小段的情况。

P9339

首先对于第一个特殊性质，只需要做一个背包。对于第二个特殊性质，考虑每个桶都要匹配满东西，按照每种元素的个数从大到小贪心即可。

考虑第二个特殊性质的情况，桶和元素的关系看起来很像二分图匹配。如果桶是确定的，就是需要判断这个二分图是否有完美匹配。考虑 Hall 定理来刻画。对于大小前 $i$ 大的桶，他们对应另一边的元素个数和桶大小无关，可以预处理出来，为 $lim_i$。那么需要这些桶的大小和不超过 $lim_i$。根据 Hall 定理，这个条件是充要的，所以可以 dp 。

设 $dp_{i,j,k}$ 表示考虑了前 $i$ 大的桶，选了 $j$ 个桶，总和为 $k$ 是否合法。转移类似完全背包。可以用 bitset 优化到 $O(\frac{n^3}{w})$。再注意到桶大小不同，所以 $j$ 这一维的范围是调和级数。实际复杂度为 $O(\frac{n^2\log n}{w})$。

6.29

A

每一段 ABABABA 都可以删去任意个 AB，全都乘起来就行了。注意处理一下长度为奇数和偶数的情况。

B

构造题/fn/fn/fn

考虑逆排列，操作可以交换两个逆排列上值的差在 $k$ 以上的位置，一路冒泡排序上去，不会出现重复的操作，并且可以说明这个是最优解。

C

我的做法好像比官方做法少一个 $n$。设 $f_{i,j}$ 表示前 $i$ 个，选的前缀和为 $j$ 的本质不同方案数，为了去重，再设 $g_{i,j}$ 表示前 $i$ 个，选的前缀和为 $j(j\neq 0)$，并且有一个 $j=0$ 的方案前面的所有数的值都和它相同的方案数。

考虑转移，首先有 $f_{i-1,j}\rightarrow f_{i,j},f_{i-1,j}\rightarrow f_{i,j+a_i}$，并且如果 $j=0$，这两种状态前面是一样的，所以有 $f_{i-1,0}\rightarrow g_{i,a_i}$。注意这里的后两个转移在 $a_i=0,j=0$ 的时候完全没有意义，所以这时不进行转移。对于 $j=a_i$ 的情况，还需要考虑转移 $-g_{i-1,j}\rightarrow f_{i,j}$，原因在于这里 $f_{i-1,0}$ 并且选入和 $f_{i-1,j}$ 且不选入会得到两个完全相同的状态，需要减去算重的部分。对于 $g$ 数组，如果 $j\neq a_i$，那么需要传递到下一级，$g_{i-1,j}\rightarrow g_{i,j}$。复杂度 $O(n^2|a|)$。

D

简单题。首先找到区间内部的一个最大值位置。这个最大值位置一定会对答案产生贡献。考虑分类讨论区间的形式，第一种情况是最大值在第二段，这种情况两边第一段第三段一定只有 $a_l,a_r$ 分别一个元素。考虑另一种情况，如果最大值在第一段，那么第二段一定只有一个元素。这又分成两种，其中一中是第三段也只有一个元素，另一种是第三段并不是只有一个元素，这种情况第三段拿这个后缀的最大值，第二段单拿一个位置的值。离线下来用单调栈+线段树维护即可。$O(n\log n)$。

E

直接考虑最终序列的状态，假设最终 LIS 中最大值为 $r$，那么 $[r+1,n]$ 的元素一定倒序排在最前面，这个结论是显然的。另一个结论是对于剩下的元素，LIS 的值域一定是一段后缀值域，证明考虑调整，交换后一定不劣。并且 LIS 部分递增，非 LIS 部分递减。那么最后情况是先把 $[r+1,n]$ 排在前面，然后剩下分成两半，LIS 和非 LIS 分别是一个单调序列。

发现只有 LIS 位置可能会产生代价，并且产生代价的条件是放置位置 $i$ 满足 $a_i\geq n-r$，可以对于每个 $r$ 预处理最多有多少个位置不产生贡献，这个可以扫描线+树状数组预处理。然后查询答案就对 $r$ 求一个后缀 $\max$ 即可。复杂度 $O(n\log n)$。

7.2

梦熊 round 33

A

想了一个 $O(n\log^2 n)$ 的整体二分+线段树合并做法，跑了 $6s$。一点前途都没有。

看了一眼题解。先建出来 Kruskal 重构树。对于每次询问二分答案，查询就是一段 dfn 区间的点是否向一段 dfn 区间的点有直接连边，线段树合并有直接连边的点，每次在线段树上区间查询即可。复杂度 $O(n\log^2 n)$，跑的很快。

B

合格考还是不太适合想题。这个题竟然没想到。

第一步转化是将求 $\prod \min(a_i,b_i)$ 的和转化为求满足 $x_i\leq \min(a_i,b_i)$ 的序列数量。这个是对 $\prod $ 常见的转化方式，把 $x_i$ 变成 $x_i$ 个 $1$ 相加，然后用乘法分配律在每一组中选择一项。这样之后，发现最后的选择 $a_i,b_i$ 的方式只和 $\sum x_i$ 有关，设 $sum x_i=X$，那么方案数就是 $\binom{X-1}{k-1}\binom{n-X+k-1}{k-1}\binom{m-X+k-1}{k-1}$。

上面式子第一项是分配 $x_i$，第二项是分配 $a_i-x_i$，第三项是分配 $b_i-x_i$。因为模数很小，所以可以直接用 Lucas 定理把组合数拆到每一位上。直接数位 dp 即可。记录 $dp_{p,0/1,0/1,0/1}$ 表示当前考虑到第 $p$ 位，是否顶上界，后面两个组合数是否产生借位的方案数，转移直接枚举这一位的值。复杂度 $O(Tmod\log_{mod}n)$。

7.3

梦熊 round 32

B

考虑拆成每个数的贡献，需要考虑每个数和两边的大小关系。发现需要关注的信息还是太多了，考虑进一步拆贡献，拆成每个数和左边数的贡献以及和右边数的贡献。

枚举每个数 $x$ 考虑，设 $dp_{u,i,0/1/2}$ 表示当前关心的数在 $u$ 子树内排第 $i$ 个，$x$ 关注的那边没有数或者有比它小的数或者有比它大的数的方案数。转移枚举转移进来的子树有多少个拓扑序在 $x$ 的前面，然后再讨论一下转移之后靠近 $x$ 的元素是原来的还是新进来的。每个的转移系数都是一堆组合数。如果新来的是原来的，那么 $v$ 子树的任意一个拓扑序都行。如果新来的是靠近 $x$ 的元素，那么需要求在 $v$ 子树内拓扑序排行第 $j$ 个的编号 $\leq x$ 的方案数。如果已经处理好了这个东西，那么类似树形背包可以 $O(n^2)$ 转移。这部分总复杂度 $O(n^3)$。

考虑预处理 $g_{u,i,j}$ 表示 $i$ 在 $u$ 子树内排 $j$ 的方案数。转移和 $dp$ 的转移是类似的，同样类似树形背包以组合数为系数转移，复杂度 $O(n^3)$，求前缀和之后就能得到需要的预处理数组。总时间复杂度 $O(n^3)$。

标签：赛前,log,训练,复杂度,位置,NOI2024,区间,考虑,dp
From： https://www.cnblogs.com/Harry27182/p/18322681