前置知识：拟阵。

不会拟阵大概只能感性理解做法正确性了。

为了方便，我们将 $L,R$ 的定义改为：当松鼠横坐标为 $i-0.5$ 时，高度必须在 $[L_i,R_i]$ 之间。特别地，令 $L_0=R_0=0$。若 $R_n<h$ 则全部无解，否则再令 $L_n=R_n=h$。

容易发现，令 $L_i\gets \max\limits_{j=0}^i L_j$，$R_i\gets\min\limits_{j=i}^n R_j$ 不影响答案，而做了这一步处理之后 $L,R$ 均不减。

转换视角，对于每个 $0\leq i<h$，我们可以求出，能让高度从 $i$ 增加到 $i+1$ 的柱子编号区间 $[l_i,r_i]$。那么我们相当于要选择执行升高操作的柱子编号序列 $b_{0\sim h-1}$，满足 $b$ 单调递增且 $b_i\in [l_i,r_i]$。

考虑建出二分图，左部点为 $0,\cdots,n-1$，右部点为 $0,\cdots,h-1$，每个右部点 $i$ 向 $[l_i,r_i]$ 内的所有左部点连边。注意到 $l,r$ 同样不减，因此一个大小为 $h$ 的左部点集合实际上就对应了一个合法的 $b$。这是因为，我们可以令 $b_i$ 为右部点 $i$ 对应的左部点，如果出现了 $i<j\land b_i>b_j$ 的交叉结构，由 $l,r$ 的单调性，必然有 $l_i\leq l_j\leq b_j<b_i\leq r_i\leq r_j$，于是交换 $b_i,b_j$ 仍然满足区间限制。一直交换下去，即可得到，将 $b$ 从小到大排序后依然满足区间限制。

问题转化为：左部点有红蓝染色和权值 $a_i$，一个匹配的权值为左部点的权值和。对于每个 $0\leq k\leq h$，求出恰好包含 $k$ 个蓝点的大小为 $h$ 的最小权匹配。

设 $E=\{0,\cdots,n-1\}$，$\mathbf{B}$ 为所有合法的 $b$ 构成的族。我们证明一个很强的性质：对于任意两个基 $B_1,B_2\in \mathbf{B}$，存在双射 $f:B_1\to B_2$，使得对于任意的 $S\subseteq B_1\setminus B_2$，$(B_1\setminus S)\cup f(S)\in\mathbf{B}$。

:::info[证明]

将 $B_1,B_2$ 中的元素从小到大排序，设 $B_1=\{x_1,\cdots,x_k\},B_2=\{y_1,\cdots,y_k\}$,我们直接构造 $f(x_i)=y_i$。

考察任意一个子集 $S\subseteq B_1\setminus B_2$，设 $(B_1\setminus S)\cup f(S)=\{z_1,\cdots,z_k\}$，其中 $z_i = \begin{cases} y_i, & \text{if } i \in S, \\ x_i, & \text{if } i \notin S \end{cases}$。设 $z$ 从小到大排序后得到的序列为 $z'$，我们只需证明 $z'_i\in[l_i,r_i]$。

注意到 $z_{i\sim k}$ 必然都 $\geq l_i$，这说明 $z$ 中至少有 $k-i+1$ 个元素 $\geq l_i$，因此必然有 $z'_i\geq l_i$。同理可以得到 $z'_i\leq r_i$。$\Box$

:::

这个性质被叫做 Strongly Base Orderable，下面简称为 SBO。

显然 SBO 严格强于基交换定理，因此我们可以由 $(E,\mathbf{B})$ 定义出一个拟阵。进一步地，其实 $\mathcal{I}$ 就是所有能被一组匹配完全覆盖的左部点集合构成的族。

考虑左部点全为红色怎么做，相当于求最小权基。因为构成拟阵结构，可以直接贪心：将所有左部点按权值从小到大排序，维护一个初始为空的集合 $S$，遍历每个点 $i$，若 $S\cup \{i\}\in \mathcal{I}$ 就把 $i$ 加到 $S$ 中。容易想到使用 Hall 定理判定：$\forall T\subseteq S,|T|\leq |N(T)|$。套路地，我们指出一个等价的条件：$\forall 0\leq l\leq r<n,|S\cap[l,r]|\leq |N([l,r])|$。

