admin官方

下面给出一种基于差分和闭合集合判定的做法。

设 di=bi−aid_i=b_i-a_i，表示第 ii 个位置最终需要的净变化量。为了方便处理边界，令 d0=dn+1=0d_0=d_{n+1}=0，并定义差分 Δi=di−di−1\Delta_i=d_i-d_{i-1}，其中 1≤i≤n+11\le i\le n+1。

一次区间操作只会影响差分数组的两个端点。若对区间 [l,r][l,r] 减小 11，则 Δl−=1,Δr+1+=1\Delta_l\mathrel{-}=1,\Delta_{r+1}\mathrel{+}=1；若对区间 [l,r][l,r] 增加 11，则 Δl+=1,Δr+1−=1\Delta_l\mathrel{+}=1,\Delta_{r+1}\mathrel{-}=1。

把差分位置 1,2,…,n+11,2,\ldots,n+1 看成点。一次合法的区间减小操作 [l,r][l,r] 满足 r≥plr\ge p_l，它对应一条边 l→r+1l\to r+1。一次合法的区间增加操作 [l,r][l,r] 满足 l≤qrl\le q_r，它对应一条边 r+1→lr+1\to l。

若沿边 u→vu\to v 使用一次操作，则差分变化为 Δu−=1,Δv+=1\Delta_u\mathrel{-}=1,\Delta_v\mathrel{+}=1。因此问题等价于：在这些有向边上发送若干单位流量，使得每个点的净流入减净流出等于 Δi\Delta_i。

考虑一个点集 SS。如果从 SS 中的点出发的所有边仍然指向 SS 内部，则称 SS 为一个出边闭合集合。对于这样的集合，流量无法从 SS 流到外部，所以必须满足 ∑i∈SΔi≥0\sum_{i\in S}\Delta_i\ge 0。反过来，由最大流最小割可知，只要所有出边闭合集合都满足这个条件，就一定存在可行方案。

所以我们只需要判断是否存在一个出边闭合集合，使得其中 Δi\Delta_i 的和为负。

下面刻画所有出边闭合集合。令 m=n+1m=n+1。对每个点 ii，定义 Li=0 (i=1)L_i=0\ (i=1)，Li=qi−1 (2≤i≤m)L_i=q_{i-1}\ (2\le i\le m)；同时定义 Ri=pi+1 (1≤i≤n)R_i=p_i+1\ (1\le i\le n)，Rm=m+1R_m=m+1。

如果闭合集合中包含点 ii，那么它必须包含前缀 [1,Li][1,L_i] 和后缀 [Ri,m][R_i,m]。因此任意闭合集合都可以写成 [1,L]∪[R,m]∪M[1,L]\cup[R,m]\cup M，其中 M⊆(L,R)M\subseteq(L,R)。

边界 (L,R)(L,R) 合法需要满足 max⁡i≥RLi≤L\max_{i\ge R}L_i\le L 以及 min⁡i≤LRi≥R\min_{i\le L}R_i\ge R。固定合法的 L,RL,R 后，一个中间点 ii 可以被额外选入，当且仅当 L<i<RL<i<R，Li≤LL_i\le L 且 Ri≥RR_i\ge R。为了让集合权值和尽量小，只需要选入这些中间点中所有 Δi<0\Delta_i<0 的点。

令 Sx=∑i=1xΔiS_x=\sum_{i=1}^x\Delta_i。固定 L,RL,R 时，前缀和后缀的贡献为 SL−SR−1S_L-S_{R-1}，中间负点的贡献为所有满足 L<i<RL<i<R、Li≤LL_i\le L、Ri≥RR_i\ge R 且 Δi<0\Delta_i<0 的点的 Δi\Delta_i 之和。

接下来枚举 LL，用线段树维护每个 RR 对应的值 −SR−1+当前可选负点贡献-S_{R-1}+\text{当前可选负点贡献}。这样对于固定的 LL，只需要查询合法 RR 中的最小值，再加上 SLS_L，就能得到当前所有闭合集合的最小权值。

一个负点 ii 会在 L∈[Li,i−1]L\in[L_i,i-1] 且 R∈[i+1,Ri]R\in[i+1,R_i] 时产生贡献。因此扫描 LL 时，在 L=LiL=L_i 将 Δi\Delta_i 加到线段树区间 [i+1,Ri][i+1,R_i] 上，在 L=iL=i 时再删除这份贡献。

为了判断哪些 RR 合法，预处理 AR=max⁡i≥RLiA_R=\max_{i\ge R}L_i 和 BL=min⁡i≤LRiB_L=\min_{i\le L}R_i。对于当前 LL，合法的 RR 需要满足 AR≤LA_R\le L、R≤BLR\le B_L 且 R>LR>L。在线段树上查询所有合法 RR 的最小值即可。

若存在某个 LL 使得 SL+min⁡R<0S_L+\min_R<0，说明存在权值和为负的出边闭合集合，答案为 NO；否则所有闭合集合的权值和都非负，答案为 YES。

正确性来自上述转化。差分后，每次操作等价于在有向边上发送一单位流量，原问题等价于有向图上的流可行性问题。对于任意出边闭合集合，集合内部无法向外部发送流量，所以其 Δ\Delta 和必须非负；最大流最小割保证这个条件也是充分的。随后对闭合集合的刻画没有遗漏任何可能的集合，扫描线和线段树又对每个合法边界 (L,R)(L,R) 都取到了最小可能权值，因此判定结果正确。

复杂度方面，每个负点只会产生一次区间加入和一次区间删除，线段树支持区间加和区间最小值查询。因此单组数据时间复杂度为 O(nlog⁡n)O(n\log n)，总时间复杂度为 O(∑nlog⁡n)O(\sum n\log n)，空间复杂度为 O(n)O(n)。

本题的部分分从小值域和小规模开始。特殊性质 A 中 nn 与数值都很小，可以用搜索或状态图判断可达性，帮助选手理解区间加减操作的本质。中等规模数据可以通过差分建模，把一次区间操作转化为差分数组两个端点的变化。特殊性质 B 中 pi=qi=ip_i=q_i=i，操作限制退化得更简单，选手可以先解决这种局部结构较强的情况。满分数据则需要把差分上的操作理解为有向图中的流量，并进一步用闭合集合判定和数据结构优化。