让我们重新表述一下这个问题：构建一个网络流模型，$s \to i$ 流量为 $a_i$，$i \to [l_i + n, r_i + n]$ 流量为 $\inf$，$i + n \to t$ 流量为 $c_i$。

要求改变区间后，对每个 $x$ 求出最大流。

---

回忆 Hall 定理：

• 一个二分图对右部点有完美匹配，当且仅当对于任何右部点集合 $S$ 满足 $\lvert N(S) \rvert \geq \lvert S \rvert$；
• 推广：一个带权二分图对右部点有带权完美匹配，当且仅当对于任何右部点集合 $S$ 满足 $Val(N(S)) \geq Val(S)$。

设 $X = Val(S)$，$Y = Val(N(S))$。此处的完美匹配就是 $\sum c_i$。由于 Hall 定理只给出了完美匹配的标准，我们必须修改它让它能够计算最大流。比如说，增加一个能被所有磁铁匹配的权值为 $s$ 的铁钉，那么：只要 $X \leq Y + s$，我们就能断言最大流的值，因此我们只要找到 $s = \max(X - Y)$（再次注意，$\bm X$ 是磁铁，而 $\bm Y$ 是铁钉）。

固定 $Y$，我们想要最大化 $X$，可以加入所有使 $Y$ 不变的磁铁，那么对于 $1 \leq l \leq x \leq r \leq n$，如果 $\leq x$ 的磁铁编号最大为 $l$，$\geq x$ 的磁铁编号最小为 $r$，那么显然可以加入 $[1, l] \cup [r, n]$ 的所有磁铁。

令 $c[L, R]$ 表示 $c_L + c_{L+1} + \dots + c_R$，$a[L, R]$ 表示 $L \leq l_i \leq r_i \leq R$ 的铁钉的 $a_i$ 之和。固定 $l, r$，显然

$$X - Y = \sum_{i=1}^m c_i - \sum_{i=l+1}^{r-1} c_i - \sum_{i=1}^n a_i + a[l + 1, r - 1] $$

删去容易计算的常量，我们只考虑 $a[l + 1, r - 1] - c[l + 1, r - 1]$，也就是 $a[l, r] - c[l, r]$。排除掉平凡的情况（如果 $l = x$ 或 $r = x$，我们事实上相当于可以加入所有的 $X$ 和所有的 $Y$），我们只考虑用 $a[l, r] - c[l, r]$ 对 $l \leq x \leq r$ 的所有 $x$ 快速 $\text{chkmax}$。

---

我们采用分治的方式解决上述问题。让我们设 $\text{solve}(L, R)$ 表示解决 $L \leq l \leq r \leq R$ 的所有问题。

首先，取 $M = \lfloor\frac{L + R}{2}\rfloor$ 并递归解决。然后我们便只关心 $L \leq l \leq M$，$M + 1 \leq r \leq R$ 的问题。显然这个问题对于 $x \leq M$ 和 $x \geq M + 1$ 又不同了，如果仅考虑 $x \leq M$：显然 $r$ 一端的后缀我们只要取一个最大值即可，线段树维护，于是扫描一下 $l$。另一侧同理。

需要一颗线段树支持区间 $\text{chkmax}$ $\mathcal O((n + m)\log m)$ 次，另一颗线段树支持区间加、区间 $\text{querymax}$ $\mathcal O((n + m)\log m)$ 次，复杂度是 $\mathcal O((n + m)\log^2 m)$ 的。

std::vector<std::pair<int, int>> Rp[MAXN], Lp[MAXN];
void dc_L(int l, int r) {
	if (l == r) { for (auto [r, v] : Rp[l]) T2::add(r, N, v); T1::chkmax(l, l, T2::query(l, l) + s[l - 1]); return; }
	int mid = l + r >> 1; dc_L(mid + 1, r);
	for (int k = mid; k >= l; --k) {
		for (auto [r, v] : Rp[k]) T2::add(r, N, v);
		long long val = T2::query(mid + 1, r) + s[k - 1];
		T1::chkmax(k, mid, val);
	}
	for (int k = l; k <= mid; ++k) for (auto [r, v] : Rp[k]) T2::add(r, N, -v);
	dc_L(l, mid);
}
void dc_R(int l, int r) {
	if (l == r) { for (auto [l, v] : Lp[r]) T2::add(1, l, v); T1::chkmax(r, r, T2::query(r, r) - s[r]); return; }
	int mid = l + r >> 1; dc_R(l, mid);
	for (int k = mid + 1; k <= r; ++k) {
		for (auto [l, v] : Lp[k]) T2::add(1, l, v);
		long long val = T2::query(l, mid) - s[k];
		T1::chkmax(mid + 1, k, val);
	}
	for (int k = mid + 1; k <= r; ++k) for (auto [l, v] : Lp[k]) T2::add(1, l, -v);
	dc_R(mid + 1, r);
}

可以通过限制区间范围和减少区间撤销、减少 $\text{chkmax}$ 操作等方式来卡常（在上述代码中没有展示出来，请选手各显神通）。

---

这里的 Hall 定理形式与最小割几乎类似，就留给读者细究。