task15

[TOC]

1. 联合省选 2025 - 图排列 [E]

题面

有 $m$ 个数对 $(a_i,b_i)$，满足 $1\le a_i\le b_i\le n$，且不存在 $1\le i,j\le n$ 满足 $a_i<a_j<b_i<b_j$

有一个 $1\sim n$ 的排列 $p$，你会得到所有 $(p_{a_i},p_{b_i})$ 组成的可重集，求字典序最小的符合条件的 $p$

数据保证至少有一组解。

$1\le n\le10^5,1\le m\le2n$

题解

Sol

建成一张图之后，这个题目要做的事情就是让我们把这张图镶到一个圆上，使得所有点都在这个圆上，并且边在除端点处都不相交

那么对于一棵树的情况，我们随便定一个根，然后子树下去推，那么最后在根合并的时候就是把子树的序列和 $[u]$ 放在一起从小到大排序拼起来

对于图的情况，容易发现一个环只有两种顺序，而继续画一画就会发现一个点双一定是外面有一个环，中间是一个类似三角剖分的东西

那么我们建出圆方树，方点的转移和上面类似，圆点的转移就需要我们求出一个点双的哈密顿回路，注意到这是一个三角剖分，所以我们可以缩二度点，这样就能得到最外面的一层环，判断一下正反两种顺序哪个大即可

复杂度 $O(n\log n)$

---

2. 联合省选 2025 - 岁月 [E] ✔️

题面

给定一张 $n$ 个点 $m$ 条边的带权无向图 $G$，按照如下方式生成一个带权有向图 $G^\prime$：

• 对于 $G$ 中每条边 $(u_i,v_i)$，分别以 $\frac12$ 的概率独立决定 $G^\prime$ 中是否存在同权值的 $u\rightarrow v$ 和 $v\rightarrow u$ 的边

求 $G$ 的最小生成树权值等于 $G^\prime$ 中最小外向生成树的权值的概率，对 $10^9+7$ 取模

$T$ 组数据。

$1\le T\le 5,2\le n\le15,n-1\le m\le\frac12n(n-1)$

题解

Sol

首先考虑边权相等的情况怎么做。

那么我们需要计算的就是 $G^\prime$ 中存在外向生成树的概率，注意到这相当于缩完点之后必须恰好有一个入度为 0 的 scc

对入度为 0 的 scc 容斥，令 $f_S$ 为只考虑 $S$ 内部的边，$S$ 强连通的概率，求 $f_S$ 的时候需要我们对入度为 $0$ 的 scc 容斥，具体地，我们将 $S$ 划分为若干个集合 $T_1,T_2,\cdots,T_k,U$，其中 $T_1,T_2,\cdots,T_K$ 分别为我们钦定出来的若干个入度为 0 的 scc，最后我们需要额外算上的贡献就是 $T_i\rightarrow T_j$ 和 $U\rightarrow T_i$，我们需要乘上一个概率，让这些边不存在，并乘上 $(-1)^{k}$ 的贡献系数

$T_1,T_2,\cdots,T_k$ 的部分可以再设一个状态 $g_T$，表示当前选的 $T_i$ 的并集为 $T$

最后我们要计算的是恰好有一个入度为 0 的 scc 的概率，那么算一下容斥系数，我们钦定了 $i$ 个集合的话，需要贡献 $(-1)^{i+1}i$ 的系数，这个可以转化成从中选择一个 scc，那么也是可以 dp 在 $O(3^n)$ 内解决的

因此我们在 $O(3^n)$ 的时间内解决了边权全相等的问题

接下来考虑边权不相等的情况。

考虑按边权分层，那么考虑到边权为 $w$ 的时候，我们可以按照 $\le w$ 的所有边划分出来的连通性把问题拆开

此时对于一个子问题内部，我们会用 $<w$ 的边提前缩好了一些连通块，而任意一个合法最小外向树，必须是将这些连通块串成一棵外向树，我们就要计数这样的方案数

对每个连通块定义 $V_i,W_i$，分别表示这个连通块的总点集，和连通块内部形成外向树，可能的树根，那么一条连通块 $c$ 到连通块 $d$ 的有向边有效当且仅当其是从 $V_c$ 连向 $W_d$

类似地定义 $f_S$，表示 $S$ 中的点涉及到的连通块，其 $W_i$ 恰好为 $V_i\cap S$，现在将这些连通块连成一个 scc 的概率（只考虑边权为 $w$ 的边的概率贡献，不考虑 $<w$ 的），以及 $g_S$

转移是类似的，多了一些边权上的讨论

但是注意到最后我们为了下一层的转移，需要对每个 $S$，求出整个连通块，树根恰好为 $S$ 的概率，这个需要再进行一些处理

具体地，还是考虑容斥入度为 0 的 scc，那么我们需要枚举一个 $S$，再枚举一个钦定的若干个 scc $T_1,T_2,\cdots,T_k$，再枚举剩下部分的 $W$ 的并集 $U$，这样复杂度是 $O(4^n)$ 的

考虑首先枚举 $S\cup T$ 和 $U$，将贡献放到 $S\cup T$ 上，然后再从 $S\cup T$ 贡献到 $S$，这样复杂度就降到了 $O(3^n)$

因此总复杂度就是 $O(T3^n)$ 的

---

3. 联合省选 2025 - 封印 [E] ✔️

题面

给定一个长为 $n$ 的序列 $a_1,a_2,\cdots,a_n$，你可以进行若干次如下操作：

• 选择某个严格前缀最大值 $a_s$，如果 $a_s\neq 1$，则在序列末尾插入 $a_s$
• 将 $a_s$ 及之前的所有元素删除

求能得到的本质不同非空序列数量，对 $998244353$ 取模

$1\le T\le10,1\le n,m\le2500,1\le a_i\le m$

题解

Sol

困难的。

首先考虑给这个操作找一个好看点的形式，我们把 $a$ 重复无穷多遍，每次给所有元素 $-1$，如 $[1,3,2,3,4]$ 就会变成 $[1,3,2,3,4,0,2,1,2,3,-1,1,0,1,2,-2,0,-1,0,1,-3,-1,-2,-1,0,\cdots]$

那么我们操作能得到的东西就是其中某一个长为 $n$ 的子区间的子序列，具体地，如果我们选择的区间为 $[p:p+n-1]$，那么我们的子序列会有如下的限制：

• 设子序列的下标为 $k_1,k_2,\cdots,k_r$，那么首先 $a_{k_i}>0$
• 对于所有 $2\le i\le k$ 应满足 $a_{k_i}>\max(a[k_{i-1}+1:k_i-1])$，并且 $k_1>\max(a[p:k_1-1])$
• $\max(a[k_r+1:p+n-1])\le 0$
• 特别地，如果 $p\le n$，那么强制要求 $a[p:n]$ 必须都在子序列中

这些都是手玩从操作规则推出的

那么我们需要对所有这样的子序列，计数本质不同数量，这个还是不太能做，我们需要继续找一找性质

如果你把样例手玩一下，把所有子序列都写出来，发现这个东西好像很少会有重复

实际上，对于绝大部分子序列，我们最多有一种 $k$，将其选出，具体地，这个事情对所有 $a_{k_1}>1$ 的子序列都成立，证明如下：

• 如果某个子序列 $b$ 在两个位置出现，那么取 $b$ 第一次出现时的 $[p_1:p_1+n-1]$，考察怎么样让 $b$ 在后面出现
• 注意到对于每个 $k$，如果我们固定下一个要求的值，那么下一个 $k$ 的位置也是固定的
• 那么考察此时 $b$ 中的最大值 $mx$，不妨设有 $cnt$ 个，那么 $p_1$ 之后一定只有这 $cnt$ 个 $mx$ 了，因此 $p_1$ 往后挪的过程中，不能删除掉任意一个 $mx$
• 而考虑 $a_{k_1}>1$，也就是说我们只要把 $k_1$ 删掉之后，后面就会多一个 $>0$ 的数，那就一直无法选上，因此存在一种合法的挪动 $p$ 的方式，使得其能够选出这个子序列

那么对于一个 $k$，我们需要限定一个 $p$ 唯一统计到，那么我们对于一个 $[p:p+n-1]$，我们强制其必须使用到这个区间第一个 $\ge2$ 位置前的所有 $1$，这样不论 $a_{k_1}$ 是否为 $1$ 都会恰好在一个位置统计到

我们就可以写出一个暴力了，对这个长为 $nm$ 的数组，每个长为 $n$ 的子区间都做一遍这个子序列数量统计，可以用单调栈优化到 $O(n)$，总复杂度 $O(n^2m)$

考虑优化到 $O(nm)$，首先前 $n$ 个区间，和 $a_p=1$ 的区间比较特殊，但是这样的区间只有 $O(n+m)$ 个，可以暴力

对于剩下的部分，如果我们直接在 $[n+1:3n]$ 这个段上考虑，那么我们每个 $k$ 就能选的次数就是 $\min a_{k_i}$，再考虑一些开头和结尾的限制

那么考虑枚举这个最小值 $x$，我们可以对 $n$ 种 $[p:p+n-1]$ 的选法一起做，对前面的数求出 $f_i$ 表示 $i$ 到 $x$ 有多少种走法，对后面的数求出 $g_i$ 表示 $x$ 到 $i$ 有多少种走法，统计答案就是枚举一个 $p$，然后把某个 $f$ 和 $g$ 乘起来，再乘上一些次数的计算

可以做到总复杂度 $O((n+m)n)$

---

4. QOJ10103 - Quad Kingdoms Chess 2 [E]

题面

有两个人 X 和 Y，X 手中有 $n+k$ 张牌，其中有 $n$ 张牌上面分别写着 $a_1,a_2,\cdots,a_n$，剩下 $k$ 张牌是炸弹牌，Y 手中有 $m$ 张牌，上面分别写着 $b_1,b_2,\cdots,b_m$

X 和 Y 会把这些牌从随机打乱自己手中的牌，然后开始决斗，决斗每人会出当前手中第一张牌：

• 如果有炸弹牌，或者两张牌上的数字相等，则两人的牌均被击败，两人分别出手中下一张牌
• 否则数字小的一方的被击败，需要出自己手中下一张牌

先出完牌的人负，两人同时出完则视为平局

你需要求出 $P_X,P_Y,P_=$，分别表示 X 胜的概率，Y 胜的概率，和两个人同时出完牌的概率，对 $998244353$ 取模

$1\le n,m\le1000,0\le k\le20$

题解

Sol

首先考虑 $k=0$ 怎么做。