:::info[证明]

先证必要性。设 $T=S\cap [l,r]$，则 $|T|\leq |N(T)|\leq |N([l,r])|$。

再证充分性。对于单个元素 $x$，$N(x)$ 是一个连续的右部点区间 $[c_x,d_x]$，这里 $c,d$ 均单调不减。不妨将 $N(S)=\bigcup\limits_{x\in S}[c_x,d_x]$ 分解成若干个极长的连续区间 $P_1,\cdots P_k$ 的并，同时我们可以把 $S$ 划分成对应的 $S_1,\cdots,S_k$ 的并。若 $|S|>|N(S)|$，则必然存在一个 $S_i$ 使得 $|S_i|>|N(S_i)|$，我们考察这个不合法的 $S_i$。考虑区间 $[\min(S_i),\max(S_i)]$，那么 $|S_i\cap [\min(S_i),\max(S_i)]|=|S_i|$，而我们知道 $N(S_i)$ 是一个连续区间，不难得出 $N([\min(S_i),\max(S_i)])=N(S_i)$，因此我们会在 $[\min(S_i),\max(S_i)]$ 处判定出不合法。$\Box$

:::

设 $sum_i=\sum\limits_{j=0}^i [j\in S]$，则 $|S\cap [l,r]|=sum_r-sum_{l-1}$。再设 $preL_i=\sum\limits_{j=0}^{h-1}[l_j\leq i]$，$preR_i=\sum\limits_{j=0}^{h-1}[r_j\leq i]$，则 $|N([l,r])|=preL_r-preR_{l-1}$。于是我们只需要判定 $sum_r-sum_{l-1}\leq preL_r-preR_{l-1}\Leftrightarrow sum_{l-1}-preR_{l-1}\geq sum_r-preL_r$。使用线段树维护区间内的 $\min(sum_i-preR_i)$，$\max(sum_i-preL_i)$ 和 $\min\limits_{l\leq i<j\leq r}\{(sum_i-preR_i)-(sum_j-preL_j)\}$ 即可。这样我们就可以 $\mathcal{O}(n\log{n})$ 解决左部点全为红色的情况。

尝试拓展到红蓝染色的情况。由 SBO 不难看出，若存在蓝点个数为 $i,j(i<j)$ 的基，则 $\forall i<k<j$，必然也存在蓝点个数为 $k$ 的基，因此有解的蓝点个数是一段连续区间 $[mn,mx]$。进一步地，考察 $T_{k-1}$ 和 $T_{k+1}$，设它们对应的基分别为 $B_{k-1},B_{k+1}$，则必然存在一个红蓝点对 $(r,b)$，使得 $B_1=B_{k-1}\setminus\{r\}\cup\{b\}$ 和 $B_2=B_{k+1}\setminus\{b\}\cup\{r\}$ 都是基，于是

$$T_{k-1}+T_{k+1}=w(B_{k-1})+w(B_{k+1})=w(B_1)+w(B_2)\geq 2T_k$$

因此 $T$ 在有解的区间内是下凸的。使用 WQS 二分可以 $\mathcal{O}(n\log{n}\log{V})$ 求解单个 $T_k$。

进一步挖掘相邻两个基 $B_i,B_{i+1}$ 的性质。考察二元组集合 $S=\{(u,f(u))\mid u\in B_i\setminus B_{i+1}\}$，其中至少存在一个红蓝点对 $(r,b)$，设 $S'=S\setminus\{(b,r)\}$，取 $B_i'=(B_i\setminus S')\cup f(S')$。若 $w(B_i')<w(B_i)$，则和 $B_i$ 是最优解矛盾；而若 $w(B_i')\geq w(B_i)$，则 $B_i\setminus \{r\}\cup\{b\}$ 不劣于 $B_{i+1}$。于是相邻两个基之间恰好会差一个红蓝点对。

