P11833 [省选联考 2025] 推箱子

竟然和 ABC 的题重了。。。

先考虑贪心做这个问题。很容易想到，按照

t

排序，依次满足要求。每个箱子直接从当前位置推向

b_i

，并把过程中遇到的箱子“挤压”着移动。由于

a,b

均递增，这样做并不会妨害到后续箱子的移动，并能最小化当前时间。

那么看起来只需要写一个：区间推平成等差数列，区间求和。由于挤压的存在，实现起来有一定细节。

考虑维护

c_i=a_i-i

，显然

c_i\leq c_{i+1}

。可以发现，这时操作就转成了区间推平，查询区间和。例如对箱子

i

操作，从

x

位置走向

y

位置，只需把

j\geq i\land c_j\in [x, y]

的值推平成

y

即可（

x>y

同理）。步数显然仍是移动前后对应位置

c_i

之差的绝对值。

若用线段树维护，维护区间和与覆盖标记，同时为了在线段树上二分找到推平区间，需要维护区间最值。时间复杂度

\mathcal O(n\log n)

。

不过我们注意到，查询区间与覆盖区间总是相同，因此用 ODT 维护即可，时间复杂度也是

\mathcal O(n\log n)

。

~~代码后续补。~~

这里有一份能通过官方数据的 ODT 实现：

CPP

int testcase, n; ll ans;

struct node {
	int a, b, id; ll t;
	
	il bool operator < (const node &p) const {
		return t < p.t;
	}
	
	il void input(int i) {
		read(a, b, t);
		a -= i; b -= i; id = i;
	}
} a[MAXN];

struct ODT {
	struct node {
		int l, r;
		mutable int v;
		
		il bool operator < (const node &p) const {
			return l < p.l;
		}
	}; set <node> odt;
	
	il void init() {
		odt.clear(); 
		rep1(i, 1, n) odt.emplace(node{i, i, a[i].a});
	}
	
	il void change(int i) {
		int id = a[i].id;
		auto it = --odt.upper_bound(node{id, -1, -1});
		auto [l0, r0, v0] = *it;
		if (a[i].a < a[i].b) {
			if (l0 ^ id) {
				odt.erase(it); odt.emplace(node{l0, id - 1, v0});
				it = odt.emplace(node{id, r0, v0}).fst;
			} auto itr = it; ll sum = 0; int rpos = id - 1;
			while (itr != end(odt) && itr -> v < a[i].b) {
				auto [l, r, v] = *itr++;
				sum += ll(r - l + 1) * v; rpos = r;
			} odt.erase(it, itr); odt.emplace(node{id, rpos, a[i].b});
			ans += ll(rpos - id + 1) * a[i].b - sum;
		} else {
			if (r0 ^ id) {
				odt.erase(it); odt.emplace(node{id + 1, r0, v0});
				it = odt.emplace(node{l0, id, v0}).fst;
			} auto itl = it; ll sum = 0; int lpos = id + 1;
			while (itl -> v > a[i].b) {
				auto [l, r, v] = *itl;
				sum += ll(r - l + 1) * v; lpos = l;
				if (itl == begin(odt)) break;
				--itl;
			} odt.erase(--odt.upper_bound(node{lpos, -1, -1}), next(it));
			odt.emplace(node{lpos, id, a[i].b});
			ans += sum - ll(id - lpos + 1) * a[i].b;
		}
	}
} T;

il void solve() {
	read(n); ans = 0;
	rep1(i, 1, n) a[i].input(i);
	T.init(); sort(a + 1, a + 1 + n);
	rep1(i, 1, n) if ((T.change(i), ans) > a[i].t) return puts("No"), void();
	puts("Yes");
}

int main() {
	read(testcase);
	for (int T = read(); T--; ) solve();
	return 0;
}

下面是我的赛时代码，线段树写法。

CPP

int testcase, n;

struct node {
	int a, b, id; ll t;
	