那么不妨考虑两人手里的最大值 $mx$，如果两边 $mx$ 数量不相等那么一定是 $mx$ 多的一方赢

如果相等的话，这些 $mx$ 一定配对消除，那么我们就把原问题拆成了一些子问题，后面有 $(mx,mx)$ 的子问题可以随便处置，最后一个没有 $(mx,mx)$ 的子问题则还是一样的

那么再考虑有炸弹牌的情况。

注意到我们可以只考虑 X 赢或者平手的情况，Y 赢的情况可以减出来。

记炸弹牌为 $\times$，首先把炸弹牌炸掉的牌全列出来，形成若干个 $(?,\times)$ 的对，那么还是从大到小填数，考虑填一个数 $v$ 的时候会发生什么

那么当前会有一些 $(?,\times)$ 的对，有一些 $(>v,\times)$ 的对，以及有一些只有一个 $\times$ 的位置（即最后 X 赢了手里剩下的炸弹）

首先我们会把若干个 $(?,\times)$ 填成 $(v,\times)$，接下来我们需要填一些 $v$ 在段内，那么我们每个段会填两种东西，一种是一个配对的 $(v,v)$，表示这两张 $v$ 最后一起消去了，或者填单独的 $v$，表示这个 $v$ 没有和其他的 $v$ 一起消去

那么 $(v,\times),(?,\times),(>v,\times)$ 这三种段都是可以随便填 $(v,v)$ 的，填完 $(v,v)$ 后，$(v,v)$ 前面的部分就可以随便填 $<v$ 的数了

而单独的 $v$ 相当于影响两个人在这个段内的胜负，而段对胜负的要求，相当于是 $(v,\times),(?,\times)$ 要求该段内两个人 $v$ 的数量必须相等，否则无法让它们匹配，而 $(>v,\times)$ 要求该段内 X 的 $v$ 数量不小于 Y 的 $v$ 数量，也就是说我们可以枚举向多少个 $(>v,\times)$ 的对里插入了多余的 $v$，插入完之后，这个 $v$ 后面也是随意插 $v$ 的段

上述是大概的想法，接下来整体描述一下做法：

从大到小填数，令 $dp_{v,x,y,0/1}$，表示当前填到了值 $v$，有 $x$ 个 $(?,\times)$ 的段，有 $y$ 个 $(>v,\times)$ 的段还未分出胜负，最后一个段是 X 赢/平局 的概率

此时除了这 $x+y+0/1$ 个段之外，其他的段都是随便填 $\le v$ 的数，这样的段数量我们可以通过 $>v$ 的数个数和 $k$ 之类的东西算出

转移的时候我们如下东西：

• $a$，表示有多少个 $(?,\times)$ 被填成了 $(v,\times)$
• $b,b^\prime$，有多少个 $(>v,\times)$ 的段中，X 填入了更多的 $v$，最后一个段特殊枚举
• $c$，表示我们一共填入了多少对配对的 $(v,v)$

转移的话，需要注意的是 $b$ 枚举的段会多产生一个能随意填入 $v$ 的段，把各种乱七八糟的系数都算一下可以做到 $O(1)$ 转移

初值的话，枚举有多少炸弹牌被使用了，如果使用了 $k$ 个就是 $dp_{A,k,0,1}\leftarrow 1$，否则使用了 $i$ 个，我们可以视作第 $i+1$ 个炸弹是 $(\infty,\times)$，就是 $dp_{A,i,1,0}\leftarrow1$

总复杂度 $O(nk^4)$

---

5. QOJ10100 - Exchanging Kubic 3 [E]

题面

给定一个长为 $n$ 的数组 $a_1,a_2,\cdots,a_n$，每次你可以选择 $i,j$，使得 $|i-j|=1$ 且 $a_i\ge0$，然后执行 $a_j\leftarrow a_j+a_i,a_i\leftarrow0$

求让所有 $a_i\ge0$ 的最小步数，或者判断不可能

$1\le n\le5\times10^5,|a_i|\le10^9$

题解

Sol

无解是直接判一下总和 $<0$。

取一下前缀和，操作相当于选择一个 $s_{i-1}\le s_i$，然后执行 $s_{i-1}\leftarrow s_i$ 或 $s_i\leftarrow s_{i-1}$，最后我们的目标是让 $s_i$ 递增

注意到我们执行的是赋值的操作，那么对于任意 $s_i$，我们找到所有被赋值成 $s_i$ 的位置，要么最后被赋值成 $s_i$ 的位置不存在，要么其形成一个包含 $i$ 的区间（如果区间不包含 $i$ 的话一定不优）

那么我们根据这个不变的 $s_i$ 位置设状态，就可以列出转移方程：

$$f_i\leftarrow f_j+i-j-1+\sum_{x=j+1}^k[b_x<b_j]+\sum_{x=k+1}^{i-1}[b_x>b_i]$$

其中要求 $a_j\le a_i$，这样复杂度是 $O(n^3)$ 的

那么我们按照 $a$ 的大小从小到大扫，维护一个 $g_k$ 表示所有中间点选在 $k$ 的转移最小值，那么枚举到一个 $i$ 的时候，我们需要干如下两件事情：

$$f_i\leftarrow g_k+2(i-k-1)-(tcnt_{i-1}-tcnt_k),&[k\in [0,i-1)]\\g_k\leftarrow f_i+k-i+cnt_k-cnt_i,&[k\in [i,n]]$$

其中 $cnt_i$ 表示前缀 $<a_i$ 的数量，$tcnt_i$ 表示前缀 $\le a_i$ 的数量，那么复杂度就降到了 $O(n^2)$

将上述两个操作用线段树优化，我们需要支持如下的事情：

• 将区间 $g_k$ 的值对 $k+cnt_k+C$ 取 $\min$
• 区间加 $cnt,tcnt$
• 求区间 $g_k-2k+tcnt_k$ 的最小值

这个可以通过线段树上打 tag 维护，复杂度 $O(n\log n)$

---

6. AGC015F - Kenus the Ancient Greek [E]

题面

对于非负整数 $a,b$，定义 $f(a,b)$ 如下：

• $f(a,b)=f(b,a)$
• $f(0,a)=0$
• 如果 $a>0$ 且 $a\le b$，则 $f(a,b)=f(b\bmod a,a)+1$

$q$ 组询问，每次询问给定 $X,Y$，求 $1\le x\le X,1\le y\le Y$ 的 $f(x,y)$ 最大值，并计数有多少对 $(x,y)$ 得到了这个最大值，对 $10^9+7$ 取模

$1\le q\le3\times10^5,1\le X,Y\le10^{18}$

题解

Sol

这个问题看起来很不可做。但是我们可以先从第一问进行入手。

我们首先自动只保留 $a\le b$ 的点，那么首先注意到所有 $(a,b)$ 状态的前驱都是唯一的，也就是说这形成了一棵类似树一样的结构

我们从 $(1,2)$ 开始每次扩展，那么如果想要操作步数最多的话就是每次令 $(a,b)$ 变成 $(b,a+b)$，这样得到的就是斐波那契数，那么根据经典结论可知答案量级是 $O(\log V)$ 的，称这个值为 $k$

那么考虑计数，一个暴力就是我们当前有一个 $(a,b,stp)$，我们每次进行如下两种操作之一：

• A 操作：$(a,b,stp)\leftarrow(a,a+b,stp)$
• B 操作：$(a,b,stp)\leftarrow(b,a+b,stp+1)$

我们最后计数的就是得到的 $stp=k$

定义 $F_0=0,F_1=1,F_n=F_{n-1}+F_{n-2}$，原本我们的最优解得到的是 $(F_{k+1},F_{k+2})$，如果一开始我们是从 $(0,2)$ 出发，最后得到的就至少是 $(2F_{k+1},2F_{k+2})$，而这个对位大于 $(F_{k+2},F_{k+3})$，那么此时 $k$ 最大的性质就被打破了

也就是说我们起始的节点一定是 $(1,2,1)$。

从这里已经可以初见端倪了，我们可以发现我们有可能进行不了很多次 A 操作。

但是最后一次 B 操作之后可以进行很多很多次 A 操作，那么我们特殊处理这部分。

具体地，如果我们在最后一次 B 操作之前，进行了两次 A 操作，那么我们只要说明，在除了这两次操作之外没有其它 A 操作的情况下，数已经过大了即可

设这两次 A 操作之前数对为 $(a,b)$，这两次之间隔了 $u$ 次 B 操作，那么在经过第二次 A 操作之后，我们再做一次 B 操作，得到的情况会是（规定 $F_{-1}=1$ ）：

$$(a,b)\rightarrow(a,a+b)\rightarrow(F_{u-1}a+F_{u}(a+b),F_ua+F_{u+1}(a+b))\\=(F_{u+1}a+F_ub,F_{u+2}a+F_{u+1}b)\rightarrow(F_{u+1}a+F_ub,F_{u+3}a+F_{u+2}b)\\\rightarrow(F_{u+3}a+F_{u+2}b,(F_{u+1}+F_{u+3})a+(F_u+F_{u+2})b)$$

而此时我们在 $(a,b)$ 上进行了 $u+1$ 次 B 操作，如果我们在 $(a,b)$ 上直接进行 $u+2$ 次 B 操作得到的值比这个值对位小，那么后面我们一直做 B 操作，由于 $k$ 的最大性，说明这种情况不需要考虑

$u+2$ 次 B 操作后会得到 $(F_{u+1}a+F_{u+2}b,F_{u+2}a+F_{u+3}b)$，左边显然小于，对右边作差，得到 $2F_{u+1}a+(F_u-F_{u+1})b$，重新整理得到 $F_{u+1}(2a-b)+F_ub$，由于 $(a,b)$ 是斐波那契数，所以 $2a-b\ge0$，因此该式 $\ge0$

那么我们只需要考虑除了最后一次 B 操作之外，只进行了一步 A 操作的数对，那么直接爆搜算方案数即可，复杂度 $O(\log V)$

---

7. CF1787I - Treasure Hunt [E] ⭐

题面

对于一个序列 $b_1,b_2,\cdots,b_c$，定义 $f(b)$ 为：最大的 $\sum_{i=1}^qb_i+\sum_{i=s}^tb_i$，其中 $q,s,t$ 都是整数（可以为负），满足 $s>q$ 或 $t\le q$，并且如果 $i<1$ 或 $i>c$ 我们认为 $b_i=0$，并且求和下指标大于上指标我们也认为是 $0$

给定长为 $n$ 的序列 $a_1,a_2,\cdots,a_n$，求 $\sum_{1\le l\le r\le n}f(a[l:r])$，对 $998244353$ 取模

