省选国赛精选题单

AGC052B Tree Edges XOR

给定一个 $n$ 个点的无根树（保证 $n$ 为奇数），第 $i$ 条边有边权 $w_{i,1}$。

你可以进行任意次操作，每次操作选定一条边，并将与这条边相接的所有边的 $w_{j,1}$ 异或上这条边的 $w_{i,1}$。你需要将所有边的 $w_{i,1}$ 变为 $w_{i,2}$，求是否可以做到。

$1\leq n\leq 10^5,0\leq w_{i,1},w_{i,2} < 2^{30}$。

非常深刻的一道题。

首先边权是较难处理的，我们考虑将边权转化为点权。具体地，一种较好的方法是钦定一个点 $1$ 为根，然后点 $u$ 的权 $W_u$ 是路径 $(1,u)$ 上所有边的 $w_{i,1}$ 的异或和。然后尝试刻画题意中的操作。

考虑原树的一部分：

我们选定 $(a,b)$ 进行操作，会得到：

那么如果我们用 $W'$ 表示新的点权，那么 $W'_a=W_f\otimes F\otimes x = W_b,W'_b=W_f\otimes F\otimes x\otimes x=W_a$，而 $W_c,W_d$ 因为异或两次 $x$，所以不会变化。因此我们得到原题中选定边 $(u,v)$ 进行操作，等价于交换 $W_u,W_v$。

真的是这样吗？事实上如果我们选择了一端点是根的边，由于根没有父节点，因此会出问题。所以我们建立一个虚拟节点 $E$，向 $1$ 连一条边，我们不对这条边进行操作，用于保持性质。

那么我们需要调整这个 $(E,1)$ 间的边权，使得每个点的点权经过交换（重排）后等于 $W_{i,2}$ 时候的点权，再额外异或上 $n$ 次 $(E,1)$ 的权 $\omega$（因为在期望时候的点权中，$1$ 的点权为 $0$，但这不一定成立，所以需要用异或补足）。

我们可以用两个序列的异或和来（暂时）判定相等。具体地，$W_{i,2}$ 的异或和以及每个点的点权异或和我们都清楚，异或上 $n$ 次 $\omega$ 等价于异或上一次，所以我们可以求出原始点权和期望点权，它们的异或和就是 $\omega$。

不过注意这样的 $\omega$ 只是保证异或和相等，不能保证所有元素相等，所以最后用这个 $\omega$ 去判定是否合法（点权序列是否真的相等）即可。

时间复杂度 $O(n\log n)$，Submission。

CF1458D Flip and Reverse

$T$ 组数据。每组数据给出一个 $01$ 字符串 $S$，你可以进行任意次操作：

• 选择一个区间 $[l,r]$，要求 $S[l,r]$ 中 $\texttt{0}$ 的数量与 $\texttt{1}$ 的数量相等。
• 将 $S[l,r]$ Flip（即 $\texttt{0}$ 变成 $\texttt{1}$，$\texttt{1}$ 变成 $\texttt{0}$）。
• 将 $S[l,r]$ Reverse（即翻转）。

你需要使得最后的 $S$ 的字典序最小，输出这个 $S$。

$1\leq \sum |S|\leq 5\times 10^5$。

啊这道题真是有种如拨云雾而（直）见（接）青（升）天之感。

让我穿透云雾，直接升天

对于“$\texttt{0}$ 的数量等于 $\texttt{1}$ 的数量”这种限制，一种经典的处理方法是折线图模型，也就是将 $\texttt{0}$ 看成 $-1$，$\texttt{1}$ 看成 $+1$，则我们将 $S$ 转换成了一个 $\pm 1$ 序列，则 $S[l,r]$ 中 $\texttt{0}$ 的数量等于 $\texttt{1}$ 的数量等价于 $[l,r]$ 的和为 $0$，即 $P_r=P_{l-1}$，其中 $P$ 是这个序列的前缀和，下面我们的研究都在 $P$ 上进行。

