27pts求调,玄关
查看原帖
27pts求调,玄关
700558
williamwei楼主2024/10/23 14:57
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
#define lson (k << 1)
#define rson (k << 1 | 1)
const int maxn = 2e5 + 10;
const int N = 2e5;
const ll inf = 1e14;
int n, q;
ll A[maxn], c[maxn << 2];
void build(int k, int l, int r) {
    c[k] = inf; if (l == r) return;
    int mid = (l + r) >> 1;
    build(lson, l, mid); build(rson, mid + 1, r);
}
void update(int k, int l, int r, int p, ll v) {
    if (l == r) {c[k] = v; return;}
    int mid = (l + r) >> 1;
    if (p <= mid) update(lson, l, mid, p, v);
    else update(rson, mid + 1, r, p, v);
    c[k] = min(c[lson], c[rson]);
}
ll query(int k, int l, int r, int L, int R) {
    if (L <= l && r <= R) return c[k];
    int mid = (l + r) >> 1; ll res = inf;
    if (L <= mid) res = min(res, query(lson, l, mid, L, R));
    if (R > mid) res = min(res, query(rson, mid + 1, r, L, R));
    return res;
}
int nxt(int p, ll v) {
    int l = p + 1, r = n, res = n + 1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (query(1, 1, N, 1, mid) <= v) res = mid, r = mid - 1;
        else l = mid + 1;
    } return res;
}
int main() {
    ios::sync_with_stdio(false);
    cin >> q; build(1, 1, N);
    while (q--) {
        int op; bool v; ll x; cin >> op >> x;
        if (op == 1) cin >> v, update(1, 1, N, ++n, !v ? x : 0), A[n] = x;
        else if (op == 2) update(1, 1, N, x, inf);
        else {
            vector<pair<int, int> > res;
            for (int cur = nxt(0, x); cur <= n && x > 0; cur = nxt(cur, x)) {
                res.emplace_back(cur, min(x, A[cur])); 
                int val = A[cur]; A[cur] -= x; x -= val;
                update(1, 1, N, cur, A[cur] <= 0 ? inf : A[cur]);
            } cout << res.size() << '\n';
            for (auto [a, b] : res) cout << a << ' ' << b << '\n';
        }
    }
    return 0;
}
2024/10/23 14:57
加载中...