A2481 全村最好的嘤嘤刀【无数据】

#include <bits/stdc++.h>
using namespace std;

struct SegTree {
    int n;
    vector<long long> mx, tag;
    explicit SegTree(int n) : n(n), mx(4 * n + 4, 0), tag(4 * n + 4, 0) {}
    void build(int p, int l, int r, const vector<long long> &a) {
        if (l == r) { mx[p] = a[l]; return; }
        int m = (l + r) / 2;
        build(p * 2, l, m, a);
        build(p * 2 + 1, m + 1, r, a);
        pull(p);
    }
    void pull(int p) { mx[p] = max(mx[p * 2], mx[p * 2 + 1]); }
    void apply(int p, long long v) { mx[p] += v; tag[p] += v; }
    void push(int p, int l, int r) {
        if (tag[p] == 0 || l == r) return;
        int m = (l + r) / 2;
        apply(p * 2, tag[p]);
        apply(p * 2 + 1, tag[p]);
        tag[p] = 0;
    }
    void add(int p, int l, int r, int ql, int qr, long long v) {
        if (ql <= l && r <= qr) { apply(p, v); return; }
        push(p, l, r);
        int m = (l + r) / 2;
        if (ql <= m) add(p * 2, l, m, ql, qr, v);
        if (qr > m) add(p * 2 + 1, m + 1, r, ql, qr, v);
        pull(p);
    }
    long long queryMax(int p, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return mx[p];
        push(p, l, r);
        int m = (l + r) / 2;
        long long res = LLONG_MIN;
        if (ql <= m) res = max(res, queryMax(p * 2, l, m, ql, qr));
        if (qr > m) res = max(res, queryMax(p * 2 + 1, m + 1, r, ql, qr));
        return res;
    }
    long long queryPoint(int p, int l, int r, int pos) {
        if (l == r) return mx[p];
        push(p, l, r);
        int m = (l + r) / 2;
        return pos <= m ? queryPoint(p * 2, l, m, pos) : queryPoint(p * 2 + 1, m + 1, r, pos);
    }
    void setPoint(int p, int l, int r, int pos, long long v) {
        if (l == r) { mx[p] = v; tag[p] = 0; return; }
        push(p, l, r);
        int m = (l + r) / 2;
        if (pos <= m) setPoint(p * 2, l, m, pos, v);
        else setPoint(p * 2 + 1, m + 1, r, pos, v);
        pull(p);
    }
    // 在 [ql,qr] 中找最靠右的、值等于 val 的位置
    int findRightmost(int p, int l, int r, int ql, int qr, long long val) {
        if (r < ql || l > qr || mx[p] < val) return -1;
        if (l == r) return l;
        push(p, l, r);
        int m = (l + r) / 2;
        int t = findRightmost(p * 2 + 1, m + 1, r, ql, qr, val);
        if (t != -1) return t;
        return findRightmost(p * 2, l, m, ql, qr, val);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    SegTree seg(n);
    seg.build(1, 1, n, a);

    set<int> demon;         // 当前有绯狱丸的位置
    long long total = 0;    // 嘤嘤刀积累的能量

    for (int i = 0; i < m; i++) {
        int op;
        cin >> op;
        if (op == 1) {
            int x;
            long long val;
            cin >> x >> val;
            // 绯狱丸吞噬该点能量：该点能量变成 val - 原能量
            long long cur = seg.queryPoint(1, 1, n, x);
            seg.setPoint(1, 1, n, x, val - cur);
            demon.insert(x);
        } else if (op == 2) {
            int l, r;
            cin >> l >> r;
            long long gain;
            int pos = -1;
            auto it = demon.lower_bound(l);
            if (it != demon.end() && *it <= r) {
                // 区间里有绯狱丸：优先用嘤嘤刀对付它
                pos = *it;
                demon.erase(it);
                gain = seg.queryPoint(1, 1, n, pos);
            } else {
                // 否则取区间最大值（出现多个最大值时取靠右的）
                gain = seg.queryMax(1, 1, n, l, r);
                pos = seg.findRightmost(1, 1, n, l, r, gain);
            }
            // 取走能量后该点清零
            seg.setPoint(1, 1, n, pos, 0);
            total += gain;
            cout << gain << '\n';
        } else {
            int l, r;
            long long val;
            cin >> l >> r >> val;
            seg.add(1, 1, n, l, r, val);
        }
    }

    if (total < 10000) cout << "QAQ\n";
    else if (total < 10000000) cout << "Sakura\n";
    else cout << "ice\n";
    return 0;
}