$1\le n\le10^6,|a_i|\le10^6$

题解

Sol

注意到那个乱七八糟的东西就是区间最大前缀和加上区间最大子段和，非常弱智。

区间最大前缀和是好求的，直接建笛卡尔树即可

考虑如何求区间最大子段和之和。

Flamire 做法

分治。

当前区间是 $[L,R]$，处理跨过分治端点 $M$ 的贡献，那么答案形式就应该是 $\max(lans,rans,lsuf+rpre)$

此时如果我们假定 $lans\ge rans$，那么讨论一下 $rpre$ 和 $lans-lsuf$ 的大小，进行一个二分，可以 $O(\log n)$ 定位到分界点，那么就可以在 $O(n\log^2n)$ 内的时间计算出答案

但是这还不够优。

观察一下性质：对于一个序列，我们往右边插入一个数，那么最大子段和的左右端点一定都会向右移动，这个可以通过简单分类讨论得到

也就是说，我们固定了一个左端点 $l$，那么 $r$ 从 $M+1\rightarrow R$ 的过程中一定是左边一段取到 $lans$，中间一段取到 $lsuf+rpre$，右边一段取到 $rans$，我们只要找到这个分界点即可

而 $l$ 从 $M\rightarrow L$ 的过程中，我们每次往左边插入一个数，那么最大子段和的左右端点一定都会向左一定，也就是说这两个分界点都一定是单调向左的

那么我们就可以 $O(R-L)$ 计算一个区间的答案，总复杂度 $O(n\log n)$

线性做法

$l$ 从大到小扫描线，考虑此时每个 $r$ 的最大子段和的结构。

求出前缀和 $s$，那么我们就是要选择 $l-1\le x\le y\le r$ 使得 $s_y-s_x$ 最大，我们把它改成 $[l,r]$

那么考虑加一个 $s_l$ 的影响：

• $s_l>s_{l+1}$，那么右边的任何东西都不会改变 $x$ 的选择，去选成 $x=l$
• $s_l\le s_{l+1}$，那么右边所有满足 $s_x\ge s_l$ 的 $x$ 会改成选择 $x=l$，而一个可以注意到的事情就是我们把每个 $r$ 的 $(x,y)$ 对写出来，$s_x$ 一定是递增的，这个可以通过上面的结论推出，也就是说我们维护一个 $x$ 的单调栈，那么每次就是把前面的一些段改成 $x$

那么此时考虑 $y$ 的选择，一段恒定的 $x$ 内的 $y$ 一定是选择前缀最大值，那么我们对每段 $x$ 再开一个单调栈，维护所有 $y$ 的取值，那么合并 $x$ 段的时候我们使用链表，然后往前考虑单调栈内 $y$ 的弹出

这样复杂度是 $O(n)$ 的

---

8. CF1458E - Nim Shortcuts [S]

题面

有两堆石子 $a,b$，两个人轮流操作，每人每次会从一堆中取出任意堆石子，不能操作者负

同时，还额外有 $n$ 个位置 $(x_i,y_i)$，如果一个人即将操作，并且当前 $a=x_i,b=y_i$，那么他也会直接输掉

现在有 $m$ 次询问，每次给定一个初始局面 $(u_i,v_i)$，查询先手胜还是后手胜

$1\le n,m\le10^5,0\le x_i,y_i,u_i,v_i\le10^9$

题解

Sol

考虑画到一个矩形上，首先 $(0,0)$ 和所有 $(x_i,y_i)$ 是负，那么会推出来同行同列的位置都是胜

考虑从上到下扫 $x$ 推理：我们每次维护一个当前所有 $y_i$ 的集合，每次选出这个集合的 mex，然后判断一下 $mex$ 是否小于当前行 $y$ 最小的负位置，如果是把 $(x,mex)$ 判定为负，然后加入 $y_i$ 的集合

由于值域是 $10^9$，所以需要使用连续段优化，复杂度 $O(n\log n)$

---

9. CF1566H - Xor-quiz [E]

题面

给定一个 $c$，有一个均匀随机生成的元素为 $[1,c]$ 的集合 $A$，现在你已知 $|A|=n$

你可以进行一次询问，一次询问给出 $k$ 个 $[1,c]$ 内的整数 $q_1,q_2,\cdots,q_k$，对每个 $q_i$，你会知道所有 $x\in A$ 且 $\gcd(x,y)=1$ 的 $x$ 的异或和

你需要保证 $k\le\lceil0.65c\rceil$，还原出一个集合 $A^\prime$，使得 $|A^\prime|=n$ 且 $A$ 和 $A^\prime$ 在所有 $c$ 种可能的询问上都是一样的

$100\le c\le10^6,0\le n\le c$

题解

Sol

神经病。

我们可以把 $\mu\neq0$ 的数全问一遍，这样会问 $6/\pi^2$ 次，低于 $\lceil0.65c\rceil$

然后经过一些异或我们可以得到对每个 $\mu(i)\neq0$ 的数 $i$ 得到 $w_i$ 表示 $A$ 中所有包含质因子恰为 $i$ 这个集合的数的异或和

那么我们就是要对每个 $i$ 构造一个集合，使得它的异或和为 $w_i$，且所有 $i$ 的集合总大小加起来 $=n$

注意到 $n$ 的大小一定是在 $c/2$ 附近，那么我们对每个 $i$，建线性基然后分类讨论一下自由元个数，如果自由元个数 $\le7$ 我们就暴力枚举 $128$ 种情况，否则我们随机 $128$ 组，把大小拿出来跑背包用 bitset 优化

是对的。

---

10. AGC052D - Equal LIS [E] ⭐

题面

给定一个 $1\sim n$ 的排列 $p$，求是否能将 $a$ 分为两个非空的子序列 $u,v$，使得 $u$ 和 $v$ 的 LIS 长度相等

$1\le n\le2\times10^5$

题解

Sol

太恐怖了啊。

Flamire 思路

这种题一种思路是考虑有哪些情况显然可以有解，不断筛选，最后得到一个判定条件

那么首先注意到我们一种策略是从前往后选数，那么每次我们左边的 LIS 会 $+1$ 或不变，右边的 LIS 会 $-1$ 或不变，构造不出来的情况就是左边的 LIS 为 $k$，右边的 LIS 为 $k+1$，向右挪动 $1$ 后左边为 $k+1$，右边为 $k$，设这一步挪动的元素为 $p$

此时我们可以得到一些性质：左边的 LIS 为 $k$，且存在一个长为 $k$ 的 LIS 能拼上 $a_p$，右边同理，这也就意味着我们整体的 LIS 为 $2k+1$，且 $p$ 为必经点

同时我们也可以对值域进行一个类似的过程，我们也能得到下边上边的 LIS 均为 $k$

画到二维平面上，按 $(p,a_p)$ 把平面划分为四个象限，那么我们得到的条件就是一二，二三，三四，四一象限内的 LIS 都 $=k$

那么我们找出一三象限内长为 $k$ 的 LIS，如果除了这个 LIS 之外一三象限还有其它元素，不妨设是一象限，且这个元素为 $x$，那么我们可以令 $u$ 为一象限内所有点去掉 $x$，并上 $a_p$，此时 $u$ 的 LIS $=k+1$，外部 $v$ 的 LIS 是 $k+1$，因为存在三象限并上 $x$ 的选法，而剩下的 LIS 一定都 $\le k+1$，那么这种就是可以构造的

所以现在一三象限除了一个长为 $k$ 的上升序列之外不能有其它元素

但是这样还是有可能构造出来解。比如 1 2 4 5 6 7 3 8

也就是说我们可以选择一个三四一/三二一象限的子序列

但是具体地，我们取一个长为 $k+1$ 的上升序列，满足其至少存在一段位置不属于整体 LIS

如果我们保留了恰好 $k+1$ 个整体 LIS 内的点，并且这段点在整体 LIS 中的位置是一段区间，那么可以说明这个东西的 LIS 一定恰好 $=k+1$，因为想要 $>k+1$ 只能是三四一/三二一象限的上升子序列，而如果这些子序列 $>k+1$ 就违反了整体 LIS 的最长性

那么我们找到中间这个不属于的段最短的上升子序列，我们取一个最长的整体 LIS 前缀使得其仍然能拼上，然后取 $k-len$ 个整体 LIS 的后缀，由于这个段是最短的，可以发现这样的 LIS 一定 $=k+1$

也就是说，最后无解的条件就是 LIS 为奇数，且我们取任意一条 LIS，所有 $\ge k+1$ 的上升 LIS 都完全被这个 LIS 包含

题解思路

上面那个想法其实效率很低。

考虑一种刻画 LIS 的方式：令 $f(i)$ 表示以 $a_i$ 结尾的 LIS，那么任意一个 LIS 一定在 $f(i)$ 上也是严格递增的，并且 $f(i)$ 的值域有一些限制

一件显然的事情是任意一条 LIS 上的 $f(i)$ 一定是 $1,2,3,\cdots$ 排下去的

具体地，我们求出原来的 LIS，如果其长度为 $2k$，那么我们把所有 $f(i)\le k$ 的位置选出作为一个子序列，剩下的作为另一个子序列，此时两边都至少包含 $k$ 个 LIS 中的元素，而 $f(i)$ 种类数又 $=k$，所以 LIS $=k$

那么偶数就是可以构造的。

考虑 LIS 长度为 $2k+1$ 的情况，此时如果我们存在一个长为 $k+1$ 的子序列 $i_1,i_2,\cdots,i_{k+1}$ 满足其至少存在一个位置 $x$ 不属于原来的 LIS，那么我们可以如下构造：

• 对于所有 $i_j\neq x$，把所有 $f(t)=f(i_j)$ 的 $t$ 放入第一个子序列
• 将 $x$ 放入第一个子序列
• 对于其余所有元素，放入第二个子序列

此时两个子序列的 $f$ 种类数都是 $k+1$，而第一个子序列包含一个长为 $k+1$ 的上升子序列，第二个子序列至少包含整体 LIS 的 $k+1$ 个元素，因此构造成立

否则所有长为 $k+1$ 的子序列都一定在长为 $2k+1$ 的 LIS 内，而两边的 LIS 至少要 $\ge k+1$，因此无法选出

---

11. AGC016F - Games on DAG [E]

题面

给定 $n$ 个点 $m$ 条边的 DAG，保证 $1,2,\cdots,n$ 是合法的拓扑序

两个人在这个上面玩游戏，初始节点 $1,2$ 上分别有一个棋子，两个人轮流操作，每次选定一个棋子将其移动一步

