C++(clang++ 11.0.1) 解法, 执行用时: 810ms, 内存消耗: 148332K, 提交时间: 2022-09-08 09:57:02

#include <bits/stdc++.h>
#define F(x, y, z) for (int x = (y); x <= (z); ++x)
#define DF(x, y, z) for (int x = (y); x >= (z); --x)
using namespace std;
typedef long long ll;
int read() {
    char ch = getchar();
    int x = 0, pd = 0;
    while (ch < '0' || ch > '9') pd |= ch == '-', ch = getchar();
    while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ 48), ch = getchar();
    return pd ? -x : x;
}
const int maxn = 300005;
int n, m;
struct Op {
    int opt, x;
} q[maxn];
int s[maxn], t[maxn][2], mn[maxn][19];
int qmn(int l, int r) {
    int g = __lg(r - l + 1);
    return min(mn[l][g], mn[r - (1 << g) + 1][g]);
}
int tot, rt[maxn], ls[maxn << 5], rs[maxn << 5], c[maxn << 5]; ll sum[maxn << 5];
void pp(int o) { c[o] = c[ls[o]] + c[rs[o]], sum[o] = sum[ls[o]] + sum[rs[o]]; }
void upd(int &o, int l, int r, int x) {
    ++tot, ls[tot] = ls[o], rs[tot] = rs[o], o = tot;
    if (l == r) { c[tot] = 1, sum[o] = q[l].x; return; }
    int mid = (l + r) >> 1;
    if (x <= mid) upd(ls[o], l, mid, x);
    else upd(rs[o], mid + 1, r, x);
    pp(o);
}
int suf, R;
ll qry(int o, int l, int r) {
    if (c[o] <= suf && r <= R) {
        suf -= c[o];
        return sum[o];
    }
    int mid = (l + r) >> 1;
    if (R <= mid) return qry(ls[o], l, mid);
    ll ret = qry(rs[o], mid + 1, r);
    if (suf) ret += qry(ls[o], l, mid);
    return ret;
}
int stk[maxn][3], top[3], len;
struct P {
    int x, y;
} p[maxn];
int py[maxn];
void pre() {
    DF(i, n, 1) {
        if (q[i].opt < 3) {
            if (!top[q[i].opt]) p[++len] = {i, n + 1};
            else p[++len] = {i, stk[top[q[i].opt]][q[i].opt]}, --top[q[i].opt];
        } else stk[++top[q[i].opt - 2]][q[i].opt - 2] = i;
    }
    sort(p + 1, p + len + 1, [](P A, P B) {
        return A.y < B.y;
    });
    DF(i, len, 1) {
        rt[i] = rt[i + 1];
        upd(rt[i], 1, n, p[i].x);
        py[i] = p[i].y;
    }
}
int main() {
    n = read(), m = read();
    F(i, 1, n) {
        s[i] = s[i - 1], q[i].opt = read();
        t[i][0] = t[i - 1][0], t[i][1] = t[i - 1][1];
        if (q[i].opt < 3) q[i].x = read(), ++s[i], ++t[i][0];
        else --s[i], ++t[i][1];
        mn[i][0] = s[i];
    }
    F(j, 1, __lg(n))
        for (int i = 1; i + (1 << j) - 1 <= n; ++i)
            mn[i][j] = min(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);
    pre();
    while (m--) {
        int l = read(), r = read();
        if (qmn(l, r) < s[l - 1]) {
            puts("wlwzgkd");
            continue;
        }
        int k1 = t[r][0] - t[l - 1][0], k2 = t[r][1] - t[l - 1][1], pos = upper_bound(py + 1, py + len + 1, r) - py;
        suf = k1 - k2, R = r;
        printf("%lld\n", qry(rt[pos], 1, n));
    }
    return 0;
}