考虑这样的贪心：先求出一个蓝点数最少的 $B_{mn}$，将所有不在 $B_{mn}$ 中的蓝点按权值从小到大排序，设为 $b_{mn+1\sim mx}$。维护一个初始为 $B_{mn}$ 的基 $B$，按顺序考虑每个蓝点 $b_i$，取唯一环 $C(B,b_i)$ 中权值最大的红点 $r_i$，设 $\Delta_i=w(b_i)-w(r_i)$，然后令 $B\gets B\setminus \{r_i\}\cup\{b_i\}$。最后将 $\Delta_{mn+1\sim mx}$ 从小到大排序，依次累加得到 $T$。

我们来证明这个做法的正确性。

::::info[证明]

先给出一些引理。

引理 $1$：该算法在考虑完 $b_i$ 后得到的基 $B$，是蓝点集合恰为 $b_{1\sim i}$ 的最小权基。

:::info[证明]

使用数学归纳法。

当 $i=mn$ 时，命题显然成立。

接下来假设命题在 $i-1$ 处成立，对应最小权基为 $B_1$，再设蓝点集合恰为 $b_{1\sim i}$ 的最小权基为 $B_2$。利用 SBO 性质不难得出 $B_1,B_2$ 间同样只差一个红蓝点对 $(r,b_i)$，而我们取了 $r$ 为 $C(B_1,b_i)$ 中权值最大的红点，显然可以最小化 $w(B_2)$。$\Box$

:::

引理 $2$：对于任意拟阵 $(E,\mathcal{I})$，设 $B$ 为其最小权基。定义 $S(k)=\{x\in E\mid w(x)<k\}$，则

$$\forall x\notin B,x\in\operatorname{cl}(S(k))\Leftrightarrow\max_{y\in C(B,x)\setminus\{x\}}w(y)<k$$

:::info[证明]

先证充分性。显然 $C(B,x)\setminus\{x\}\subseteq S(k)$，由闭包的单调性，立刻得到 $x\in\operatorname{cl}(C(B,x)\setminus\{x\})\subseteq \operatorname{cl}(S(k))$。

再证必要性。根据贪心算法的性质，可以看出 $B\cap S(k)$ 是 $S(k)$ 的最大独立集，因此 $\operatorname{cl}(S(k))=\operatorname{cl}(B\cap S(k))$，这说明存在环 $C$ 使得 $x\in C\subseteq (B\cap S(k))\cup\{x\}$，又因为 $(B\cap S(k))\cup\{x\}\subseteq B\cup\{x\}$，可以得出 $C=C(B,x)$，因此 $C(B,x)\setminus\{x\}\subseteq B\cap S(k)$。$\Box$

:::

考察 WQS 二分的过程，相当于引入了一个参数 $\lambda$，令蓝点的权值全体减去 $\lambda$，然后跑贪心算法。设贪心算法得到的基为 $B_{\lambda}$，我们尝试证明：

$$b_i\in B_{\lambda}\Leftrightarrow\lambda\geq \Delta_i$$

设算法考虑完 $b_{i-1}$ 后得到的基为 $B$。再设 $R(k)=\{r\in R\mid w(r)<k\}$，其中 $R$ 为红点集合。由闭包定义，不难得出，$b_i\in B_{\lambda}\Leftrightarrow b_i\notin\operatorname{cl}(\{b_1,\cdots,b_{i-1}\}\cup R(w(b_i)-\lambda))$。不妨分析收缩拟阵 $E'=E/\{b_1,\cdots,b_{i-1}\}$，此时：

• 闭包条件化为 $b_i\notin\operatorname{cl}(R(w(b_i)-\lambda))$。
• 由引理 $1$，$B\setminus\{b_1,\cdots,b_{i-1}\}$ 是 $E'$ 的最小权基。
• 基本环 $C(B,b_i)$ 变为 $C(B,b_i)\setminus\{b_1,\cdots,b_{i-1}\}=C(B,b_i)\cap R$。

直接运用引理 $2$：

$$b_i\in\operatorname{cl}(R(w(b_i)-\lambda))\Leftrightarrow \max_{r\in C(B,b_i)\cap R}w(r)<w(b_i)-\lambda$$

这完全等价于

$$b_i\notin B_{\lambda}\Leftrightarrow r_i<b_i-\lambda\Leftrightarrow \Delta_i>\lambda$$

因此 $b_i\in B_{\lambda}\Leftrightarrow\lambda\geq \Delta_i$。