考虑这个操作在前缀和序列上干了什么，不妨假定在整个字符串 $S[1,|S|]$ 上操作，那么研究序列 $P$ 的变化：

• Flip：即 $P_i\gets -P_i$。
• Reverse：由于 $P_n=0$，所以 $P_i\gets P_n - P_{n-i} = -P_{n-i}$。

所以一次操作等价于 $P_i\gets P_{n-i}$，换句话说就是将 $[1, |S|-1]$ 翻转。迁移到区间 $[l,r]$ 的操作就是将序列 $[l,r-1]$ 翻转。

最后我们要求 $S$ 的字典序最小，也就是 $\pm1$ 序列字典序最小，或者说是 $P$ 序列字典序最小。

我们尝试将关系建图，具体地，对于每一个 $i$，连边 $(P_i, P_{i+1})$，那么我们会得到一张有向图（并且有很多重边）。

考虑如果我们将一个区间 $[l,r-1]$ 翻转，在原图上会有怎样的影响，那么可以注意到我们是在将一个环上的所有边反向，但是注意到由于每条边只能将 $P$ 序列 $\pm1$，所以如果有一个 $+1$ 边，那么就会有一个 $-1$ 边，所以实际上反向不会对原图产生实质上的影响。

这个图是容易构建的，现在的问题是如何通过这张图构造最优方案。我们有引理：

引理：通过任意次操作得到的一个字符串，可以与图上的一个欧拉路径一一对应。

理解起来也并不困难，首先原串本身对应了欧拉路径，可以考虑每一个欧拉路径和原串路径做对比，如果在一个位置脱离了，那么最后还要在走回这条边的，相当于我们逆向走了一个环，也就是对一个区间进行了 Flip & Reverse 操作。

所以最后我们只需要求出这张图的字典序最小的欧拉路径即可，可以用 Hierholzer 算法完成。时间复杂度 $O(\sum |S|)$，Submission。

QOJ 6504 Flower's Land 2

有一个长度为 $n$ 的序列 $a$，保证 $0\leq a_i\leq 2$，有 $q$ 次操作，支持：

• 1 l r：$\forall i\in[l, r], a_i\gets (a_i+1)\bmod 3$。
• 2 l r：令 $T=a[l, r]$，你在序列 $T$ 上玩一个游戏，每次选择相邻两个相等的数并将它们删除，重复上述操作直至无法操作为止，询问你是否可以将 $T$ 变成空序列。

$1\leq n,q\leq 5\times 10^5$。

每天一个神奇 trick。

假如我们找到了一个非 Abel 群 $G$，并适当选择其中三个元素 $k_0,k_1,k_2\in G$，那么在序列的奇数位放 $a_{k_i}$，偶数位放 $a_{k_i}^{-1}$，那么在查询时，如果区间 $[l,r]$ 的乘积为 $\epsilon$，说明我们可以通过改变运算先后顺序（而不是交换顺序），使得每次运算的结果都是 $\epsilon$，即区间 $[l,r]$ 可以通过玩游戏变成空序列（因为在理想情况下，只有相邻相同的数，乘起来才会使 $\epsilon$）。

这样的群是非常常见的，典型代表就是矩阵乘法。因此我们可以寻找三个可逆形状相同的可逆方阵，然后用线段树维护区间乘积，查询时判断乘积是否为单位矩阵 $I$ 即可，修改的话可以改为每个节点存储一个长度为 $3$ 的矩阵列，分别表示序列中这一位（模 $3$ 意义下） $+0,+1,+2$ 后的新矩阵，那么修改就变成了对这个东西做一次循环移位，也是容易叠加的。

有一个小技巧，如何选择这样的矩阵？为了方便，可以直接用 $2\times 2$ 的。为了更方便些，我们可以采用对合矩阵，即逆矩阵为本身的可逆矩阵（这样就不需要按照奇偶分类讨论了）。构造对合矩阵可以用对合矩阵通式：

