Description

题目链接

题目大意：$m$ 次操作维护 $n$ 个栈，要求支持区间入栈，单点出栈，查询区间栈顶元素的和。$1 \le n, m \le 5 \times 10^5$。

Solution

如果没有第二种操作，可以用一个支持区间覆盖，区间求和的线段树完成。

如果我们把每次操作都看成一个版本，第二种操作其实是给定 $x$，找到当前 $x$ 的位置上最后是哪个版本赋值给它的，再退回到这个版本的上一个版本。

只需要写一个支持区间赋值，求区间和的可持久化线段树即可。

由于是区间赋值，需要用到懒标记，这里只能用标记永久化的方法，每次下放的时候都要新建节点。

Code

#include <bits/stdc++.h>

template <class T>
inline void read(T &x) {
    x = 0;
    int f = 0;
    char ch = getchar();
    while (!isdigit(ch))    { f |= ch == '-'; ch = getchar(); }
    while (isdigit(ch))     { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    x = f ? -x : x;
    return ;
}

typedef unsigned long long uLL;
typedef long long LL;

constexpr int maxn = 5e5 + 10;

struct Node {
    int ls, rs, v, tag;
} t[maxn << 5];

int rt[maxn], a[maxn];
int n, m, ty, ans, tot;

void modify(int &x, int lst, int L, int R, int l, int r, int id) {
    x = ++tot;
    if (l <= L && R <= r) {
        t[x].tag = id;
        t[x].v = (R - L + 1) * a[id];
        return ;
    }
    int mid = (L + R) >> 1;
    if (t[lst].tag) {
        t[++tot] = t[t[lst].ls], t[lst].ls = tot, t[++tot] = t[t[lst].rs], t[lst].rs = tot;
        t[t[lst].ls].tag = t[t[lst].rs].tag = t[lst].tag;
        t[t[lst].ls].v = (mid - L + 1) * a[t[lst].tag], t[t[lst].rs].v = (R - mid) * a[t[lst].tag];
        t[lst].tag = 0;
    }
    t[x] = t[lst];
    if (l <= mid)    modify(t[x].ls, t[lst].ls, L, mid, l, r, id);
    if (r > mid)    modify(t[x].rs, t[lst].rs, mid + 1, R, l, r, id);
    t[x].v = t[t[x].ls].v + t[t[x].rs].v;
    return ;
}

int ask(int x, int L, int R, int p) {
    if (L == R || t[x].tag)    return t[x].tag;
    int mid = (L + R) >> 1;
    if (p <= mid)    return ask(t[x].ls, L, mid, p);
    else    return ask(t[x].rs, mid + 1, R, p);
}

int query(int x, int L, int R, int l, int r) {
    if (l == L && R == r)    return t[x].v;
    if (t[x].tag)    return (r - l + 1) * a[t[x].tag];
    int mid = (L + R) >> 1;
    if (r <= mid)    return query(t[x].ls, L, mid, l, r);
    else if (l > mid)    return query(t[x].rs, mid + 1, R, l, r);
    else    return query(t[x].ls, L, mid, l, mid) + query(t[x].rs, mid + 1, R, mid + 1, r);
}

int main() {
    read(n), read(m), read(ty);
    for (int i = 1, op, l, r, x; i <= m; ++i) {
        rt[i] = rt[i - 1];
        read(op);
        if (op == 1) {
            read(l), read(r);
            l = (l + ans * ty) % n + 1;
            r = (r + ans * ty) % n + 1;
            if (l > r)    std::swap(l, r);
            ans = query(rt[i], 1, n, l, r);
            printf("%d\n", ans);
        } else if (op == 2) {
            read(l);
            l = (l + ans * ty) % n + 1;
            x = ask(rt[i - 1], 1, n, l);
            if (!x)    continue;
            x = ask(rt[x - 1], 1, n, l);
            modify(rt[i], rt[i], 1, n, l, l, x);
        } else {
            read(l), read(r), read(x);
            l = (l + ans * ty) % n + 1;
            r = (r + ans * ty) % n + 1;
            if (l > r)    std::swap(l, r);
            a[i] = x;
            modify(rt[i], rt[i], 1, n, l, r, i);
        }
    }
    return 0;
}