	il bool operator < (const node &p) const {
		return t < p.t;
	}
	
	il void input(int i) {
		read(a, b, t); id = i;
		a -= i, b -= i;
	}
} a[MAXN];

struct setr {
	#define STZ MAXN << 2
	#define ls(x) x << 1
	#define rs(x) x << 1 | 1
	ll sum[STZ]; int maa[STZ], mii[STZ], tg[STZ];
	
	il void pushup(int x) {
		sum[x] = sum[ls(x)] + sum[rs(x)];
		maa[x] = max(maa[ls(x)], maa[rs(x)]);
		mii[x] = min(mii[ls(x)], mii[rs(x)]);
	}
	
	il void change(int x, int k, ll len) {
		tg[x] = maa[x] = mii[x] = k;
		sum[x] = k * len;
	}
	
	il void pushdown(int x, int l, int r) {
		if (!~tg[x]) return;
		int mid = l + r >> 1;
		change(ls(x), tg[x], mid - l + 1);
		change(rs(x), tg[x], r - mid);
		tg[x] = -1;
	}
	
	il void upd(int x, int l, int r, int ql, int qr, int k) {
		if (l > qr || r < ql) return;
		if (l >= ql && r <= qr) return change(x, k, r - l + 1);
		int mid = l + r >> 1; pushdown(x, l, r);
		upd(ls(x), l, mid, ql, qr, k); upd(rs(x), mid + 1, r, ql, qr, k);
		pushup(x);
	}
	
	il ll query(int x, int l, int r, int ql, int qr) {
		if (l > qr || r < ql) return 0;
		if (l >= ql && r <= qr) return sum[x];
		int mid = l + r >> 1; pushdown(x, l, r);
		return query(ls(x), l, mid, ql, qr) + query(rs(x), mid + 1, r, ql, qr);
	}
	
	il void build(int x, int l, int r) {
		tg[x] = -1;
		if (l == r) return sum[x] = maa[x] = mii[x] = a[l].a, void();
		int mid = l + r >> 1;
		build(ls(x), l, mid); build(rs(x), mid + 1, r);
		pushup(x);
	}
	
	il int query1(int x, int l, int r, int k) {
		if (l == r) return l;
		int mid = l + r >> 1; pushdown(x, l, r);
		if (mii[rs(x)] <= k) return query1(rs(x), mid + 1, r, k);
		return query1(ls(x), l, mid, k);
	}
	
	il int query2(int x, int l, int r, int k) {
		if (l == r) return l;
		int mid = l + r >> 1; pushdown(x, l, r);
		if (maa[ls(x)] >= k) return query2(ls(x), l, mid, k);
		return query2(rs(x), mid + 1, r, k);
	}
} T;

il void solve() {
	read(n);
	rep1(i, 1, n) a[i].input(i);
	T.build(1, 1, n);
	sort(a + 1, a + 1 + n);
	bll now = 0;
	rep1(i, 1, n) {
		int id = a[i].id;
		if (a[i].a < a[i].b) {
			int pos = T.query1(1, 1, n, a[i].b);
			if ((now += a[i].b * ll(pos - id + 1) - T.query(1, 1, n, id, pos)) > a[i].t) return puts("No"), void();
			T.upd(1, 1, n, id, pos, a[i].b);
		} else {
			int pos = T.query2(1, 1, n, a[i].b);
			if ((now += T.query(1, 1, n, pos, id) - a[i].b * ll(id - pos + 1)) > a[i].t) return puts("No"), void();
			T.upd(1, 1, n, pos, id, a[i].b);
		}
	} puts("Yes");
}

int main() {
	read(testcase);
	for (int Q = read(); Q--; ) solve();
	return 0;
}
/*
维护 a_i - i
abc 原题 
*/

P11833 [省选联考 2025] 推箱子

文章操作

相关推荐

评论

P11833 [省选联考 2025] 推箱子