$$A=\begin{bmatrix} a& b\\ c& -a \end{bmatrix}\quad (a^2+bc=1)$$

时间复杂度 $O(q\log n)$，Submission。

P7211 [JOISC 2020] カメレオンの恋

每日一道 JOISC （1 / 1）。

这是一道交互题。

有 $2n$ 只变色龙，其中 $n$ 只是雄性，$n$ 只是雌性。具体地，若 $Y_i=0$ 表示变色龙 $i$ 是雌性，否则是雄性。

第 $i$ 只变色龙的原本颜色是 $C_i$，且喜欢变色龙 $L_i$，$C_i,L_i$ 满足：

• $Y_i\neq Y_{L_i}, C_i\neq C_{L_i}$，即变色龙只会喜欢和自己颜色不同的异性。
• $\forall i\neq j, L_i\neq L_j$，即不存在两只变色龙喜欢同一只变色龙。
• $\forall (i\neq j, Y_i=Y_j), C_i\neq C_j$，即同性变色龙颜色互异。
• $\forall i, \exists Y_i\neq Y_j, C_i=C_j$，即对于每一只变色龙，都存在一只与其颜色相同的异性变色龙。

你只知道 $n$ 和关于 $L,C,Y$ 的这些限制。但你不知道 $L,C,Y$ 的具体值。所幸你可以进行最多 $2\times 10^4$ 次询问 int Query(const vector<int>& p)，表示组织向量 $p$ 中的所有变色龙开会。若变色龙 $i$ 参加会议，且 $L_i$ 也参加会议，变色龙 $i$ 就会将自己的颜色变成 $C_{L_i}$（不会修改 $L_i$），该函数会返回与会的所有变色龙的颜色数量。

你需要实现函数 void Solve(int n)，通过若干次询问求出每一对同色的异性变色龙，调用 $n$ 次 void Answer(int a, int b) 来报告你求出的答案。

对于 $40\%$ 的测试点，$n\leq 50$。对于 $100\%$ 的测试点，$1\leq n\leq 500$。

非常神奇的交互题，使我大脑旋转。

先来考虑 $40$ 分应该怎么做，为了获取尽可能多的有用信息，不妨获取所有 Query({i, j}) 的答案，记作 $Q(i,j)$。那么容易发现 $Q(i,j)\in \{1, 2\}$。

若 $Q(i,j)=1$，可以发现 $i,j$ 只能是如下关系之一：

• $C_i=C_j$，即 $i,j$ 是同色的异性变色龙。
• $L_i=j,L_j\neq i$，即变色龙 $i$ 喜欢变色龙 $j$，但 $j$ 不喜欢 $i$。
• $L_j=i,L_i\neq j$，即变色龙 $j$ 喜欢变色龙 $i$，但 $i$ 不喜欢 $j$。

我们发现变色龙之间的“同色”是一种双向关系，但是“喜欢”是一种单向关系。无论如何它们都是二元关系，因此可以考虑建图。对于 $C_i=C_j$，我们连一条黑色无向边 $(i,j)$，对于 $L_i=j$，我们连一条绿色有向边 $(i,j)$。那么我们就得到了一张混合图，例如：

如果将每条边都视为无向边，那么我们得到的其实是一张二分图（因为同色的两个变色龙是异性，变色龙也只会喜欢异性变色龙，所以性别就可以看成一组染色）。不妨将两条绿色的蓝边去除，这样子我们就得到了一张简单图，这样的好处是 $Q(i,j)=1$ 表明存在边 $(i,j)$：

对于 $40$ 分的数据，我们可以 $O(n^2)$ 暴力询问出所有 $Q(i,j)$，然后建出这张图，现在只需要关注如何通过这张图来求得答案。

