倍增分块板子。

· · 题解

独立调出来的倍增分块！

这题码量比倍增分块做堕天作战要短。

倍增分块维护 \log 个块，第 i 个块存 [\text{base}^i,\text{base}^{i+1}) 之间的所有元素。

实际上就是维护 \log 棵线段树的信息。

那么需要实现的操作除了朴素线段树，以下几点不太一样。

为了卡空间，这里用了底层分块。

就是，对于长度 \le L（这里的 L 是一个常数）的线段树区间，直接暴力修改。

重构就是对于某个块 id，把一段长度 \le L 的区间 [l,r] 的信息全部删除。

然后再重新加入所有元素。

这里维护的信息除了区间和、最小值、最大值、懒标记，还维护了当前节点 rt 的左儿子和右儿子（动态开点缩小空间）。

对于第 id 个块（也就是第 id 棵线段树）的节点 rt，维护一个 len 表示节点 rt 管辖的区间内，属于 id 这个块的元素个数，这样可以方便区间减。

插入操作 \text{ins} 表示一个元素从某个块下坠到下面的一个块。

实现细节上，就是从某个块删去这个元素，然后重构。

接着进行下坠，在新的块内加入元素，更新贡献。

差不多就是这样，代码很好懂。

这里的 \text{base} 取了 16。

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

template <typename T> inline void read(T &x) {
    x = 0; char ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
}

template <typename T, typename ...Args>
inline void read(T &x, Args &...args) { read(x), read(args...); }

const int N = 5e5 + 10, bas = 16; const ll inf = 1e9;
int n, m, V, cnt, Maxb, pw[40], rot[40], a[N], bel[N];
struct Node { int ls, rs, len, tag, Min, Max; ll val; } t[N << 4];

#define ls t[rt].ls
#define rs t[rt].rs
#define getid(x) ((int)(log(x) / log(bas)))

inline void pushup(int rt) {
    t[rt].Min = min(t[ls].Min, t[rs].Min);
    t[rt].Max = max(t[ls].Max, t[rs].Max);
    t[rt].len = t[ls].len + t[rs].len;
    t[rt].val = t[ls].val + t[rs].val; return ;
}

inline void rebuild(int id, int rt, int l, int r) { // 重构操作
    t[rt].Min = inf, t[rt].Max = -inf, t[rt].len = t[rt].val = 0;
    for (int i = l; i <= r; ++i) {
        if (bel[i] != id) continue;
        t[rt].Min = min(t[rt].Min, a[i]);
        t[rt].Max = max(t[rt].Max, a[i]);
        t[rt].val += a[i], ++t[rt].len;
    }
    return ;
}

inline void addtag(int rt, int val) {
    if (!t[rt].len) return ;
    t[rt].tag += val, t[rt].val += (ll)t[rt].len * val;
    t[rt].Min += val, t[rt].Max += val; return ;
}

inline void pushdown(int id, int rt, int l, int r) {
    if (!t[rt].tag) return ;
    if (r - l >= bas) addtag(ls, t[rt].tag), addtag(rs, t[rt].tag);
    else for (int i = l; i <= r; ++i) if (bel[i] == id) a[i] += t[rt].tag;
    return t[rt].tag = 0, void();
}

inline void build(int id, int &rt, int l, int r) {
    rt = ++cnt; if (r - l < bas) return rebuild(id, rt, l, r);
    int mid = (l + r) >> 1;
    build(id, ls, l, mid), build(id, rs, mid + 1, r);
    return pushup(rt);
}

inline void ins(int id, int rt, int l, int r, int pos, int val) { // 插入操作
    if (r - l < bas) {
        pushdown(id, rt, l, r), bel[pos] = id;
        t[rt].Min = min(t[rt].Min, val);
        t[rt].Max = max(t[rt].Max, val);
        return t[rt].val += val, ++t[rt].len, void();
    }
    int mid = (l + r) >> 1; pushdown(id, rt, l, r);
    if (pos <= mid) ins(id, ls, l, mid, pos, val);
    else ins(id, rs, mid + 1, r, pos, val);
    return pushup(rt);
}