现在从这个边集中保留一个子集，求所有有多少边集的子集会使先手必胜，对 $10^9+7$ 取模

$2\le n\le15,1\le m\le\frac12n(n-1)$

题解

Sol

题目问的就是 $\text{SG}(1)=\text{SG}(2)$ 的方案数

可以尝试爆搜 mex，但是状态数是 $\text{Bell}(n)$ 的，稍微有点大。

考虑按 mex 的值加数，可以发现我们并不关心 mex 的值具体是多少，令 $f_S$ 表示当前考虑完了某个 mex 的前缀，当前 $S$ 内的点已经被赋上了 mex，剩下的点 mex 更大，并且我们已经保证了剩下的点连向每种小值都至少有一条边

转移就是再枚举当前考虑的 mex 的点的集合 $T$，设 $S\cup T$ 的补为 $U$，那么我们需要处理的边有：

• $T$ 内部，边都不能存在
• $U\rightarrow T$，每个点至少存在一条出边
• $T\rightarrow U$，边随意

总复杂度可以做到 $O(n3^n)$ 或 $O(3^n)$

---

12. CF1666A - Admissible Map [E/K] ✔️

题面

给定一个长为 $n$ 的由 LRUD 组成的字符串 $s$

定义一个 LRUD 的方向矩阵是 admissible 的当且仅当其所有方向连出来的图没有连到外面的边，并且内部的边形成若干个环

你需要统计有多少子串，可以通过一个 admissible 的方向矩形，把每一行依次拼接得到

$1\le n\le20000$

加强版：$1\le n\le10^5$

题解

Sol

很厉害的题。

直接做不是很好得到低于 $n^2$ 的复杂度，考虑分析一些性质：

可以发现任意一个包含 UD 的串最多只有一种行长让其合法，具体地，这个合法的行长可以通过讨论直接得到：

• 如果 $s_i=\texttt{L}/\texttt{U}$，那么一定不可行
• 如果 $s_i=\texttt{R}$，如果 $s_{i+1}=\texttt{L}$，那么我们到 $i+2$ 接着 check，否则说明必须有一个 $\texttt{U}$ 指向 $s_i$，而这个 $\texttt{U}$ 必须是 $s_i$ 后面的第一个 $\texttt{U}$
• 如果 $s_i=\texttt{D}$，那么我们找到接下来的一段 $\texttt{LLL…LL}$，那么必须有一个 $\texttt{U}$ 指向最后一个 $\texttt{L}$，同理也必须是第一个 $\texttt{U}$

那么我们特判全是 $\texttt{RL}$ 的串，对于原串的每一个 $l$，可以求出其如果想合法需要的行长，那么接下来的事情就是如何判断合法

一个暴力是我们可以依次扫每一行，然后进行一些边界上的 check，中间的部分用哈希维护入度和出度，这样我们就可以做到在 $O(\frac{n}{len})$ 的时间复杂度内 check 一个左端点

但是考虑我们的 check 可以直接从上一个推过来，所以我们可以同时对于一种 $len$ 做到 $O(n)$ check 所有的左端点

根号分治一下，可以做到总复杂度 $O(n\sqrt n)$

---

12. NOI2023 - 深搜 [E]

题面

给定一棵 $n$ 个点的树 $T$，以及 $m$ 条非树边，它们共同形成一张无向图 $G$，保证这 $n+m-1$ 条边互不相同

给定一个大小为 $k$ 的集合 $S$，求有多少保留这 $m$ 条非树边的一个子集的方式，使得剩下的图 $G^\prime$ 中，存在一个 $s\in S$ 使得 $T$ 是以 $s$ 为根的一棵合法的 dfs 树

答案对 $10^9+7$ 取模

$1\le n,m\le5\times10^5$

题解

Sol

合法的 dfs 树即为没有横叉边

考虑容斥，我们枚举一个集合然后判断其全部合法的方案数

那么一定是一些边必须不选，剩下的边可选可不选

设我们选定的点集是 $T$，如果我们把 $T$ 的虚树建出来，所有可选可不选的边即为所有在虚树某条边内部的边，以及我们把 $T$ 虚树上的所有边断掉之后，每个子树以 $T$ 中的点为根的祖孙边数量

预处理 $f_i$ 表示 $i$ 子树内以 $i$ 为根时返祖边数量，$g_i$ 表示子树外类似的事情

对着虚树 dp，令 $dp_u$ 表示虚树内存在 $u$ 这个节点，子树内的边方案数，转移的话我们再额外维护一个转移系数 $cdp_v$，计算从 $dp_v$ 转移过来的时候会多乘多少贡献，最后我们在虚树的根处统计贡献

到一个点 $u$ 的时候，我们需要做如下两个事情：

• 求出 $dp_u$，这部分就是跑一个大小上限为 $3$ 的背包，为 $3$ 是因为根处如果有 $=2$ 棵子树的话，我们需要额外处理一些横叉边的贡献
• 对子树内的点的 $cdp$ 进行一些更新，具体地我们需要加上 lca 为 $u$ 的非树边的影响（实际上我们只用考虑从 $u$ 出发到子树内的非树边，因为横叉边在除了根处之外不会产生贡献，而根处我们需要特判）

根处的话，如果子树数量 $=2$，设选择的两个点为 $(x,y)$，我们需要额外乘上完全在 $x-y$ 这条链内的非树边的贡献，这个可以用 dsu on tree 实现，但是由于一条非树边只会在一个位置被操作到，所以总共的区间操作还是 $O(n+m)$ 次的

总之就是一堆乱七八糟的东西，最后可以用区间乘区间求和线段树维护，复杂度 $O((n+m)\log n)$

---

13. UER12 - 电子运动 [K] ⭐

题面

给定一个长为 $n$ 的 +-? 字符串 $s$，每个 ? 会以 $\frac12$ 的概率变成 + 或 -

初始有一个概率序列 $a_1,a_2,\cdots,a_n$，你会选择以 $a_i$ 的概率在 $i$ 位置放置粒子，这个粒子每次会运动：

• 如果当前为 -，那么粒子会向右运动，并将这个位置变为 +
• 如果当前为 +，那么粒子会向左运动，并将这个位置变为 -

粒子最后会从右边或左边掉出去，对 $i=0,1,2,\cdots,n$ 求最后有 $i$ 个 + 的概率，对 $998244353$ 取模

$1\le n\le5\times10^5$

题解

Sol

注意到粒子的位置每次 $+1$ 会减少一个 +，每次 $-1$ 会增加一个 +，因此如果起点为 $x$，只有最后的两种可能就是 $cnt+x$ 和 $cnt-(n+1-x)$，而这两个相差 $n+1$，一定恰好有一个在 $[0,n]$ 内

也就是说最后 + 的个数就是 $(cnt+x)\bmod (n+1)$，用 ntt 优化即可

---

14. 联合省选 2023 - 染色数组 [E]

题面

定义一个长为 $n$ 的数组 $a$ 是完美的当且仅当其有至少两种方式将每个元素染上红色或绿色，满足红色的元素严格递增，绿色的元素严格递降

定义一个染色方案的得分为：

• 对于每个红色元素 $j$，计数 $1\le ia_j$ 的 $i$ 的数量 $cnt$，对得分贡献 $cnt\cdot a_j$
• 对于每个绿色元素 $j$，计数 $1\le i<j$ 且 $a_i<a_j$ 的 $i$ 的数量 $cnt$，对得分贡献 $cnt\cdot a_j$

定义一个完美数组的得分为所有染色方案得分的最大值

现在给定 $n,m,t$，已知了 $a_1,a_2,\cdots,a_t$，$a_{t+1},a_{t+2},\cdots,a_n$ 在 $[1,m]$ 中任取，求：

• 完美数组的数量
• 完美数组的得分和

答案对 $998244353$ 取模

$T$ 组数据。

$1\le T\le5,2\le n\le50,1\le t\le n,1\le m\le200,1\le a_i\le m$

题解

Sol

大跃进时代的题目。

考虑刻画完美数组这件事情：首先判断有没有解完美可以进行一个 dp，存两个值表示当 $a_i$ 为红色的时候，绿色的结尾的最大值，以及 $a_i$ 为绿色的时候，红色的结尾的最大值

但是这个看起来不够好，因为我们转移的时候需要进行很多讨论

注意到如果我们把序列沿着红色绿色第一次交叉的位置切开，那么前面的部分一定是每次加入一个数 $a_{i+1}$，在原来的 $(prv,a_i,nxt)$ 内，其中 $prv$ 为 $a_i$ 的值域前驱，$nxt$ 为 $a_i$ 的值域后继，分类讨论一下可以发现只有 $prv<a_{i+1}<a_i$ 和 $a_i<a_{i+1}<nxt$ 的情况可以插入，分别插入成 $(prv,a_{i+1},a_i)$ 和 $(a_i,a_{i+1},nxt)$

那么考虑不断给前缀插入，直到插入不动为止，设这个位置为 $id$，那么我们对 $[id+1,n]$ 倒序进行一个类似的插入，分类讨论一下此时的解数，我们有的条件是 $a_{id}=a_{id+1}$ 或 $a_{id+1}\not\in(prv_l,nxt_l)$：

• 如果 $(prv_l,nxt_l)$ 和 $(prv_r,nxt_r)$ 无交，那么在 $id$ 处无解，并且在别的地方也不可能有解
• 如果 $(prv_l,nxt_l)$ 和 $(prv_r,nxt_r)$ 有交，且 $a_{id}\not\in(prv_r,nxt_r)$，那么在 $id$ 处恰有一组解，并且在别的地方也不可能有解
• 否则在 $id$ 处至少有两组解

此时我们已经可以考虑 dp 了，注意到我们状态中只需要保留 $(prv,a_i)$ 或 $(a_i,nxt)$ 中的一个，这个可以用前缀和优化到 $O(nm^2)$

考虑第二问。

可以手模一下存在至少两组解的方案的形态，注意到一定是中间有一个递增/递降的序列，并且恰有一个元素可以被选成绿色/红色，其余都为另一个颜色

讨论一下贡献可以发现改变的一定是最靠右的元素

那么在交叉及前面的贡献就可以通过 $O(n^2m^2)$ 的 dp 求得，记录一下较小的部分选的数的个数

右边的贡献需要使用巨大组合数讨论，也可以做到 $O(n^2m^2)$

总复杂度 $O(n^2m^2)$，卡常。

---

15. CF2055F - Cosmic Divide [E]

题面

给定一个 $n$ 行的凸的方格连通块（多格骨牌），第 $i$ 行占据了 $[l_i,r_i]$ 列的方格，凸性即为每一行占据的都是一个区间，每一列占据的也是一个区间