不难看出这验证了我们的做法正确性。$\Box$

::::

尝试维护出 $C(B,b_i)$ 中的元素，也就是找出 $B\cup\{b_i\}$ 中可删的红点位置。我们知道一个区间 $[l,r]$ 合法当且仅当 $val(l,r)=(sum_{l-1}-preR_{l-1})-(sum_r-preL_r)\geq 0$。加入 $b_i$ 相当于给 $sum$ 后缀加 $1$，会令所有 $l\leq b_i\leq r$ 的区间的 $val$ 减 $1$；删除 $r_i$ 相当于后缀减 $1$，会令所有 $l\leq r_i\leq r$ 的区间的 $val$ 加 $1$。因此 $r_i$ 在环中，当且仅当所有包含 $b_i$ 且 $val$ 为 $0$ 的区间 $[l,r]$ 都包含 $r_i$。因此我们只需要找出包含 $b_i$ 的限制最紧的左右端点 $L,R$，那么 $r_i$ 自然就是 $[L,R]$ 可用的红点中权值最大的那个，容易用线段树维护。同时，我们只需找出 $[0,b_i)$ 中 $sum_l-preR_l$ 最靠右的最小值位置 $mnp$，以及 $(b_i,n)$ 中 $sum_r-preL_r$ 最靠左的最大值位置 $mxp$，则 $L=mnp+1,R=mxp$，一样使用线段树维护。

这样我们就 $\mathcal{O}(n\log{n})$ 解决了本题。

代码并不难写。

:::success[主要代码]

struct Node {
	int mn, mnp, mx, mxp, df;
	friend Node operator+(const Node &lhs, const Node &rhs) {
		return {
			min(lhs.mn, rhs.mn),
			rhs.mn <= lhs.mn ? rhs.mnp : lhs.mnp,
			max(lhs.mx, rhs.mx),
			lhs.mx >= rhs.mx ? lhs.mxp : rhs.mxp,
			min({lhs.df, rhs.df, lhs.mn - rhs.mx})
		};
	}
	Node &operator+=(const Node &rhs) { return *this = *this + rhs; }
};

struct SegTree1 {
#define ls(p) (p << 1)
#define rs(p) (p << 1 | 1)
	Node nd[MAXN << 2];
	int tg[MAXN << 2];
	void push_up(int p) { nd[p] = nd[ls(p)] + nd[rs(p)]; }
	void make_tg(int p, int v) { tg[p] += v, nd[p].mn += v, nd[p].mx += v; }
	void push_down(int p) { if (tg[p]) make_tg(ls(p), tg[p]), make_tg(rs(p), tg[p]), tg[p] = 0; }
	void build(int p, int l, int r) {
		if (l == r) return nd[p] = {-preR[l], l, -preL[l], l, inf}, void();
		int mid = l + r >> 1;
		build(ls(p), l, mid), build(rs(p), mid + 1, r);
		push_up(p);
	}
	void add(int p, int l, int r, int x, int y, int v) {
		if (x <= l && y >= r) return make_tg(p, v);
		push_down(p);
		int mid = l + r >> 1;
		if (x <= mid) add(ls(p), l, mid, x, y, v);
		if (y > mid) add(rs(p), mid + 1, r, x, y, v);
		push_up(p);
	}
	Node query(int p, int l, int r, int x, int y) {
		if (x <= l && y >= r) return nd[p];
		push_down(p);
		int mid = l + r >> 1;
		Node res = {inf, 0, -inf, 0, inf};
		if (x <= mid) res = query(ls(p), l, mid, x, y);
		if (y > mid) res += query(rs(p), mid + 1, r, x, y);
		return res;
	}
#undef ls
#undef rs
} sgt1;

struct SegTree2 {
#define ls(p) (p << 1)
#define rs(p) (p << 1 | 1)
	pii mx[MAXN << 1];
	int n;
	void build(int n_) { n = n_, fill(mx + 1, mx + (n << 1), pii{-inf, 0}); }
	void upd(int p, pii v) {
		mx[p += n - 1] = v;
		while (p > 1) p >>= 1, mx[p] = max(mx[ls(p)], mx[rs(p)]);
	}
	pii query(int l, int r) {
		pii resL = {-inf, 0}, resR = {-inf, 0};
		for (l += n - 1, r += n - 1; l <= r; l >>= 1, r >>= 1) {
			if (l & 1) chk_max(resL, mx[l++]);
			if (~r & 1) chk_max(resR, mx[r--]);
		}
		return max(resL, resR);
	}
#undef ls
#undef rs
} sgt2;