考察每个点的度数，在原图上，每个点的度数应该都是 $3$，但是在新图上则出现了度数为 $1$ 的点，它是双向喜欢关系引起的，我们暂时忽略这些点。对于一个度数为 $3$ 的点 $i$，我们可以找出它的邻域 $\{x,y,z\}$，那么 $x,y,z$ 中一定有一只变色龙与 $i$ 同色，其余的是与 $i$ 间有喜欢 / 被喜欢关系的变色龙。

考虑如何找到那只与 $i$ 同色的变色龙，我们可以尝试挑出两只变色龙 $x,y$ 与 $i$ 一起组织会议，那么实际上有三种情况：

• $C_x=C_i,L_y=i$，即 $x$ 与 $i$ 同色，$y$ 喜欢 $i$。此时组织会议 $y$ 的颜色会变成 $C_i$，$x,i$ 不变，因此询问结果为 $1$。
• $C_x=C_i,L_i=y$，即 $x$ 与 $i$ 同色，$i$ 喜欢 $y$。此时组织会议 $i$ 的颜色会变成 $C_y$，$y,i$ 不变，因此询问结果为 $2$。
• $L_x=i,y=L_i$，即 $x$ 喜欢 $i$，$i$ 喜欢 $y$。此时组织会议 $x$ 的颜色会变成 $C_i$，$i$ 的颜色会变成 $C_y$，$y$ 不变。因此询问结果为 $2$。

那么我们可以通过两次询问中找到一组询问结果为 $1$ 的 $x,y$，此时我们至少可以确定 $L_i=z$，即在原图 / 新图中存在边 $(i,z)$，并且可以发现所有绿色边都可以通过这种方法找到，那么剩下的边自然也就是黑色边了。这一部分只需要 $\sim 2n$ 次询问，代码片段如下：

for(int i=1;i<=(n<<1);i++){
    int ngb[3], t = 0;
    for(int j=1;j<=(n<<1);j++) if(g[i][j]) ngb[t++] = j;
    if(t == 1) continue;
    auto query = [&](int x, int y, int z){
        if(Query({i, x, y}) == 1) return g[i][z] = g[z][i] = 2, 0;
        return 1;
    };
    auto [x, y, z] = ngb;
    if(query(x, y, z)) if(query(x, z, y)) g[i][x] = g[x][i] = 2;
}
for(int i=1;i<=(n<<1);i++){
    for(int j=1;j<i;j++) if(g[i][j] == 1) Answer(i, j);
}

我们发现要想拿到 $100$ 分，关键在于优化建图的过程（因为通过图来求答案不是瓶颈）。

这里就比较需要人类智慧了，我们考察新图的一个独立集，比如 $\{1,3,6,7\}$，那么如果让这些变色龙一起开会，答案肯定就是独立集的大小，但是这个条件并不充要（比如这些可怜的变色龙构成了三角恋或者四角恋之类的）。不过如果采用增量法，这就是显然成立的：

引理：对于新图的一个独立集 $I$，对于 $u\not\in I$，$I\cup \{u\}$ 也是独立集当且仅当 $I\cup\{u\}$ 这些变色龙组织会议时，答案恰好为 $|I|+1$。

那么可以通过 $n$ 次询问找出新图的一个独立集：增量法维护当前独立集 $I$，对于尝试加入的点 $u$，若 $I\cup\{u\}$ 的答案是 $|I|+1$，就将 $u$ 加入到 $I$ 中。

由于每个点的度数最多为 $3$，因此加入一个点最多排除之后的三个点，因此这个独立集的大小至少为 $\frac{n}{4}$。

独立集中肯定是没有边的，因此我们实际上给规模乘上了 $\frac{3}{4}$，不过还需要处理一下其他点连向独立集的边。

考虑枚举 $\overline{I}$ 中的每个点 $u$，考察 $u,I$ 之间有哪些边。注意到判定独立集 $I$ 的非空子集一定也是独立集，且判断独立集 $I'$ 与 $u$ 间有没有边，等价于判断 $I'\cup \{u\}$ 是否是独立集，因此可以进行若干次二分来找到所有与 $u$ 相连的独立集上的点，因此也就确定了这些边。