你需要把这个骨牌分成两个完全一样的，可以通过平移得到的骨牌，请判断是否可行

$1\le n\le2\times10^5,1\le l_i\le r_i\le10^9$

题解

Sol

注意到如果我们确定了骨牌向下移动的距离，那么我们就可以唯一确定一组解，判断这组解是否合法即可，那么我们就得到了一个 $O(n^2)$ 的做法。

但是对于所有向下移动的距离都 check 一遍复杂度太高了，我们需要加速。

我们的 check 中一些部分可以通过哈希加速，唯一不能加速的部分就是判断得到的骨牌连通

那么我们猜测一下，通过其它所有判断的距离一定不会很多，写一下可以发现事实确实是这样的，可以通过

editorial 说可以证明通过这些 check 的距离最多有 $9$ 个，因此这个算法是 $O(n)$ 的。

一个更容易想到的证明是 $len$ 序列一定要是一个 $(1+x^d)$ 的倍数，而拆成分圆多项式之后我们相当于是要选择一些数使得它们的 $\varphi$ 之和 $\le n$，而 $\varphi(k)\ge\frac k{\log\log k}$，所以最多有 $O(\sqrt n\log\log n)$ 个可以通过一个比较松的 check 的距离

---

16. CF1949H - Division Avoidance [E]

题面

二维平面上，初始 $(0,0)$ 被染黑，其它的格子均为白色。

一次操作，你可以选择一个黑色格子 $(a,b)$，然后如果 $(a,b+1)$ 和 $(a+1,b)$ 均为白色，那你可以将 $(a,b)$ 变白，将 $(a,b+1)$ 和 $(a+1,b)$ 都染黑

现在给定 $n$ 个坐标 $(x_i,y_i)$，你需要判断是否能将这几个格子同时变成白色

$1\le n\le10^6,0\le x_i,y_i\le10^9$

题解

Sol

容易注意到这个过程其实是很容易无解的。根据经典分析我们可以把一个格子赋上 $2^{-x-y}$ 的权值。

但是这并没有什么用。

考虑 $x=0$ 的所有格子，我们可以将 ban 掉的格子视为在这个格子上 $+1$，最后我们要让所有格子都 $\le1$

按 $x$ 扫描线，我们肯定是希望向后推的东西越少越好，那么分讨一下几种情况：

• 全是 $1$，显然不会向后推任何东西，因此我们可以把全是 $1$ 的前缀都扔掉
• 形如 $2,1,1,1,\cdots,1,?$，我们会向下推一段连续的 $1$，并且向后推一个 $1$
• 开头为 $3$，此时我们可以发现如果下一个位置不是 $0$，那么一定无解，否则一定会向下向右各推一个 $2$

模拟即可，颜色段均摊一下可以做到复杂度 $O(n\log n)$

---

17. CF1887F - Minimum Segments [E]

题面

对于一个序列 $a_1,a_2,\cdots,a_n$，定义序列 $r$ 为：$r_i$ 表示最小的 $j\ge i$ 使得 $a[i:j]$ 中包含 $a$ 中出现过的所有元素，不存在则为 $n+1$

现在给定一个序列 $r$，要求还原一个可能的 $a$ 或者判断无解

$1\le n\le2\times10^5$

题解

Sol

Flamire 思路

考虑把 $[i,r_i]$ 带来的限制描述成更正常的形式。

称 $prv_i$ 表示 $i$ 前第一个值等于 $i$ 的点，$nxt_i$ 表示 $i$ 后第一个值等于 $i$ 的点

如果 $r_i\neq r_{i+1}$，那么一个显然的事情就是 $prv_{r_{i+1}}=i$

否则的话 $r_i=r_{i+1}$，此时就是说 $i$ 加入到这个区间内并没有出现新元素，也就是说 $nxt_i\le r_i$

并且我们还需要保证每个区间恰好出现了所有颜色的限制，这个可以描述为 $[r_i+1:n]$ 的元素的 $prv\ge i$

那么把这些取一下交，我们就得到了一些关于 $prv$ 和 $nxt$ 的限制（注意仔细讨论 $0$ 和 $n+1$ 的情况），现在考虑如何构造

具体地，我们会有 $prv_i\ge limp_i$，$nxt_i\le limn_i$ 的两种限制

我们的构造只要在有解的时候都能构造出解就好了，构造出来的东西不合法我们可以直接输出无解。

首先假设我们枚举了颜色数 $c$，最后就是要把所有东西串到 $c$ 条链上，$i$ 从 $1$ 到 $n$ 枚举，枚举到 $i$ 的时候考虑确定 $prv_i$，如果已经确定了的话我们不管，否则我们需要用一个数据结构维护当前所有的 $c$ 条链底，且下一条边还没有被钦定过的链底集合

在这之中，如果选择的是 $j$，那么我们需要满足 $j\ge limp_i$，且 $i\le limn_j$，此时我们一定取下标最小的 $j$，因为 $limp,limn$ 都是递增的，此时取了，相当于把限制最严的元素选了，如果此时选不了，那么之后也选不了了，因此这样贪心是正确的

用堆或者队列实现，那么我们就得到了一个 $O(n^2\log n)/O(n^2)$ 的做法。

注意到我们构造不出来解的条件是某一时刻堆为空，或者此时堆顶元素的限制过于严了，而我们发现，当 $c$ 减小的时候堆顶元素一定不会变小

也就是说我们取最小的 $c$ 保证过程中堆都不会为空即可，总复杂度 $O(n\log n)/O(n)$

题解思路

其实和上面基本一样，但是说不定理解起来更简单一点。

颜色数有一个简单的上界是 $\min r_i-i+1$

颜色数的下界更复杂的一点，我们取 $\{r_i\}$ 为所有关键点集合，$c\ge1+\max([i+1:r_i] 中的关键点数)$，因为任意 $r_i$ 都满足 $a_{r_i}$ 与 $a[i:r_i-1]$ 中的任意元素颜色不同

可以发现对于 $c$ 在这个区间内都是可以构造的，我们依然构造每个点的 $prv$：

• 如果 $r_i\neq r_{i+1}$，那么 $a_{r_{i+1}}=a_i$
• 否则我们找到 $0\sim i-1$ 内第一个后继还没有确定的位置连过去（$0$ 位置可以连 $c$ 次）

这样每个区间内自由元的颜色是在不断轮换的，而我们的上界保证了自由元数量是充足的。

---

18. AGC031E - Snuke the Phantom Thief [E] ⭐

题面

给定平面上 $n$ 个点 $(x_i,y_i)$，第 $i$ 个点的价值为 $v_i$，你需要从中选择一些点，满足 $m$ 条限制，每条限制为以下四种中的一种：

• L：$x$ 坐标 $\le a_i$ 的点最多选 $b_i$ 个
• R：$x$ 坐标 $\ge a_i$ 的点最多选 $b_i$ 个
• U：$y$ 坐标 $\ge a_i$ 的点最多选 $b_i$ 个
• D：$y$ 坐标 $\le a_i$ 的点最多选 $b_i$ 个

求选的点的最大价值和

$1\le n\le80,1\le x_i,y_i\le100,1\le m\le320$

题解

Sol

做法 1

这个看起来有点流。考虑如何描述这个限制。

直接对每个点建点的话我们需要处理一个点的两种限制，这个不太好做。

但是如果我们把点看成 $x$ 坐标和 $y$ 坐标的边的话，这个就相对更好限制一些。

如果只有 R 和 D 限制的话，我们给 $x$ 坐标和 $y$ 坐标分别建一条 $i$ 到 $i+1$ 的链，$x$ 链的边权连 $x\ge i+1$ 最多选多少个，$y$ 链的边权连 $y\le i$ 最多选多少个

而此时加入 L 和 U 限制的话，我们并没有比较好的办法去限制另一边最多选多少个

那么考虑枚举一个总共选的个数 $c$，限制就变成一个前缀要至少选一些点，可以使用上下界网络流建模，最后求流量恰好为 $c$ 的最小费用

这样需要跑 $n$ 次 $O(n)$ 个点和 $O(n)$ 条边的网络流，总复杂度 $O(n^3\log n)$

做法 2

考虑如何写这个限制：对于 L 限制一个 $x\le a_i$ 的点最多选 $b_i$ 个的限制，相当于 $x$ 坐标从小到大第 $b_i+1$ 个点的坐标要 $>a_i$，类似如果我们枚举了总个数 $c$，对于 R 限制也可以这样做，最后我们会得到 $x$ 坐标从小到大第 $i$ 个点需要在一个区间 $[L_i,R_i]$ 内

注意到我们可以把这个条件弱化一下，改成在每一个 $[L_i,R_i]$ 内部选一个点，可以发现这样依然是正确的

那么对每个区间建 $O(n)$ 条边，网络流建模是容易的

这样需要跑 $n$ 次 $O(n)$ 个点和 $O(n^2)$ 条边的网络流，总复杂度 $O(n^4)$

---

19. AGC035E - Develop [E] ✔️

题面

最开始一个有一个集合 $S$ 包含所有整数，给定 $n,k$，接下来每步操作你可以进行如下事情：

• 选择一个 $1\le x\le n$，且 $x\in S$，将 $x$ 从 $S$ 中删去，然后对于 $x-2$ 和 $x+k$，如果它们不在 $S$ 中则将其加入 $S$

求能得到多少种不同的集合 $S$，答案对给定数 $m$ 取模

$1\le k\le n\le150,10^8\le m\le10^9$

题解

Sol

Flamire 做法

倒过来，那么就是每次如果 $x-2,x+k$ 都存在，我们可以将 $x$ 加入 $S$，最后要让所有东西都加入 $x$

首先 $k$ 如果是偶数的话那就非常好求了，只讨论 $k$ 是奇数的情况

手模这个过程，发现我们如果有一段 $\ge y$ 的奇数全选了，那么在这之后，我们选择了一个 $\ge y-k-2$ 的偶数，我们就可以把大于等于这个偶数的偶数全都补全

那么一个初步的想法就是维护奇数和偶数的这个最后一个全选的位置 $x,y$，然后新加一个元素 $i$ 进行一些转移

但是还是有一些问题的，因为我们忽略了一些元素，我们需要考虑这些元素有没有可能再带来转移

如果我们新加的奇数 $i\ge x-k-2$，那么它会把 $i$ 以上的所有奇数全都补全， 此时如果存在一个偶数 $z<x$，那么 $z$ 会把 $z$ 以上的偶数也全都补全，这是我们之前的转移考虑不到的

