自动搬运

查看原文

来自洛谷，原作者为

	TernaryTree ?steal a life

搬运于2025-08-24 22:59:00，当前版本为作者最后更新于2024-05-30 21:06:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

献给我死去的 APIO2024。

显然要 $dp$，也就是 $f_i$ 表示经过边 $i$，到达点 $Y_i$ 的最少代价。方便起见，我们多加两个起点到起点（$0$ 时刻到 $0$ 时刻，代价为 $0$），终点到终点（$\infin$ 时刻到 $\infin$ 时刻，代价为 $0$）的边，编号为 $0$ 和 $m+1$。于是我们要求的就是 $f_{m+1}$。有转移方程：

$$f_i=C_i+\min_{X_i=Y_j,B_j\le A_i}f_j+T_{X_i}\cdot w(B_j+1,A_i-1) $$

其中 $cost(l,r)$ 表示被 $[l,r]$ 完全包含的 $[L[i],R[i]]$ 个数。

我们维护两个边集 $e$ 和 $ej$，一个是所有我们要计算 $f_i$ 的 $i$，一个是当前可以被转移的 $j$。显然地，$e$ 按照 $A_i$ 排序，$ej$ 按照 $B_j$ 排序，这样每次我们的决策点与被决策点都是一段前缀，使用双指针很好处理，也方便理解决策单调性。

通过上面的方程可以推出转移具有决策单调性。具体地，若 $i_1\lt i_2$，$e_{i_1}$ 的最优决策点为 $p_1$（即，从 $ej_{p_1}$ 转移过来），$e_{i_2}$ 的最优决策点为 $p_2$，则 $p_1\le p_2$。

处理决策单调性 dp 的方法是二分队列。很不幸我 APIO 之前并不会这个 trick。其过程如下：

维护结构体队列，结构体形如 $(j,l,r)$，表示 $j$ 决策点可以决策 $[l,r]$ 这段区间。

• 对于加入决策点 $j$：

  在队尾进行操作。如果一个队尾 $(j',l',r')$ 中，决策 $j'$ 在 $l'$ 时的价值劣于新加入的决策点 $j$ 在 $l$ 时的价值，则弹出队尾，反复进行直到不满足为止。此时仍需要对队尾 $(j',l',r')$ 进行划分，考虑类似地二分出决策点 $j$ 可以“占领”哪些部分，将其从队尾中分裂出去即可。

• 对于计算 $i$ 的答案：

  在队头进行操作。若队头 $(j,l,r)$ 中 $r<i$ 说明队头过时，弹出。反复进行操作，最后得到的队头中的 $j$ 即为最优决策点。同时把队头中的 $l$ 缩减到 $i$ 即可。

但是由于方程中还有一个 $Y_i=X_j$ 的限制，所以要对每个结点都维护一个上述队列。同时，$(j,l,r)$ 的含义也有改动：表示当前所在队列对应结点 $u$ 可以转移到的 $i$ 是第 $l$ 个到第 $r$ 个（起点与当前结点相同的），必要时再套一个二分即可。至于 $cost(l,r)$ 的计算，可以离散化所有时间戳后使用主席树维护。于是总复杂度为 $\Theta(n\log ^2n)$。

shitcode:

struct edge {
	int u, v, p, q, w, id;
};

struct op {
	int j, l, r;
};

struct QwQ {
	vector<op> q;
	int hd = 0, tl = -1;
	void push_back(op x) { q.push_back(x), ++tl; }
	void pop_back() { q.pop_back(), --tl; }
	bool empty() { return hd > tl; }
	op& front() { return q[hd]; }
	op& back() { return q[tl]; }
	void pop_front() { hd++; }
};

struct node {
	int ch[2] = {};
	int sum = 0;
};

node tr[maxn * 22];
int rt[maxn], tot;

void modify(int &u, int pre, int l, int r, int p, int k) {
	tr[u = ++tot] = tr[pre];
	if (l == r) {
		tr[u].sum += k;
		return;
	}
	if (p <= mid) modify(ls, tr[pre].ch[0], l, mid, p, k);
	else modify(rs, tr[pre].ch[1], mid + 1, r, p, k);
	tr[u].sum = tr[ls].sum + tr[rs].sum;
}

