题解 | #游游的整数操作#

本题好像只要用支持区间加，区间重置的线段树也能过，但是不能够在过程中取模？

大思路就是，我们给原数组排序，因为每次加减都是在所有数的上面操作，然后加法不会改变顺序，而减法可能会导致从某个位置开始往左全是0，具有二段性，我们可以二分找到这个位置，然后将左边的全部置为0，右边的正常减就行了。

由于涉及到了比大小，所以不能在中间取模，所以最后的求和数会很大，直接用了__int128。

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

typedef __int128 ll;

const int MOD = 1e9 + 7;

class LazySegmentTree {
public:
    LazySegmentTree(int _n) {
        n = _n;
        sum.assign(4 * n, 0);
        add_lazy.assign(4 * n, 0);
        reset_lazy.assign(4 * n, -1);
    }

    void add_update(int start, int end, int v) {
        _add_update(0, 0, n - 1, start, end, v);
    }

    void reset_update(int start, int end, int v) {
        _reset_update(0, 0, n - 1, start, end, v);
    }

    ll query(int start, int end) {
        return _query(0, 0, n - 1, start, end);
    }

private:
    int n;
    vector<ll> sum;
    vector<ll> add_lazy;
    vector<ll> reset_lazy;

    void doSum(int o, int l, int r, int v) {
        sum[o] += (ll)(r - l + 1) * v;
        add_lazy[o] += v;
    }

    void doReset(int o, int l, int r, int v) {
        sum[o] = (ll)(r - l + 1) * v;
        reset_lazy[o] = v;
        add_lazy[o] = 0;
    }

    void push_down(int o, int l, int r) {
        if (reset_lazy[o] != -1) {
            int left = 2 * o + 1;
            int right = 2 * o + 2;
            int m = (l + r) / 2;
            doReset(left, l, m, reset_lazy[o]);
            doReset(right, m + 1, r, reset_lazy[o]);
            reset_lazy[o] = -1;
        }
        if (add_lazy[o] != 0) {
            int left = 2 * o + 1;
            int right = 2 * o + 2;
            int m = (l + r) / 2;
            int v = add_lazy[o];
            doSum(left, l, m, v);
            doSum(right, m + 1, r, v);
            add_lazy[o] = 0;
        }
    }

    void maintain(int o) {
        int left = 2 * o + 1;
        int right = 2 * o + 2;
        sum[o] = sum[left] + sum[right];
    }

    void _add_update(int o, int l, int r, int start, int end, int v) {
        if (start <= l && r <= end) {
            doSum(o, l, r, v);
            return;
        }
        push_down(o, l, r);
        int m = (l + r) / 2;
        int left = 2 * o + 1;
        int right = 2 * o + 2;
        if (m >= start) _add_update(left, l, m, start, end, v);
        if (m < end) _add_update(right, m + 1, r, start, end, v);
        maintain(o);
    }

    void _reset_update(int o, int l, int r, int start, int end, int v) {
        if (start <= l && r <= end) {
            doReset(o, l, r, v);
            return;
        }
        push_down(o, l, r);
        int m = (l + r) / 2;
        int left = 2 * o + 1;
        int right = 2 * o + 2;
        if (m >= start) _reset_update(left, l, m, start, end, v);
        if (m < end) _reset_update(right, m + 1, r, start, end, v);
        maintain(o);
    }

    ll _query(int o, int l, int r, int start, int end) {
        if (start <= l && r <= end) {
            return sum[o];
        }
        push_down(o, l, r);
        ll res = 0;
        int m = (l + r) / 2;
        int left = 2 * o + 1;
        int right = 2 * o + 2;
        if (m >= start) res += _query(left, l, m, start, end);
        if (m < end) res += _query(right, m + 1, r, start, end);
        return res;
    }
};
ll read() {
    string s;
    cin >> s;
    ll x = 0;
    int start = 0;
    bool neg = false;
    if (s[0] == '-') {
        neg = true;
        start = 1;
    }
    for (int i = start; i < s.size(); i++) {
        x = x * 10 + (s[i] - '0');
    }
    return neg ? -x : x;
}
void print(ll x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) print(x / 10);
    putchar(x % 10 + '0');
}
int main() {
    ll n, k;
    n = read();k = read();
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    LazySegmentTree tr(n);
    for (int i = 0; i < n; ++i) {
        tr.add_update(i, i, a[i]);
    }
    for (int _ = 0; _ < k; ++_) {
        int op, x;
        cin >> op >> x;
        if (op == 1) {
            tr.add_update(0, n - 1, x);
        } else {
            int l = 0, r = n;
            while (l < r) {
                int m = (l + r) / 2;
                ll val = tr.query(m, m);
                if (val >= x) {
                    r = m;
                } else {
                    l = m + 1;
                }
            }
            if (l < n) {
                tr.add_update(l, n - 1, -x);
            }
            if (l - 1 >= 0) {
                tr.reset_update(0, l - 1, 0);
            }
        }
    }
    ll res = tr.query(0, n - 1);
    print(res % MOD);
    return 0;
}