而注意到此时每个奇偶性只有最小的 $z$ 有用，而 $z>i$ 且 $z+k+2<y$，说明此时一定有 $x\le y$

那么我们记录一下 $i,x,y$，以及较小那一侧的 $z$，就可以做到 $O(n^4)$ 状态，$O(1)$ 转移，总复杂度 $O(n^4)$

事实上，可以进一步注意到需要记录 $z$ 的时候一定是 $y$ 之后都不再会有用的情况，所以此时我们可以只记 $(x,z)$，但是这样也会带来其一定的问题，说不定可以做到 $O(n^3)$？

题解做法

用一点更好的东西来描述这个操作。

我们让 $x\rightarrow x-2,x\rightarrow x+k$ 连边，如果我们要删除的集合形成了环的话，我们一定无法做到这件事情，因为环上至少有一个点在集合内，而如果不存在环的话，我们可以直接按拓扑序删除，因此这个是充要条件

考虑计数不存在环的集合。我们把两条 $x-2$ 的链拎出来，把其中一条偏移一下，以 $k=3$ 为例：

此时我们可以发现任意一个简单环一定长为 $k+2$，即走若干个左边的点，然后走横边到右边再走若干个右边的点，再回到起点

那么我们按层转移，令 $dp_{i,p,q}$ 表示第 $i$ 层，从第 $i$ 层右部点能走到的最靠前的右部点是 $q$，从第 $i$ 层左部点能走到的最靠前的左部点是 $p$，我们需要保证 $p$ 大于第 $i$ 层左部点 $-k$

转移容易做到 $O(1)$，复杂度 $O(n^3)$

---

21. AGC026F - Manju Game [E] ⭐

题面

给定一个长为 $n$ 的序列 $a_1,a_2,\cdots,a_n$，两个人轮流操作，一共操作 $n$ 次：

• 选择一个还没有被任何一个人占领过的位置，满足这个位置和上一步操作被对手占领的位置相邻，然后占领这个位置
• 如果不存在合法的位置，或者是第一步操作，那么就可以任选一个没被占领过的位置占领

双方都想最大化自己占领的格子的数之和，求最后的数是什么

$1\le n\le3\times10^5,1\le a_i\le1000$

题解

Sol

偶数比奇数简单。

首先我们将偶数位置染成黑色，奇数位置染成白色

注意到先手选出的第一个元素左右边如果是奇数个元素，那么后手就可以选这个段然后抢占先机

那么对于 $n$ 为偶数的情况，先手至少可以做到 $\max(B,W)$，其中 $B$ 和 $W$ 分别为对应颜色的和，而后手至少可以做到 $\min(B,W)$，只要通过先选两边长度为偶数的段，然后另一边达成对应颜色的值即可

那么偶数的时候先手的答案就是 $\max(B,W)$

考虑奇数的情况，那么如果先手选择了白色位置，后手一定可以选择所有黑色的点，这个不优于我们直接选端点，所以这种情况我们可以只考虑先手恰好获得 $W$ 的情况

接下来考虑先手选择黑色位置，那么后手就是选择一边继续做这个问题

也就是说最后先手选择的位置一定形如一段黑色，一段白色，一段黑色，而我们要最大化的就是白色段中 $W-B$ 的值

考虑先手如果选定了一个值 $v$，表示希望这个 $W-B\ge v$，怎么样才能保证选到，可以发现如果存在黑点集合 $S_i$，那么如果所有 $(S_i,S_{i+1})$（开区间）内的 $W-B$ 都 $\ge v$，先手一定可以让 $W-B\ge v$

即，如果黑点 $u,v(u<v)$ 之间的 $W-B\ge v$，我们就连一条 $u\rightarrow v$ 的有向边，最后先手能取到 $\ge v$ 的条件就是 $0$ 能到 $n+1$

充分性的话，先手只要一直操作路径上经过的点，区间内选不出来的话就直接选当前区间的 $W-B$，由我们的假设这一定是 $\ge v$ 的

必要性的话，设当前的区间为 $[l,r]$，先手操作了 $x$，那么一定有 $l$ 到不了 $x$ 或 $x$ 到不了 $r$，选择到不了的那边下去递归即可

那么总复杂度就是 $O(n\log V)$

---

22. AGC056E - Cheese [K] ✔️

题面

环上有 $n$ 个点，顺时针编号为 $1,2,\cdots,n$，每两个点之间有一只老鼠，现在我们进行 $n-1$ 次如下操作：

• 选择一个位置放置一个奶酪，以 $a_i$ 的概率选到位置 $i$，奶酪会顺时针运动，每次经过一个老鼠，如果这个老鼠之前没有吃过奶酪，那么它会以 $\frac12$ 的概率吃掉奶酪，否则什么也不做，奶酪会一直运动到被吃掉位置

最后会恰好剩一只老鼠没有吃过奶酪，求每只老鼠最后没吃过奶酪的概率，对 $998244353$ 取模

$1\le n\le40$

题解

Sol

很考验水平的题目。

直接做非常不好做，无论你怎么存状态看起来都做不了。

此时，你需要拥有足够的直觉，发现一件事情：如果最开始选的奶酪的起始位置集合一样，那么我们把问题转化为每次选择一个奶酪，让它运动到下一个老鼠的位置进行判定，最后的答案不变

一个感性理解是每个老鼠的判定过程和顺序几乎无关，在同一个位置的若干个奶酪，它们往后推的顺序对答案没有任何影响

那也就是说我们直接考虑一种起始位置最后会导致每只老鼠没吃过奶酪的概率

不妨假设我们算的是 $n$ 后面的老鼠的概率，那么我们拆成两部分计算：一部分是我们把所有奶酪推到 $n$ 的过程，另一部分是我们知道 $0$ 位置有 $x$ 个奶酪，然后不断绕圈

可以用 dp 算出，单次复杂度 $O(n^4)$，总复杂度 $O(n^5)$

---

23. JOISC2025 - 展覧会 3 [E] ✔️

题面

给定 $n$ 个数的序列 $a_1,a_2,\cdots,a_n$，以及 $m$ 个区间 $[l_i,r_i]$，生成一个长为 $m$ 的序列 $b_1,b_2,\cdots,b_m$，其中 $b_i$ 为 $a[l_i,r_i]$ 的最大值

你需要重排 $a$，使得 $b$ 的字典序最大，求这个字典序最大的 $b$

$1\le n\le10^5,1\le m\le10^5,1\le a_i\le n$

题解

Sol

The problem can be reduced to iterating over $v$ from $n$ to $1$, each time we delete a lexicographically smallest set of intervals which can be covered with $cnt_v$ elements.

To check this for a certain set of intervals $S$, a simple greedy will be taking the minimum $r$ of all uncovered intervals, and placing a element with value $v$ at this position. This runs in $O(|S|\log|S|)$ by sorting and will calculate the minimum number of elements needed to cover all intervals in $S$, we will call this value $f(S)$.

We can run this greedy in both directions, from left to right, each time taking the rightmost one, and vice versa. We name the $i$-th element on these paths $sr_i$ and $sl_i$, respectively.

To calculate the maximal prefix that can be covered for some $v$, we can run brute force check on lengths $2^0,2^1,2^2,\cdots$, until we locate that the maximal prefix is in range $[2^l,2^{l+1})$. Then we can run binary search in the range, our complexity is bounded by $O(len\log^2 len)$, where $len$ is the length of the maximal prefix. This can be further optimized to $O(len\log len)$ if we sort the first $2^{l+1}$ intervals preemptively, which means that we don’t have to sort during the binary search.

Suppose for some $v$, we have calculated the maximal prefix $S$ which can be covered, then it follows that $f(S)=cnt_v$ (or the trivial case that $S$ contains all intervals). To check whether a new interval can be added to $S$, we only need to check whether $f(S)$ increases.

Observation 1: $f(S)$ increases iff the new interval does not intersect with any $[sl_i,sr_i]$.

This can be inferred from the definition of $sr$ and $sl$, with some minor reasoning.

Now, with some extra effort, we will have a solution that runs in $O(nm)$. When $n$ becomes larger, we will need to find an efficient way to maintain $sr$ and $sl$.

Observation 2: Each interval will only enter and exit $sr$ at most once. The same holds for $sl$.

This is due to each $sr_i$ being decreasing over time, and that each interval can only enter $sr$ at one position, or else we can deduce that $f(S)$ has increased.

Each time we add an interval to $S$, we can run binary search to find its place among $sr$, and try to update one by one. We will need to maintain the “next” of each value with some data structures (I used a segment tree). We will perform linear updates to $sr$ and $sl$ in total.

Using the above, if we do an $O(m)$ check for all $v$, we can pass $a_i\le 5$. To optimize, the only task which remains is to locate the next interval that can be added to $S$ efficiently.

If we only need to check for a single $[sl_i,sr_i]$, that is, find the first interval which intersects with $[sl_i,sr_i]$. This can be solved by keeping two sets on a segment tree over positions $1,2,\cdots,n$, which yields a complexity of $O(\log^2 n)$ insertion/deletion, and $O(\log n)$ query.

A simple idea will be keeping a data structure containing the first interval for every $[sl_i,sr_i]$, each time we take the minimum, check if it is not already in $S$, and add it to $S$. However, this is incorrect, as an interval can be the first interval for lots of $[sl_i,sr_i]$, and we have no way of updating them all efficiently.

Observation 3: If we take the $sr$ and $sl$ of $S$, all intervals that contains at least one $[sl_i,sr_i]$ can always be added to $S$. Adding them will also have no influence on $sr$ and $sl$.

Therefore, after we calculate the maximal prefix, we take the current $sr$ and $sl$ and add all intervals satisfying the condition above. After this process, any interval will intersect with at most two $[sl_i,sr_i]$’s in the future, so we will have linear updates to this set in total.

Notice that all our insertions to the sets on segment tree structure is increasing, and only at the beginning. We only need to perform queries and deletions in the main algorithm. Therefore, we can replace sets with linked-lists to optimize it to $O(\log n)$.

Total complexity: $O(n\log n)$.

---

24. JOISC2025 - ビ太郎の旅 2 [S]

题面

有一个 $n\times m$ 的矩形 $a$，$(i,j)$ 位置的高度为 $a_{i,j}$，你在上面的某一个位置，你可以不断进行如下操作：

• 从当前所在位置跳起，若当前位置的高度为 $x$，你会跳到 $x+L+0.5$ 的高度，其中 $L$ 是一个给定常数
• 你可以任意向四联通的格子移动，需要满足你移动到的格子都低于你当前高度
• 最后你在移动到的格子降落