于是我们成功将规模为 $n$ 的问题，以 $O(n\log n)$ 的询问次数，$O(n^2\log n)$ 的时间复杂度归约到了一个规模为 $\frac{3}{4}n$ 的问题。因此我们可以删去独立集，重复上述操作直至点集为空。这样就询问出了新图的所有边。

分析一下总询问次数和时间复杂度。对于总询问次数，有 $T(n)=T(\frac{3}{4}n)+O(n\log n)=O(n\log n)$，对于时间复杂度有 $T(n)=T(\frac{3}{4} n)+O(n^2\log n)=O(n^2\log n)$，这大致是可以接受的（我的实现中，实测最大询问次数为 $18866$ 刚好可以通过），Submission。

UOJ361 【JOISC2017】Long Distance Coach

每日一道 JOISC （1 / 1）。

有一辆长途汽车在时刻 $0$ 从起点出发，在时刻 $X$ 到达终点，沿途经过 $n$ 个服务区，在时刻 $S_i$ 到达服务区 $i$。

汽车上有一个容量无限的水箱，在发车前水箱是空的。你可以在起点或服务区给水箱瞬间加水，但是加一升水需要 $W$ 元。本汽车有 $m$ 位乘客和一位司机。给定 $T$，乘客 $i$ 会在每个时刻 $kT+D_i\ (k\in\mathbb{N})$ 需要接一升水，司机会在每个时刻 $kT\ (k\in\mathbb{N})$ 需要接一升水。

如果乘客 $i$ 在某个时刻没有接到水，那么他就会怒而下车，此时需要支付 $C_i$ 元赔偿。如果司机在某个时刻没有接到水，那么车就会抛锚，这是禁止的。你需要求出最少要花费多少元（包括水费和赔偿金）。

保证一个时刻最多只会有最多一个人需要接水，保证在时刻 $X$ 或到达服务区时，没有人需要接水。

$1\leq T\leq X\leq 10^{12},1\leq n,m\leq 2\times 10^5,1\leq W\leq 10^6,1\leq C_i\leq 10^9$。

首先你发现并没有很直观的多项式级别的做法，这让你意识到了问题的严重性。

引理：如果在一段 $(S_i,S_{i+1})$ 中需要赶人下车，那么如果将每个乘客按照 $D_i$ 排序，那么一定是赶走一段连续区间的乘客，并且赶人的时机是在到达 $S_{i+1}$ 的最后一个周期。

如何理解这一引理？首先如果在一段中 $(S_i,S_{i+1})$ 需要赶两个无交的不连续区间 $[l_1,r_1],[l_2,r_2]$ 的乘客下车，那么乘客 $r_1$ 一定没有接到水，那么介于区间 $[r_1+1,l_2-1]$ 的乘客一定也没有接到水，也会下车，所以实际上赶走了 $[l_1,r_2]$ 的乘客，是一段连续的区间。如果考虑在中间的一个周期赶人而不是最后一个周期赶人，那么司机一定也没有接到水，而这是禁止的。所以一定是在最后一个周期赶人。

于是可以枚举每一段赶走了多少人来做到 $O(m^n)$，显然是不可行的。

考虑换一个想法，改为决策每个乘客是否要赶走，结合前面连续区间的结论，很容易想到 dp，设 $f_i$ 表示按照 $D_i$ 排序的前 $i$ 个乘客，最少需要花费多少元在他们身上。

如何转移？可以发现有两种转移。一种转移是不赶走他，那么就需要结清所有他接的水的水费：

$$f_i\gets f_{i-1}+W\cdot \left(\left\lfloor \frac{X - D_i}{T} \right\rfloor + 1\right)$$

另一种转移是赶走他，我们不妨钦定这是被赶走的一段乘客区间的结尾。那么可以得到：