int query(int u, int l, int r, int ql, int qr) {
	if (ql <= l && r <= qr) return tr[u].sum;
	int ans = 0;
	if (ql <= mid) ans += query(lc, ql, qr);
	if (qr > mid) ans += query(rc, ql, qr);
	tr[u].sum = tr[ls].sum + tr[rs].sum;
	return ans;
}

ll solve(int n, int m, int w, vi t, vi x, vi y, vi a, vi b, vi c, vi l, vi r) {
	vector<edge> e (m + 2), ej (m + 2); vector<ll> f (m + 2);
	vector<QwQ> que(n); vector<int> buc;
	vector<pii> rg;
	e[0] = {0, 0, 0, 0, 0, 0};
	f[0] = 0;
	rep(i, 0, m - 1) e[i + 1] = {x[i], y[i], a[i], b[i], c[i], i + 1};
	e[m + 1] = {n - 1, n - 1, (int) 1e9 + 1, (int) 1e9 + 2, 0, m + 1};
	rep(i, 0, m + 1) b.push_back(e[i].p), b.push_back(e[i].q);
	rep(i, 0, w - 1) b.push_back(l[i]), b.push_back(r[i]);
	sort(b.begin(), b.end());
	b.resize(unique(b.begin(), b.end()) - b.begin());
	rep(i, 0, m + 1) {
		e[i].p = lower_bound(b.begin(), b.end(), e[i].p) - b.begin() + 1;
		e[i].q = lower_bound(b.begin(), b.end(), e[i].q) - b.begin() + 1;
	}
	rep(i, 0, w - 1) {
		l[i] = lower_bound(b.begin(), b.end(), l[i]) - b.begin() + 1;
		r[i] = lower_bound(b.begin(), b.end(), r[i]) - b.begin() + 1;
		rg.push_back({r[i], l[i]});
	}
	sort(rg.begin(), rg.end());
	rep(i, 0, w - 1) modify(rt[i + 1], rt[i], 0, b.size() + 5, rg[i].sc, 1);
	rep(i, 1, m + 1) f[i] = inf;
	ej = e;
	sort(e.begin(), e.end(), [] (edge x, edge y) {
		return x.p < y.p;
	});
	sort(ej.begin(), ej.end(), [] (edge x, edge y) {
		return x.q < y.q;
	});
	vector<vector<int>> qaq (n);
	rep(i, 0, m + 1) qaq[e[i].u].push_back(i);
	auto val = [&] (int i, int j) -> ll {
		ll ans = f[ej[j].id] + e[i].w;
		int l = ej[j].q + 1, r = e[i].p - 1;
		ll cnt = 0; pii tmp = {r, 1e9};
		auto id = upper_bound(rg.begin(), rg.end(), tmp) - rg.begin();
		cnt = query(rt[id], 0, b.size() + 5, l, b.size() + 5);
		return min(ans + cnt * t[e[i].u], inf);
	};
	int mxj = 0;
	rep(i, 1, m + 1) {
		while (mxj <= (int) ej.size() - 1 && ej[mxj].q <= e[i].p) {
			int x = ej[mxj].v;
			while (!que[x].empty() && val(qaq[x][que[x].back().l], mxj) <= val(qaq[x][que[x].back().l], que[x].back().j)) que[x].pop_back();
			if (que[x].empty()) {
				int pos = lower_bound(qaq[x].begin(), qaq[x].end(), i) - qaq[x].begin();
				if (pos < qaq[x].size()) que[x].push_back({mxj, pos, (int) qaq[x].size() - 1});
				++mxj;
				continue;
			}
			int l = que[x].back().l, r = que[x].back().r + 1;
			while (l < r) {
				if (val(qaq[x][mid], mxj) <= val(qaq[x][mid], que[x].back().j)) r = mid;
				else l = mid + 1;
			}
			que[x].back().r = l - 1;
			if (l < qaq[x].size()) que[x].push_back({mxj, l, (int) qaq[x].size() - 1});
			++mxj;
		}
		int x = e[i].u;
		while (!que[x].empty() && qaq[x][que[x].front().r] < i) que[x].pop_front();
		int g = -1;
		if (!que[x].empty()) {
			int j = que[x].front().j;
			f[e[i].id] = min(f[e[i].id], val(i, j));
			g = j;
			que[x].front().l = lower_bound(qaq[x].begin(), qaq[x].end(), i) - qaq[x].begin();
		}
	}
	return f[m + 1] == inf ? -1 : f[m + 1];
}