$q$ 次询问，第 $i$ 次询问给定一个起点 $(a,b)$ 和一个终点 $(c,d)$，求如果想要从 $(a,b)$ 到 $(c,d)$，最少操作多少次，或者输出无法到达

$2\le n\times m\le3\times10^5,1\le q\le3\times10^5$

题解

Sol

我们一定会访问到高度 $\le x+L+0.5$ 的最高的点，因此可以想到建 kruskal 重构树

建完之后判断是否有解就是起点到 LCA 的路径是否都满足与父亲的边权差 $\le L$，操作次数的话预处理一下跳一步 $L$ 最多能跳到哪个祖先，然后倍增一下即可

复杂度 $O((nm+q)\log nm)$

---

25. JOISC2025 - 救急車 [E]

题面

有一个 $L\times L$ 的方格，其中 $(1,1),(1,L),(L,1),(L,L)$ 分别有一所医院

现在有 $n$ 个病人分别在 $(x_i,y_i)$ 的位置，你需要给每个病人分配到一个医院，然后救护车会去接这些病人。

你需要满足每个医院被分配的所有病人，到医院的曼哈顿距离之和 $\le\frac12T$

请判断是否可能

$3\le L\le10000,1\le n\le160,1\le T\le20000$

题解

Sol

有四种选择，不好搞。

仔细观察一下数据范围，我们发现值域很小，也就是说我们的做法可以和值域带一点关系。

考虑观察一些性质：可以发现选到左上和右下的代价恰好是 $x$ 和 $2L-x$，那么一件显然的事情就是我们按照到左上的距离排序，选择到左上的一定是前面的一些，选择到右下的一定是后面的一些

而对于左下和右上有类似的事情，也就说我们可以用 $O(n^2)$ 的时间枚举两条分界线之后，每一个块内就只有两个医院可以选，那么我们就可以进行一个 $O(nT)$ 的背包 dp 求出选择一边的医院选择了 $v$ 的距离和，另一边的医院最少距离和

那么就可以得到一个 $O(n^3T)$ 的做法。

按照其中一条分界线的顺序做前缀后缀 dp 就可以把复杂度降到 $O(n^2T)$

---

26. JOISC2025 - スタンプラリー 4 [S]

题面

有一个 $2n$ 个点的环，依次编号为 $1,2,\cdots,2n$，每条边上有一个盖章点，第 $i$ 个盖章点的颜色为 $a_i$，一共 $n$ 种颜色每种颜色恰好出现两次

现在有一个人，要从一个点 $x$ 出发开始顺时针遍历所有盖章点，然后在盖章纸上盖章，需要遵循以下规则：

• 盖章纸有两个空，每个空只能被盖一次
• 在一个颜色为 $x$ 的盖章点，可以盖任意个颜色为 $x$ 的章，但是需要盖完第一个空才能盖第二个空

这个人想要最后盖完自己的盖章纸，并且让自己能得到至少 $K$ 种不同的盖章纸，为此，他可以交换一些盖章点

具体地，他可以花费 $X$ 的代价交换两个相邻的盖章点，你可以进行这个操作任意多次，但是限制是你不能跨过 $x$ 点进行交换，即你不能交换 $x-1$ 到 $x$，和 $x$ 到 $x+1$ 边上的盖章点

同时，你从 $x$ 开始还会有 $c_x$ 的代价

$q$ 次询问，每次给定一个 $K$，求最小代价和

$2\le n\le5\times10^5,1\le q\le5\times10^5$

题解

Sol

把每种颜色看成区间，那么代价就是 $n^2$ 减去不交的区间个数，而如果我们将每个位置是左端点还是右端点用 R 和 L 标出来，这个就是 RL 子序列的数量

那么每次交换最多可以让种类数 $+1$，并且存在一种操作方案一直 $+1$，也就是说我们一个起点的代价就是 $c_x+\max(0,K-K^\prime)\times X$，其中 $K^\prime$ 为初始的种类数

对每个起点预先求出来 $K^\prime$ 即可，这个可以直接通过用树状数组维护 RL 字符串求出

复杂度 $O(n\log n)$

---

27. JOISC2025 - 宇宙怪盗 [E]

题面

交互题。

给定一个 $n$ 个点 $m$ 条边的无向连通图，交互库在上面选择了两个点 $a,b$，保证 $a\neq b$，你需要猜出这两个点

你可以进行询问：一次询问，你需要给 $m$ 条边中的每一条指定一个方向，交互库会回答你 $a$ 是否能到达 $b$

请在 $300$ 次询问内猜出两个点

$2\le n\le10000,1\le m\le15000$

有 80pts 保证 $m=n-1$

题解

Sol

首先考虑树的情况。

如果我们能找到一条边，使得我们知道 $a$ 在其中一边，$b$ 在另一边，那么我们可以通过按照 dfn 顺序二分分别求得 $a,b$

更一般地，如果我们能将点分为两个不交的连通块，满足 $a$ 在一边，$b$ 在另一边，我们也能进行如上的过程

找一条路径上的边这个可以往二分的思路上去想，树上二分可以考虑使用二度点分治，我使用的是合并果子点分治，这时候我们二分的两侧可能并不是连通块，并且中间会空一个点，不过问题不大

手玩一下可以得到一个三步判断 $a,b$ 是否分属两边集合的策略：

如果失败了，我们无法得知 $a,b$ 在两个集合的哪边，所以我们需要下去并行二分，而由于这是一棵树，所以并行的时候，不同的二分连通块之间我们不需要在乎它们边的顺序

并行的时候如果成功了，我们还需要将此时所有的正在二分的集合拉出来，然后再在这些集合上进行二分，找到是哪一组集合成功了

找到之后我们就可以用原来的 dfn 二分了。

实际上常数应该是四倍分治树深度？不过写出来好像常数很小。

接下来考虑扩展到图上，那么一个自然的想法就是随便拉一棵生成树出来跑这个过程。

这样我们唯一需要考虑的就是非树边应该怎么办。我们希望非树边对整个过程没有任何影响。

对于将 $a,b$ 分开之后的 dfn 二分过程，是比较容易消除非树边影响的，假设当前我们知道 $a$ 在 $S$ 集合内，我们要判断它是否在 $T$ 集合内（$T\subset S$），我们可以让 $S-T$ 向外的连边都向内指，这样就不会影响二分的过程

对于并行二分，讨论的时候会痛苦一些，具体地，假设我们当前想进行的询问是 $(S_{1,x},S_{1,y}),(S_{2,x},S_{2,y}),\cdots,$，分别表示我们要询问在 $S_{i,x},S_{i,y}$ 的内部树边已经确定了一些顺序，并且 $S_{i,x}$ 和 $S_{i,y}$ 之间的边都是连向 $S_{i,y}$ 的，那么我们的目标就是让不存在某个集合 $S_i$ 能走一条非树边走到其它集合，再走一些边走回到 $S_i$ 的两个集合

这个是可以达成的，具体地我们按照如下方式定向：

• 对于连到不在任意 $S_i$ 内的点 $u$，我们让这条边向内连（其实都无所谓，只要指定一个方向即可）

• 对于两端都在某个 $S_i$ 内的边 $u-v$，我们给所有 $S_i$ 随便定一个拓扑序，从拓扑序先的连向拓扑序后的

  这样还是会有一些问题，因为我们的分治树是合并果子点分治，不同集合之间会重复一个分治中心，这个会让我们上面的构造坏掉一点，因此我们继续做出调整

  让同一个分治中心 $u$ 的集合在 $S_i$ 拓扑序内相邻，并且将包含 $u$ 的那个 $S_{i,u/v}$ 排到段内最后一个，对于在以 $u$ 为分治中心的集合之间的连边，我们按照如下方式定向：

  • 如果是从某个 $S_{?,x}$ 连向 $S_{?,y}$ 的，那么我们将这条边的方向定为 $x$ 到 $y$
  • 否则按照拓扑序定向

这个做法看起来就很烂。并且分讨得也很烂。可能是因为合并果子点分治的结构不是很好，导致要进行关于中心点的分讨。

最后询问数还是和树的情况一样的。

---

28. JOISC2025 - 勇者ビ太郎 3 [S]

题面

比太郎在打关。关有一个 $[0,L]$ 内的难度系数 $l$

一共会有 $T$ 秒时间，一共有 $n$ 个敌人，第 $i$ 个敌人会在第 $t_i$ 秒出现，血量为 $l\times h_i$，危险值为 $p_i$

比太郎每秒可以选择一个血量非零的敌人，对它进行攻击，让它的血量 $-1$

最后如果敌人的血量分别为 $h^\prime_1,h^\prime_2,\cdots,h^\prime_n$，那么你的罚分是 $\sum h^\prime_ip_i$

$q$ 次询问，每次给定一个 $m$，查询如果你想让最优策略下你能使罚分 $\le m$，那么最高的难度系数 $l$ 可以是多少

$1\le n\le6000,1\le L\le10^7,1\le q\le10^6$

题解

Sol

容易发现我们的策略是每次删 $p$ 最大的人，但是时刻维护最大值并不是很好做，所以我们可以考虑枚举一个值 $v$，然后把数分成 $\ge v$ 和 $<v$ 两个部分

考虑直接把每个 $l$ 最后的值求出来

我们要做的就是每次加上一个 $l\times h_i$，再减去时间间隔，对 $0$ 取 $\max$，给 $l$ 的答案加上最后的值

这个操作就是最大后缀和，那么我们就可以写成 $O(n)$ 个关于 $l$ 的一次函数取 $\max$，容易知道凸包上只有 $n$ 段，并且斜率还是有序的，因此可以 $O(n)$ 的复杂度把凸包求出来，再用差分加到答案上

每次询问二分即可

复杂度 $O(n^2+L+q\log L)$

---

29. JOISC2025 - 会議 [E] ✔️

题面

给定一个长为 $n$ 的包含 ABC? 的字符串 $s$，保证开头结尾为 A

$q$ 次询问，每次询问给定 $c_A,c_B,c_C$，保证 $c_A+c_B+c_C=[\texttt{?} 的个数]$，求恰好将 $c_A$ 个 ? 填成 A，$c_B$ 个 ? 填成 B，$c_C$ 个 ? 填成 C 后最少有多少 $s_i\neq s_{i+1}$ 的位置

$2\le n\le3\times10^5,1\le q\le2\times10^5$

题解

Sol

我们有两种东西：

• 形如 A????A，有 $len$ 个位置，一开始只能选 A，$+2$ 后能选 AB 或 AC，$+3$ 后能选 ABC
• 形如 A????B，有 $len$ 个位置，一开始只能选 AB，$+1$ 后能选 ABC