$$f_i\gets\min_{k=0}^{i-1} f_k+\sum_{t=k+1}^{i} C_t + Wt_i$$

也就是枚举赶走的一段区间，先支付赔偿金 $C_t$，然后支付下车前的水费 $Wt_i$，$t_i$ 表示乘客 $i$ 被赶走时，他最少需要接多少水。由于赶走一定是在一段的末尾，那么可以看成每一段的右端点找一个前驱，这可以二分查找，$O(n\log m)$ 完成。

不妨记录 $P_i=\sum_{k=1}^{i} C_k$，那么转移可以写成：

$$f_i=\min\left(f_{i-1}+W\cdot \left(\left\lfloor \frac{X - D_i}{T} \right\rfloor + 1\right), \min_{k=0}^{i-1} f_k+P_i-P_k+Wt_i(i-k)\right)$$

最后记得加上司机的水费，直接转移时间复杂度为 $O(m^2)$，可以获得 $71$ 分，Submission。

优化，第一种转移可以单次 $O(1)$ 完成，关键在第二种询问，尝试改写一下式子：

$$\begin{aligned} &f_i\gets f_k+P_i-P_k+Wt_i(i-k)\\ &f_i-P_i-Wt_i i\gets -Wk t_i + (f_k-P_k) \end{aligned}$$

可以看成动态插入一次函数，查询一次函数在 $x=t_i$ 时的最小值，李超线段树即可。时间复杂度 $O(n\log m+m\log V)$ 可以通过本题，Submission。

UOJ671 【UNR #5】诡异操作

给定一个长度为 $n$ 的序列 $a$，有 $q$ 次操作，支持：

• 1 l r v：$\forall a_i\in [l, r], a_i\gets \left\lfloor \frac{a_i}{v} \right\rfloor$，保证 $v_i\geq 1$。
• 2 l r v：$\forall a_i\in[l, r] a_i\gets a_i\& v$，其中 $\&$ 表示按位与运算。
• 3 l r：计算 $\sum\limits_{k=l}^{r} a_k \pmod{2^{128}}$。

$1\leq n\leq 3\times 10^5,1\leq q\leq 2\times 10^5,0\leq a_i<2^{128}$。时间限制 $2\text{s}$，空间限制 $1024\text{MB}$。

一个区间除，一个区间按位与，一个区间求和，操作确实很诡异。

对于区间除，经典方法是势能线段树，在每个节点维护一个 $\mathrm{zero}$ 表示这个区间是否全为 $0$，修改节点时，如果 $\mathrm{zero}$ 不成立，那么就向下递归，记得判掉 $v=1$ 的情况，那么每次一个每个元素至少减半，匡爷教导我这个东西的时间复杂度其实是 $O(n\log V)$ 的。

考虑区间与，可以拆位，对于每一位维护一下该位在区间中的出现次数，那么我们需要在每个节点维护长度为 $O(\log V)$ 的值域至多为 $n$ 的序列，时间复杂度 $O(q\log n\log V)$ 不能通过。

我们发现 $V$ 很大而 $n$ 很小，将维护的东西转置，变成维护一个长度为 $O(\log n)$ 的值域至多为 $V$ 的序列，表示有哪些位的方案数有 $2^i$ 这一位。那么 make tag 是容易的，pushup 的时候就是手动模拟加法，需要考虑进位。时间复杂度 $O(n\log V+q\log^2 n)$。可以通过本题，Submission。

AGC059C Guessing Permutation for as Long as Possible

有一个长度为 $n$ 的排列 $p$，并给定一个长度为 $\frac{n(n-1)}{2}$ 的序列 $A$，包含了所有满足 $1\leq a<b\leq n$ 的二元组 $(a,b)$。然后会进行一个游戏，第 $i$ 轮时主持人会告诉你 $A_i=(a,b)$ 中是否满足 $p_a<p_b$。如果存在一个排列 $p$ 使得你在每一轮都不能正确预知主持人的回答，那么称这个排列是好的。你需要求出有多少个好的排列，答案对 $10^9+7$ 取模。