inline void upd(int id, int rt, int l, int r, int L, int R, int val) { // 元素迁移块
    if (t[rt].Max <= val || !t[rt].len) return ;
    else if (L <= l && r <= R && t[rt].Min - val >= pw[id]) return addtag(rt, -val);
    else if (r - l < bas) {
        pushdown(id, rt, l, r), L = max(L, l), R = min(R, r);
        for (int i = L; i <= R; ++i) {
            if (bel[i] != id || a[i] <= val) continue;
            if ((a[i] -= val) >= pw[id]) continue;
            int got = getid(a[i]); ins(got, rot[got], 1, n, i, a[i]);
        }
        return rebuild(id, rt, l, r);
    }
    int mid = (l + r) >> 1; pushdown(id, rt, l, r);
    if (L <= mid) upd(id, ls, l, mid, L, R, val);
    if (R > mid) upd(id, rs, mid + 1, r, L, R, val);
    return pushup(rt);
}

inline ll queryval(int id, int rt, int l, int r, int L, int R) {
    if ((L <= l && r <= R) || !t[rt].len) return t[rt].val;
    else if (r - l < bas) {
        ll res = 0; L = max(L, l), R = min(R, r);
        for (int i = L; i <= R; ++i)
            if (bel[i] == id) res += a[i] + t[rt].tag;
        return res;
    }
    int mid = (l + r) >> 1; pushdown(id, rt, l, r); ll res = 0;
    if (L <= mid) res += queryval(id, ls, l, mid, L, R);
    if (R > mid) res += queryval(id, rs, mid + 1, r, L, R);
    return res;
}

inline ll queryMin(int id, int rt, int l, int r, int L, int R) {
    if ((L <= l && r <= R) || !t[rt].len) return t[rt].Min;
    else if (r - l < bas) {
        ll res = inf; L = max(L, l), R = min(R, r);
        for (int i = L; i <= R; ++i)
            if (bel[i] == id) res = min(res, (ll) (a[i] + t[rt].tag));
        return res;
    }
    int mid = (l + r) >> 1; pushdown(id, rt, l, r); ll res = inf;
    if (L <= mid) res = min(res, queryMin(id, ls, l, mid, L, R));
    if (R > mid) res = min(res, queryMin(id, rs, mid + 1, r, L, R));
    return res;
}

inline ll queryMax(int id, int rt, int l, int r, int L, int R) {
    if ((L <= l && r <= R) || !t[rt].len) return t[rt].Max;
    else if (r - l < bas) {
        ll res = -inf; L = max(L, l), R = min(R, r);
        for (int i = L; i <= R; ++i)
            if (bel[i] == id) res = max(res, (ll) (a[i] + t[rt].tag));
        return res;
    }
    int mid = (l + r) >> 1; pushdown(id, rt, l, r); ll res = -inf;
    if (L <= mid) res = max(res, queryMax(id, ls, l, mid, L, R));
    if (R > mid) res = max(res, queryMax(id, rs, mid + 1, r, L, R));
    return res;
}

inline void init() {
    V = *max_element(a + 1, a + 1 + n), Maxb = getid(V), pw[0] = 1;
    for (int i = 1; i <= Maxb; ++i) pw[i] = pw[i - 1] * bas;
    for (int i = 1; i <= n; ++i) bel[i] = getid(a[i]);
    for (int i = 0; i <= Maxb; ++i) build(i, rot[i], 1, n);
    return ;
}

inline void modify(int l, int r, int val) {
    int Maxi = min(Maxb, getid(val));
    for (int i = Maxi; i <= Maxb; ++i) upd(i, rot[i], 1, n, l, r, val);
    return ;
}

inline ll qv(int l, int r) {
    ll res = 0;
    for (int i = 0; i <= Maxb; ++i)
        res += queryval(i, rot[i], 1, n, l, r);
    return res;
}

inline ll qi(int l, int r) {
    ll res = inf;
    for (int i = 0; i <= Maxb; ++i)
        res = min(res, queryMin(i, rot[i], 1, n, l, r));
    return res;
}

inline ll qa(int l, int r) {
    ll res = -inf;
    for (int i = 0; i <= Maxb; ++i)
        res = max(res, queryMax(i, rot[i], 1, n, l, r));
    return res;
}

int main() {
    // freopen("P7447.in", "r", stdin);
    // freopen("P7447.out", "w", stdout);
    read(n, m); for (int i = 1; i <= n; ++i) read(a[i]);
    init(); ll res = 0;
    for (int i = 1; i <= m; ++i) {
        int op, l, r, val; read(op, l, r); l ^= res, r ^= res;
        if (op == 1) read(val), val ^= res, modify(l, r, val);
        else printf("%lld %lld %lld\n", res = qv(l, r), qi(l, r), qa(l, r)), res &= ((1 << 20) - 1);
    }
    return 0;
}