开始补 \(3\) 月的做题。
102. P7417
由于 \(f_G(a,b)\) 可以走重边，所以我们只关心奇最短路以及偶最短路。
判掉一下每个点只有奇数路径或偶数路径，即二分图，可以直接最短路树，在两题都需要特判掉。
本题的重点在于确认 \(G'\) 的结构。考虑 \((x_i,y_i)\) 为不同奇偶的最短路数对，要求 \(x_i<y_i\)。对于原图的 \((x_i,y_i)\)，将每个点拆成两个奇偶性的点之后跑 BFS 就可以 \(O(m)\) 求。
注意到相邻边的 \(x,y\) 都的差值都 \(\leq 1\)，否则可以更新掉。
考虑能得出这样的图的连边形态：
- \((x_i,y_i)\) 与 \((x_i-1,y_i-1)\) 相连。
- \((x_i,y_i)\) 与 \((x_i-1,y_i+1)\)，\((x_i+1,y_i-1)\) 相连。
- 注意到 \(x_i+1=y_i\) 的点可以直接连 \((y_i,y_i-1)=(x_i,y_i)\) 以及 \((x_i-1,x_i)\)。
考虑对原图按照 \((x_i+y_i)\) 为第一关键字，\(x_i\) 为第二关键字排序。那么将所有边定向，就是一个分层的好看的 \(\text{DAG}\)。考虑直接按照顺序贪心。令 \(cnt_{x,y}\) 表示 \((x,y)\) 的出现次数。
考虑怎么连前驱，可能的前驱有且只有两种：\((x-1,y-1)\) 和 \((x-1,y+1)\)。
注意到每层的连边形态都是若干条链，并且结尾如果为 \((x_i,x_i+1)\) 甚至可以互相连。
考虑怎么处理所有点对为 \((x_i,y_i)\) 的点。
- 若存在 \((x-1,y-1)\) 且不存在 \((x-1,y+1)\)，那么只能向上连。
- 若不存在 \((x-1,y-1)\) 且存在 \((x-1,y+1)\)，那么考虑这些点不仅需要往 \((x-1,y+1)\) 连边，还要往后面的 \((x+1,y-1)\) 连边。这个东西后效性很大，考虑怎么处理。考虑以前 \((x-1,y+1)\) 的连边的对象唯一，那么可以令 \(t\) 表示没有及时处理掉的，需要往后连的，那么关于现在就需要增加 \(\max(cnt_{x,y}-t,0)\) 往前连的边。考虑往后连的东西，\(x=y-1\) 时可以直接内部连，消掉，这样一定不劣，因为一次消了两个。否则只能往后连。
- 若两者都存在，考虑优先往前面匹配时不劣，然后是往上面连，最后才是连额外的东西。
用 \(\text{std::map}\) 随便维护下就 \(O(n\log n)\) 了。
103. P7418
现在这是一个存在性问题了。考虑：
- 连 \((x-1,y-1)\) 为向上。
- 连 \((x-1,y+1)\) 为向前。
- 连 \((x+1,y-1)\) 为向后。
那么一个点，要么有向上的，要么同时存在向前向后的。
同样考虑按照 \((x+y,x)\) 分层，考虑 dp。
我们发现往 \(x+y-2\) 的点连的限制很自由，但是同一层的连通性要求很强，所以要在 \((x,y)\) 这种链做死一点的 dp。
令 \(f_{x,y,p}\) 表示考虑到点对 \((x,y)\)，有 \(p\) 个点向后连边的合法方案数。且这 \(p\) 个点 不能 向上连的方案数（也就是说只能通过连前后来满足的有 \(p\) 个点）
考虑有 \(cnt\) 个 \((x,y)\)。
枚举 \(0\leq q\leq cnt-p\) 个点没有同时往前后连，只能往上。考虑往前的 \((x-1,y-1)\) 有 \(k\) 个。有以下贡献：
\[\sum_{q=0}^{cnt-p}\begin{pmatrix} cnt-p\\ q \end{pmatrix} (2^k-1)^{cnt-p}g_{x,y,q}\]其中 \(g_{x,y,q}\) 表示 \((x,y)\) 的点有 \(cnt-q\) 个点往前驱状态 \((x-1,y+1)\) 连边能连上的状态。
令 \(k\) 为 \((x-1,y+1)\) 的数量。
考虑怎么求 \(g_{x,y,p}\)。枚举 \(q\) 个 \((x-1,y+1)\) 的点到 \((x,y)\) 有边，那么有以下贡献：
\[\begin{pmatrix} cnt\\ p \end{pmatrix} \sum_{q=0}^{k}h_{k,q,p}f_{x-1,y+1,q}\]令 \(h_{i,j,k}\) 表示二分图连边方案数，满足：\(|L|=i,|R|=k\)，并且 \(L\) 中确定的 \(j\) 个点存在连边，\(R\) 中所有点都有连边的方案数。
可以使用连通图计数容斥的技巧。钦定 \(L\) 的 \(p\) 个点没有连边。考虑贡献系数：
\[\sum_{p=0}^{j}\begin{pmatrix} j\\ p \end{pmatrix}(-1)^{p}(2^{i-p}-1)^k\]\(h\) 可以 \(O(n^4)\) 预处理。
这样你就可以在正确的时间复杂度处理出 \(f_{x,y,i}\)。
考虑统计答案，如果将可能连边的连边，形成链，每一层就是若干条链，考虑在链尾计数保证不重不漏：
也就是考虑 不存在后继 \((x+1,y-1)\) 的所有点，进行统计。
注意到 \(x+1=y\) 时可以互相消作为向后连的点。
- 不满足 \(x+1=y\) 时考虑直接乘上 \(f_{x,y,0}\)。
否则，考虑向后连的就是互相连，考虑有 \(p\) 个点，那么这个等价于不存在孤立点，随便容斥下就行了。
总时间复杂度 \(O(n^4)\)。
104. CF1936D
考虑将 \(a\) 建立 \(\text{st}\) 表，视为区间的固定属性，就像定值电阻一样。
注意到 \(v\) 是定值，那么在满足条件的所有区间中，区间更短的权值一定不劣。由经典题目 P4435 可知，对于大区间 \([L,R]\)，跨过中点 \(\text{mid}\) 的所有区间 \([l,r]\)，维护前后缀 \(\text{OR}\) 和，对于一侧而言的值只有 \(O(\log V)\) 种。不同的 \(\text{OR}\) 值只有 \(O(\log^2V)\) 种。
考虑维护一个结构体，存着所有前缀 \(\text{OR}\)，后缀 \(\text{OR}\) 的（最大/最小位置，\(\text{OR}\) 值），以及在 \([L,R]\) 子区间的最小子区间权值。
这个东西可以线段树维护，合并结构体直接双指针遍历即可，这样可以保证不错过所有的 \(\text{OR}\) 和并且区间长度最小，这样求出来的最小值一定就是所有的最小值。
105. CF1784D
注意到一个子树的 winner 一定是 \(\min a_i\)。
考虑这个叶子是位置 \(i\)，那么把它放在第一个位置上考虑显然没影响。放到数列上就是：
\(a_1>a_2>\min(a_3,a_4)>\min(a_5,a_6,a_7,a_8)>\cdots>\min(a_{2^{(n-1)}+1},a_{2^{(n-1)}+2},\cdots,a_{2^n})\)。
那么等价于 \(a_1=i\)，求后面排列的方案使这个东西成立的方案数。
考虑值的角度，按顺序填。这个东西总共分成了 \(n+1\) 段。注意到 \(1\) 一定填到第 \(n+1\) 段，不然就寄了。因此考虑当前填了后 \(i\) 段，确定了前 \(j\) 小的数的方案数，哪些位置填了有影响，哪些位置填了没影响的位置是确定的。
随便 dp 下就过了吧。
106. CF1784C
注意到操作二只能用一次，那么它一定会在最后。
随便几把线段树二分贪一下就过了。
107. CF1574F
sb 诈骗题
考虑 任意一个非空子序列在 \(a\) 中的出现次数的最大值。这个东西就是某个元素在 \(a\) 中出现的最大次数。长度 \(\ge 2\) 时取出其中一个元素的次数，一定不小于它。
所以有 \(A_i\) 的出现次数 $\ge $ 某个元素的最大出现次数。
注意到 \(A\) 中存在重复元素时，某个元素的出现次数一定 \(>\) \(A\) 的出现次数，所以可以从元素之间的限制考虑。
对于一个观察到 \(A_i\) 的某个元素出现时，考察相邻两个元素 \(x,y\)，必须有在 \(a\) 中，\(xy\) 必须成对出现，将所有元素之间限制的边进行连边，每个连通块都必须是链。
那么 \(a\) 就是若干条链拼起来的。
直接 dp，链的大小种类数是 \(O(\sqrt n)\) 种的，进行 \(O(m\sqrt n)\) 的 dp 即可。
108. CF1879F
显然一个人会存活 \(f_i(x)=h_i\lceil\dfrac{a_i}{x}\rceil\) 轮，我们只关心次大值和最大值。显然我们对于一个 \(x\)，我们也只关心 \(f_i(x)\) 的最大和次大。
考虑对 \(a_i\) 排序。
考虑调和级数枚举，每次把 \(\lceil\dfrac{a_i}{x}\rceil\) 的放在一起求，符合条件的 \(x\) 显然是一段区间。这样需要快速求区间次大最大值，直接 st 表。
109. CF1864H
考虑经过 \(i\) 的概率为 \(f_i\)，答案即为 \(\sum_{i<n} f_i\)。
直接 \(n\leftarrow n-1\)。
考虑枚举 \(\times 2\) 共 \(0\leq L\leq\log n\) 次。
考虑每个操作序列都可以刻画成 \(L\) 维非负整数向量 \((a_0,a_1,a_2,\cdots,a_L)\)，使得 \(T+\sum_{i=0}^L a_i2^i=n-2^L\)，右边减去 \(2^L\) 是因为初始 \(x=1\)。
每个序列的权值应该为 \(2^{-(\sum a_i+L)}\)，其中 \(2^{-L}\) 可以最后统计，考虑将 \(a_i\) 拆成 \(b_{i,0\sim B=\log n}\)，每一位在 \(0/1\) 取代表该位二进制下的值。
所以只需要满足：
\[\sum_{i=0}^B 2^i\sum_{j=0}^{\min(L,i)} b_{j,j-i}=n \]注意到那个贡献系数可以拆到每一项相乘，也就是说某个数第 \(d\) 位取 \(1\) 会带来 \(\dfrac{1}{2^{2^{d}}}\) 的贡献，因此可以考虑，\(f_{i,k}\) 表示第 \(i\) 位 \(\sum b_{j,j-i}=k\) 的贡献和。
然后考虑从低到高数位 dp，\(dp_{i,j}\) 表示前 \(i\) 位，向后进 \(j\) 位的所有序列的贡献和。随便合并下就行了。
时间复杂度 \(O(\log^4n)\)。
110. 20240220 考试 T1
显然第一步要干的是把 \(m\) 的限制容斥成小于等于。
考虑特殊性质 A。将所有的 \(\delta_{i,j}\) 拉出来从小到大排序，考虑 \(w_{i,j}\) 怎么填。若当前考虑的 \(\delta_{i,j}\) 为最小值，则有 \(w_{i,j}=\delta_{i,j}\)；否则，考虑是否存在一个点 \(k\) 使得 \(\delta_{i,k}+\delta_{k,j}=\delta_{i,j}\)，若存在，\(H_{i,j}\) 不需要由原图中直接相连的边 \(w_{i,j}\) 来更新，取 \(w_{i,j}\ge \delta_{i,j}\) 即可，否则必须取等。容易 \(O(n^3)\) 实现，期望得分 \(32\)。
考虑特殊性质 B。注意到 \(0\) 边使得 \(1,2,\cdots,n\) 连通即可，那么它显然就是无向连通图计数，朴素实现 \(O(n^2)\) 即可。大概就是 \(f_n\) 表示 \(n\) 个点的联通图个数，\(g_n\) 表示 \(n\) 个点的完全图个数，然后容斥 \(1\) 所在的极大连通块大小。结合性质 A 期望得分 \(48\)。
在 \(m\geq \delta_{i,j}\ge 0\) 的一般情况中，注意到有 \(0\) 边会构成一堆团，考虑把这些团缩完之后跑特殊性质 A 的做法，注意此时连接团 \((x,y)\) 的边的重边数量为 \(\text{size}_x\times \text{size}_y\)，需要改写成 \(\min(w_{i,j})= \delta_{x,y}\)，要用一层容斥计算。
每个团内部边权值的情况显然就是性质 B。这堆东西乘起来就是答案。
时间复杂度 \(O(n^3)\)。
111. CF1609G
注意到差分单调，考虑当前新走到某一行或某一列的贡献是差分的值乘上接下来的路径长度，那么显然选差分值较小的乘上去最优。
所以每一步，都会选择差分值较小的走。
考虑将 \(a\) 视为插入点，而差分单调告诉我们互不干扰，所以可以将 \(a\) 在 \(b\) 的序列上二分查询决策点
难度全在代码实现细节上了。
112. CF1930G
难点在于刻画答案序列前缀 \(\max\) 的结构。
记录 \(mx_{u}=\max_{v\in\text{subtree}(u)} v\)，那么进入一个子树 \(u\) 再结束后的结尾要么不变要么被更新成 \(mx_u\)。
考虑一个节点 \(u\) 成为 \(\text{premax}\) 的判定条件：
- 所有祖先的标号一定更小，因为祖先一定在 \(u\) 之前。
- 所有 \(mx_v\ge u\) 的 \(v\)，如果不是 \(u\) 的祖先，那么一定还没有被访问过，因为不会回溯。
可以考虑对于一个点的所有子结点，按照 \(mx_v\) 进行排序，并且得到一个 \(\text{dfs}\) 序。
考虑 \(f_i\) 表示 \(i\) 作为 \(\text{premax}\) 结尾的所有序列，要求恰好以 \(i\) 为结尾的方案数。
由判定 2，按照 \(\text{dfs}\) 序跑 dp 一定是可以无后效的。
那么考虑 \(v\to u\) 转移成功的情况：
- 一定有 \(v<u\)。并且 \(v\) 的遍历顺序一定在 \(u\) 之前。换而言之，\(\text{dfn}_v<\text{dfn}_u\)。
- 若 \(\text{lca}(u,v)=v\)，即 \(v\) 是 \(u\) 的祖先，那么要求 \(v\to u\) 的路径上，恰好满足 \(v\) 是次大，\(u\) 是最大值。
- 若 \(\text{lca}(u,v)=d\ne v\)，那么一定有 \(d\) 关于 \(v\) 方向的子树 \(d'\) 已经遍历完毕，\(v\) 结尾一定是要求 \(mx_{d'}=v\)。考虑放在 \(d\) 上统计，对于每个除了下去的链的子树，能转移的一定是 \(\text{maxsubtree}\)。合适的转移顺序就是要求按照 \(mx_v\) 进行排序，顺势推下来就很自然。
能转移的点要么是祖先要么是子树 \(\max\)，令 \(p\) 为 \(1\to u\) 的路径的 \(\max\)，不含 \(u\)。
- \(p>u\) 时 \(f_u=0\)。
否则有 \(q\) 能转移当且仅当：
- \(q\in[p,u)\)。
- \(q\) 为 \(u\) 的祖先。
- \(q\) 为 \(u\) 祖先中某个儿子的 \(\text{maxsubtree}\)。
容易在 \(\text{dfs}\) 结束时撤销贡献，用树状数组维护。时间复杂度 \(O(n\log n)\)。
113. CF1270F
考虑 \(cnt_i\) 为前缀 \(1\) 个数。
令 \(d(cnt_r-cnt_{l-1})=r-l+1\)，考虑对 \(d\) 进行根号分治。
考虑有多少对 \(0\leq i<j\leq n\)，满足 \(d(cnt_j-cnt_i)=j-i\)。
- 对于 \(d\ge B\)，\(cnt_j-cnt_i\) 的值会很小，考虑对于每个 \(cnt_i\)，暴力移动 \(j\)，可以得到一段区间，随便算合法的。
- 对于 \(d<B\)，考虑对 $c_i=cnt_id-i $ 进行统计，求出相等数对即可，容易排序后求连续段。
精细实现可以 \(O(n\sqrt n)\)。
114. CF1815D
115. CF1815C
116. CF1948F
117. CF1609F
118. CF1948G
119. CF1770E
120. CF1770F
121. CF1904E
最长简单路径，不如直接说成连通块上两个点的距离，其中一个点是 \(x\)。
考虑用 dfs 序刻画 \(x\) 所在的连通块。这其实并不是连续的，对于每个 \(a_i\)，找出来它与 \(x\) 是否存在祖先关系，可以求出来 \(1/2\) 段 dfs 序区间，使得 \(x\) 不能到达。
这些区间取并之后（组成一堆连续段），就是 \(x\) 最终无法到达的 dfs 序区间。那么我们想要的，\(x\) 所在的连通块就可以通过剩下这些没有被染色的 dfs 序区间来刻画出来。显然，由于每个 \(a_i\) 贡献是 \(O(1)\) 个区间，我们可以暴力求出来所有的 \([l_i,r_i]\)（dfs 序区间）使得 \(x\) 可以到达。也就是，删除掉的区间形成的连续段，中间那些空隙就是可达的。
考虑一个经典结论：连通块 \(G\) 中离 \(u\) 最远的节点，记为集合 \(S\)，那么 \(G\) 任意一条直径的某个端点必然 \(\in S\)。
如果求出来了剩下这堆的区间构成的连通块的端点，那么我们显然就可以快速求出来答案。
考虑到，两个连通子图合并，构成新的直径时，显然只会从各自子图中的 \(2\) 个端点，总共 \(4\) 个端点中诞生这条直径的端点。这启发我们可以快速合并两个已知直径信息的子图。
回想到我们使用若干连续的 dfs 序区间来刻画，而且上面说的东西具有结合律，考虑线段树维护。具体地，线段树维护 \([l,r]\) 表示 dfs 序在 \([l,r]\) 中的所有的节点构成的子图，直径的两个端点以及长度。
查询的时候，求出来所有存活 dfs 序区间后直接暴力合并出来这个子图的直径即可。
每次合并子图需要求 \(\text{dis}(u,v)\)，用倍增求 \(\text{lca}\) 会很慢。此处使用 \(O(n\log n)-O(1)\) 求 \(\text{lca}\)，结合线段树的复杂度是 \(O(n\log n)\)。
标签：连边,cnt,Set,text,Solution,dfs,区间,考虑 From： https://www.cnblogs.com/nullptr-qwq/p/18236469