但是至此这个看起来还是不是很好做，考虑找一些特殊情况

如果我们整个字符串里只有 A????A，并且 $c_A=0$，那么我们就是要判断能不能选出一些 $len$ 加起来恰好等于 $c_B$，所以这个问题不弱于背包。

那么这个看起来就有点不好了，那么我们考虑仔细分析一下如何解决这种情况。

注意到不能的话，我们就至少要选一个 $+3$，而这个显然选越大的越优，那么我们就一定会把 $len$ 最大的变成 ABC，此时可以发现，我们就可以凑出任意 $c_B$ 了

更一般地，如果我们有一个段长为 $x$，并且它最后变成了 AB 或 AC，还有一个段是长为 $v$，可以选 ABC，且 $x\le v$，那么这两个段合起来可以等效为一个长为 $x+v$ 可以选 ABC 的段

此时这个问题看起来就可做一点了，因为背包我们是能做的，那么考虑重新入手一下这个问题。

首先，如果我们已经确定了最后每个段的类型，那么我们可以通过一些简单的约束判断是否有解，具体地，我们对每种字符，比如 A，只能选 A 的段之和要 $\le c_A$，并且能选 A 的段之和要 $\ge c_A$，比那个且这个也是充要条件，这个可以通过 Hall 定理说明，因此我们需要做的事情就是花费代价改变段的类型，使得其符合这个限制

画到韦恩图上就是角内的和要小于等于一个东西，圈内的和要大于等于一个东西，下面我们会使用这种表述

那么我们根据圈限制满足的数量分类讨论：

• 所有圈内的元素都足够多，此时只可能出现一些角上的元素太多了，那么我们就需要把它们往外推，此时对每种字符我们一定是不断把最大的往外推，直到合法了为止，这个可以二分求得

• 恰有一个圈内的元素不够多，设其为 C，那么此时可能出现 A 和 B 角元素太多了，容易发现我们这时推 A，AB，B 的方向一定是推到 AC，ABC，BC，那么首先我们推掉 A 角和 B 角的一段必须推的后缀，剩下的部分就是有一些数代价为 $1$，有一些数代价为 $2$，我们要选一些数，使得其的值加起来大于等于某个界，然后最小化代价和

  这个可以通过按性价比从大到小贪心实现，如果我们最后选择的是一个 $2$ 的元素，那么我们需要讨论两种反悔的情况，分别是不选这个 $2$ 选一个 $1$，或者反悔掉一个之前选的 $1$，如果两种有一种成立则我们可以让代价和 $-1$，否则不变

  可以通过二分+一堆预处理加速

• 恰有两个圈内的元素不够多，设其为 B 和 C，那么此时必然会出现 A 角内的元素太多了，我们需要将这个 A 的元素向外推，推出来会变成 AB 或 AC，这个也是导致我们要使用背包的情况

  那么首先我们往外推的显然是一段后缀，即最大的几个，于是有一个后缀是被确定必须往外推的

  然后我们想套用一下之前的结论，可以发现，我们只要代价 $+1$，把这个往外推的后缀里最大值变成 ABC，此时后缀里所有数都会变成 ABC 任选的，现在对于 B 和 C，我们相当于是必选的一定分别小于 $c_B,c_C$，并且总共可选的 $\ge c_B+c_C$，所以稳赢了。

  也就是说我们只需要判断一段 A 角的后缀能不能凑出来一段区间内的任意值（使 $c_B,c_C$ 限制均满足的区间）即可

  这个我们可以预处理出来每种数第一次能被凑出来的为止，这个我们可以使用多重背包二进制优化 + bitset 做到 $O(n\sqrt n/w)$，单次查询就是 rmq，可以用喜欢的数据结构实现

因此总复杂度是 $O(n\sqrt n/w+q\log n)$

---

30. JOISC2025 - マルチコミュニケーション [S]

题面

有 $n$ 个人，每个人有一个板，初始恰有一个人的板上会被写上 T，其余人的板上都写着 F，每个人知道自己的板上写了什么

接下来进行如下操作 $L$ 轮：

• 每个人将自己板上的字符擦除，然后根据之前看到过的所有字符决策在板上写 T 或 F
• 在所有人写完之后，每个人根据自己之前看到过的所有字符决策一个 $pos$，表示然后他会看到第 $pos$ 个人当前板上的字符

所有人需要配合使得经过 $L$ 轮之后，每个人需要知道一开始谁的板上写的是 T

请构造如下三种情况时的策略：

• $n=4,L=2$
• $n=32,L=8$
• $n=48,L=9$

题解

Sol

这个范围看起来很 $\log$，然后我们要找的就是一个人距离 T 有多远，因此可以考虑倍增

对于 $n=4$，我们的长度是 $1\rightarrow1$

对于 $n=32$，我们的长度是 $1\rightarrow2\rightarrow4\rightarrow8\rightarrow8\rightarrow4\rightarrow2\rightarrow1$

对于 $n=48$，我们的长度是 $1\rightarrow2\rightarrow4\rightarrow8\rightarrow16\rightarrow8\rightarrow4\rightarrow2\rightarrow1$

每种都刚好能覆盖对应 $n$ 的长度

---

31. JOISC2025 - 電子回路 2 [E/K]

题面

给定一棵 $2n+1$ 个点的二叉树，每个非叶子节点都有恰好两个儿子，因此一共有 $n$ 个非叶子节点

每个节点上有一个变量 $x_i$，每个非叶子节点上有一个逻辑门 $\otimes_i$，这个逻辑门可能为 $\text{AND}$ 或 $\text{OR}$，但是你不知道它们是什么，你需要通过询问来确定每个门是什么，保证 $\text{OR}$ 门不超过 $R$ 个

一次询问，每次询问你需要给每个 $x$ 赋一个值，然后根据如下规则运算：

• 对于一个叶子节点 $u$，其最后值即为自己的变量 $w_u\leftarrow x_u$
• 对于一个非叶子节点 $u$，其最后值为 $w_u\leftarrow(w_{lc}\otimes_uw_{rc})\text{ XOR }x_u$

最后你会得到根的 $w$ 值

你需要在 $1000$ 次询问内确定每个门是 $\text{AND}$ 还是 $\text{OR}$

$1\le n\le8000,1\le R\le\min(n,120)$

题解

Sol

首先有一个 $O(n)$ 做法，我们从上到下按 dfn 序，每次查询一个门是 $\text{AND}$ 还是 $\text{OR}$，由于上面的门都已知，所以我们可以直接将这个节点的运算结果保留到最后

那么我们这个询问方式是容易扩展到一次询问若干个无祖孙关系的点中是否有 $\text{OR}$ 的，但是这不能对我们的复杂度做什么改进，因为我们处理不了链（即非叶子节点串成一条链）的情况

对于链的话，我们可以一次询问出一段区间内有没有 $\text{OR}$，具体地，如果上面的东西都已知，我们可以把一段区间内上面挂着的叶子节点全填成 $1$，这样有一个 $\text{OR}$ 门上面的运算结果就会是 $1$

用这个扩展一下上面的做法，我们可以询问若干个无祖孙关系的链中是否有 $\text{OR}$

由此，可以想到重链剖分，我们把树剖完之后，每次询问到根恰有 $i$ 条轻边的所有重链

这样我们就得到了一个 $R\log n$ 次询问的做法，但是会被卡询问次数

优化一下的话，可以考虑按 $B$ 个分一块，每次先询问一个块内有没有 $\text{OR}$，有的话再继续向下二分，询问次数是 $\frac nB+R\log B$ 的，取 $B=32$ 即可通过

---

32. JOISC2025 - 移住計画 [S] ⭐

题面

给定一棵 $n$ 个点的树，根为 $1$，初始点 $i$ 上有 $a_i$ 个人，$q$ 次操作，每次进行如下操作中的一种：

• 1 x y，保证 $x\ge y$，将所有深度为 $x$ 的节点上的人，移动到其祖先中的深度为 $y$ 的节点
• 2 u w，将 $a_u\leftarrow a_u+w$
• 3 u，查询 $a_u$ 的值

$2\le n\le2\times10^6,1\le q\le2\times10^6$

题解

Sol

建一棵重构树，对每种深度建一个节点，进行 1 x y 操作的时候，我们对 $x,y$ 分别新建一个节点 $dx,dy$，$dy$ 的两个儿子分别指向原来 $x,y$ 深度的点，$dx$ 是叶子

2 操作对 $dep_u$ 新建一个节点，然后在新的节点上挂一个 $(u,w)$

3 操作就是查询一个重构树子树内，点属于原树子树的二元组值之和

这个可以转化成二维数点，复杂度 $O((n+q)\log n)$

---

33. JOISC2025 - ういろう [E]

题面

给定一个长为 $n$ 的数组 $a_1,a_2,\cdots,a_n$，$q$ 次询问，每次询问给定一个 $[l,r]$，然后令 $b\leftarrow a[l:r]$，求一下问题的答案：

• 最多将 $b$ 中多少个元素变为原来的相反数，使得 $b$ 的任意前缀和仍 $\ge0$

$1\le n\le2\times10^5,1\le a_i\le100,1\le q\le2\times10^5$

题解

Sol

首先我们需要会解决单次询问，单次询问有很多种贪心的方法，但是注意到这题值域很小，所以我们可能需要一个和值域相关的东西

我们的限制就是前缀内选的数之和小于等于某个东西，那么也就是说如果我们前面选择了 $i$，后面没选择 $j$，且 $a_i\ge a_j$，我们一定可以调整一下使其不劣

最优解就一定满足任意值选的都是一段后缀。

大胆一点可以发现如果我们从小到大扫值，每次选极长的后缀，最后贪心得到的结果是对的

这是因为假设值 $x$ 是第一个没有选到极长后缀的，那么我们可以说明我们把 $x+1$ 后缀中第一个数不选，然后将 $x$ 的后缀延长一个值是合法的

也就是说，我们已经可以每次二分后缀分界点，得到一个 $O(nA\log n)$ 的做法了，常数很小，可以通过

但事实上我们可以不用二分，注意到如果我们选了 $t$ 个值 $v$，那么我们直接认为一个前缀和是所有 $\le v$ 的值全选负，$>v$ 的值全选正，额外 $+2tv$，这个是正确的，因为我们值算大的部分一定在选择的后缀之外，也就是说它们本来就是合法的，我们不会把不合法的变合法

然后就可以推式子，把一次处理变成一次 rmq 查询，可以用 $O(n)-O(1)$ rmq 优化到 $O(nA)$