专栏文章

题解：P10711 [NOISG 2024 Prelim] Amusement Park

zzhujianheng
P10711题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min5pbzs
此快照首次捕获于
2025/12/01 20:59
3 个月前
此快照最后确认于
2025/12/01 20:59
3 个月前
查看原文
该题放在 NOIP 模拟赛 T1。
显然的，发现我们最多也就是 qq 量级的输出，于是考虑线段树。
线段树里维护两个变量。是否存在 11，以及最小值。最后要求的就是在尽量靠近自己的小于当前可乘坐人数或者是 11 的编号，然后如果那个团队的人数大于可乘坐人数就将可乘坐人数变成 00，并将该团队人数减掉剩下人数，并且停止。否则就将这个团队一起带走，然后继续找 (x,n](x,n]（xx 为当前编号）里的团队，如果找不到了（代码里标记为 −1-1），就退出程序，输出也很简单。
对于增加，就相当于增加 nn 并且在新的 nn 的位置上增加，对于删去，就将其人数变成无穷大（因为要最小值），然后将其愿不愿意改成不愿意（00）即可。
时间复杂度 O(qlog⁡q)O(q \log q)，可以通过该题。
CPP
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 500009;
const int INF = 1e18;

struct Segment {
	int l;
	int r;
	bool ok;
	int mn;
} tr[N * 4];
int s[N], f[N], g[N], t[N], n, q;

void build(int u, int l, int r) {
	if (l == r) {
		tr[u] = (Segment) {
			l, r, 0, INF
		};
		return;
	}
	int mid = (l + r) / 2;
	build(u * 2, l, mid);
	build(u * 2 + 1, mid + 1, r);
	tr[u] = (Segment) {
		l, r, tr[u * 2].ok || tr[u * 2 + 1].ok, min(tr[u * 2].mn, tr[u * 2 + 1].mn)
	};
}

void update(int u, int x, int delta, bool v) {
	if (tr[u].l == tr[u].r) {
		tr[u].mn = delta;
		tr[u].ok = v;
		return;
	}
	if (x <= tr[u * 2].r)
		update(u * 2, x, delta, v);
	else
		update(u * 2 + 1, x, delta, v);
	tr[u].ok = tr[u * 2].ok || tr[u * 2 + 1].ok;
	tr[u].mn = min(tr[u * 2].mn, tr[u * 2 + 1].mn);
}

int query(int u, int x) {
	if (tr[u].mn > x && !tr[u].ok)
		return -1;
	if (tr[u].l == tr[u].r)
		return tr[u].l;
	if (x >= tr[u * 2].mn || tr[u * 2].ok)
		return query(u * 2, x);
	else
		return query(u * 2 + 1, x);
}

signed main() {
	//freopen("bus.in", "r", stdin);
	//freopen("bus.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> q;
	build(1, 1, q);
	for (int i = 1; i <= q; i++) {
		int op, x;
		cin >> op >> x;
		if (op == 1) {
			bool y;
			cin >> y;
			s[++n] = x;
			t[n] = y;
			update(1, n, s[n], y);
		} else if (op == 2)
			update(1, x, INF, 0), s[x] = 0;
		else {
			int m = 0, c = query(1, x);
			while (c != -1 && x) {
				int p = min(s[c], x);
				f[++m] = c;
				g[m] = p;
				if (x < s[c]) {
					s[c] -= x;
					x = 0;
					update(1, c, s[c], t[c]);
				} else {
					x -= s[c];
					s[c] = 0;
					update(1, c, INF, 0);
				}
				c = query(1, x);
			}
			cout << m << endl;
			for (int j = 1; j <= m; j++)
				cout << f[j] << " " << g[j] << endl;
		}
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...