$1\leq n\leq 400$。

考虑对于三元组 $(a,b,c)$，如果 $(a,b)$ 和 $(b,c)$ 在 $A$ 序列中排在 $(a,c)$ 之前，且获悉了 $p_a<p_b$，那么对于好的排列 $p$，$p_b<p_c$ 一定不成立（因为这样就可以推断出 $p_a<p_c$ 了），所以只能有 $p_b>p_c$，反之亦然。

考虑通过每一个二元组的答案来计算排列的数量，那么每个二元组有小于和大于两种结果，并且有形如【若 $A$ 的 $p$ 成立，则 $B$ 的 $q$ 成立】这种约束，直接套用 2-SAT 即可。

最后计数时，对于每一个强连通分量肯定只能选择同样的结果，但是由于我们给每一个二元组都拆成了两个点，所以如果有解的话，一定强连通分量可以两两一组，每一组都必须得到不同的结果。所以答案就是 $2^{\frac{c}{2}}$，其中 $c$ 表示强连通分量的数量。

时间复杂度 $O(n^3)$，Submission。

ARC176E Max Vector

给定两个长度为 $n$ 的序列 $X,Y$ 和一个 $m\times n$ 的矩阵 $A$。你需要恰好进行 $m$ 次操作，第 $i$ 次操作选择下列两个操作中的一个执行：

• 令 $\forall k\in[1, n], X_k\gets \max(X_k,A_{i,k})$。
• 令 $\forall k\in[1, n], Y_k\gets \max(Y_k,A_{i,k})$。

求出最终 $\sum_{i=1}^{n} X_i+Y_i$ 的最小值。

$1\neq n\leq 10,1\leq X_i,Y_i,A_{i,j},m\leq 500$。

首先看到题意应该可以想到不少贪心，但是这些贪心几乎都是假的。不过参考 P3227 [HNOI2013] 切糕，不妨想想最小割建模。

由于 $X,Y,A$ 三者的值域都不大，因此可以考虑用切糕一题的方法将每个 $X_i,Y_i$ 拆成一条链。具体地，我们取一个值域上界 $V$，将 $X_i$ 拆成 $V$ 个点 $U_{i, 1}, U_{i, 2}, \cdots, U_{i, V}$。然后连边 $(U_{i,j}, U_{i,j+1}, j), (S, U_{i,1}, +\infty), (U_{i, n}, T, V)$。另外 $X_i$ 初始时已经有了一个下界（也就是初始值），我们连边 $(S,U_{i,X_i},+\infty)$ 来保证总是割断 $X_i$ 及以后的边。

对于 $Y_i$ 也是类似的，不过为了体现他们的不同，我们不妨将 $Y$ 倒过来拆成一条链：

然后我们考虑第 $k$ 次操作，枚举 $i$ 考察限制 $A_{k,i}$。我们新建一个点 $O$，$O$ 划分到 $S$ 割集意味着我们选择 $X$，否则选择 $Y$，连边 $(O, U_{i, A_{k, i}}, +\infty)$ 以及 $(V_{i, A_{k, i}}, O, +\infty)$。前者表示当 $O$ 划分到 $S$ 割集时，$U_{i, A_{k,i}}$ 始终在 $S$ 割集，那么 $X_i$ 就必须大于等于 $A_{k,i}$；后者同理。

如何判断与 $O$ 连接的两种边的方向

当 $O$ 被划分到割集 $S$ 时，可以将 $O$ 就看成 $S$，那么肯定是 $O\to U$ 不是 $U\to O$，$V$ 同理。

根据最小割最大流定理，我们可以用最大流算法求该图的最小割。时间复杂度 $O(\mathrm{maxflow}(Vn+m, n(V+m)))$ 可以通过本题，Submission。