题解：P10711 [NOISG 2024 Prelim] Amusement Park

· · 题解

该题放在 NOIP 模拟赛 T1。

显然的，发现我们最多也就是 q 量级的输出，于是考虑线段树。

线段树里维护两个变量。是否存在 1，以及最小值。最后要求的就是在尽量靠近自己的小于当前可乘坐人数或者是 1 的编号，然后如果那个团队的人数大于可乘坐人数就将可乘坐人数变成 0，并将该团队人数减掉剩下人数，并且停止。否则就将这个团队一起带走，然后继续找 (x,n]（x 为当前编号）里的团队，如果找不到了（代码里标记为 -1），就退出程序，输出也很简单。

对于增加，就相当于增加 n 并且在新的 n 的位置上增加，对于删去，就将其人数变成无穷大（因为要最小值），然后将其愿不愿意改成不愿意（0）即可。

时间复杂度 O(q \log q)，可以通过该题。

#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;
}