vector<ll> fly(int H, vector<int> A, vector<int> B, vector<int> L, vector<int> R) {
	int N = A.size();
	copy(A.begin(), A.end(), a + 1);
	copy(B.begin(), B.end(), b + 1);
	copy(L.begin(), L.end(), tmpL + 1);
	copy(R.begin(), R.end(), tmpR + 1);
	if (tmpL[N] > H || tmpR[N] < H) return vector<ll>(H + 1, -1);
	tmpL[N] = tmpR[N] = H;
	for (int i = 1; i <= N; ++i) chk_max(tmpL[i], tmpL[i - 1]);
	for (int i = N - 1; ~i; --i) chk_min(tmpR[i], tmpR[i + 1]);
	L.resize(H + 1), R.resize(H + 1);
	for (int h = 0, i = 0, j = 0; h <= H; ++h) {
		while (i + 1 <= N && tmpL[i + 1] <= h) ++i;
		while (j <= N && tmpR[j] < h) ++j;
		L[h] = j, R[h] = i;
		if (L[h] > R[h]) return vector<ll>(H + 1, -1);
	}
	for (int h = 0; h < H; ++h) {
		int valL = max(L[h] + 1, L[h + 1]), valR = min(R[h] + 1, R[h + 1]);
		L[h] = valL, R[h] = valR;
		if (L[h] > R[h]) return vector<ll>(H + 1, -1);
	}
	L.resize(H), R.resize(H);
	for (int l : L) ++preL[l];
	for (int r : R) ++preR[r];
	for (int i = 1; i <= N; ++i) preL[i] += preL[i - 1], preR[i] += preR[i - 1];
	sgt1.build(1, 0, N), sgt2.build(N);
	vector<int> idR, idB, tmp;
	for (int i = 1; i <= N; ++i) (!b[i] ? idR : idB).emplace_back(i);
	auto cmp = [](int x, int y) { return a[x] < a[y]; };
	sort(idR.begin(), idR.end(), cmp);
	sort(idB.begin(), idB.end(), cmp);
	ll S = 0;
	int cnt = 0, cntB = 0;
	for (int x : idR) {
		sgt1.add(1, 0, N, x, N, 1);
		if (sgt1.nd[1].df >= 0) {
			S += a[x], ++cnt;
			sgt2.upd(x, {a[x], x});
			if (cnt == H) break;
		} else {
			sgt1.add(1, 0, N, x, N, -1);
		}
	}
	for (int x : idB) {
		if (cnt == H) { tmp.emplace_back(x); continue; }
		sgt1.add(1, 0, N, x, N, 1);
		if (sgt1.nd[1].df >= 0) S += a[x], ++cnt, ++cntB;
		else sgt1.add(1, 0, N, x, N, -1), tmp.emplace_back(x);
	}
	vector<ll> ans(H + 1, -1);
	if (cnt != H) return ans;
	ans[cntB] = S;
	tmp.swap(idB);
	vector<int> df;
	for (int x : idB) {
		auto resL = sgt1.query(1, 0, N, 0, x - 1);
		auto resR = sgt1.query(1, 0, N, x, N);
		int l = 0, r = N;
		if (resL.mn == resR.mx) l = resL.mnp, r = resR.mxp;
		auto query = [&](int l, int r) {
			return l <= r ? sgt2.query(l, r) : pii{-inf, 0};
		};
		auto [c, y] = max(query(l + 1, x - 1), query(x + 1, r));
		if (y) {
			df.emplace_back(a[x] - c), sgt2.upd(y, {-inf, 0});
			sgt1.add(1, 0, N, x, N, 1), sgt1.add(1, 0, N, y, N, -1);
		}
	}
	sort(df.begin(), df.end());
	for (auto c : df) ans[cntB + 1] = ans[cntB] + c, ++cntB;
	return ans;
}

:::