吊打倍增分块

· · 题解

Description

给定长为 n 的序列 a=(a_1,a_2,\cdots,a_n)，有 m 个操作，分以下两种：

Limitations

本题强制在线

1 \le n,m \le 5\times 10^5 1 \le l \le r \le n 0 \le a_i,k \le 10^9 6\text{s},512\text{MB}

Solution

考虑上线段树，但 a_i \neq k 很棘手，先分讨一下。

下面设当前节点的最小值为 \textit{min}。

若 \textit{min} > k，直接打标记即可。

若 \textit{min} < k，遍历所有 \textit{min} < k 的儿子进行修改，由于每个数至多只会修改一次，所以这部分耗费 \mathcal{O}(\log n) 时间（单次操作）。

若 \textit{min} = k，考虑维护次小值 \textit{sec}。

综上述，时间复杂度 \mathcal{O}(n\log n \log V)。

Code

4.59\text{KB},12.96\text{s},55.88\text{MB}\; \texttt{(in total, C++ 20 with O2)} 
// Problem: P9069 [Ynoi Easy Round 2022] 堕天作战 TEST_98
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9069
// Memory Limit: 512 MB
// Time Limit: 6000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

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

using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;

template<class T>
bool chmax(T &a, const T &b){
    if(a < b){ a = b; return true; }
    return false;
}

template<class T>
bool chmin(T &a, const T &b){
    if(a > b){ a = b; return true; }
    return false;
}

constexpr ui64 inf = ULLONG_MAX;

namespace seg_tree {
    struct Node {
        int l, r, cnt;
        ui64 sum, min, sec, tag, mark;
    };

    inline int ls(int u) { return 2 * u + 1; }
    inline int rs(int u) { return 2 * u + 2; }

    struct SegTree {
        vector<Node> tr;
        inline SegTree() {}
        inline SegTree(const vector<int>& a) {
            const int n = a.size();
            tr.resize(n << 1);
            build(0, 0, n - 1, a);
        }

        inline void pushup(int u, int mid) {
            tr[u].sum = tr[ls(mid)].sum + tr[rs(mid)].sum;
            if (tr[ls(mid)].min == tr[rs(mid)].min) {
                tr[u].min = tr[ls(mid)].min;
                tr[u].cnt = tr[ls(mid)].cnt + tr[rs(mid)].cnt;
                tr[u].sec = min(tr[ls(mid)].sec, tr[rs(mid)].sec);
            }
            else if (tr[ls(mid)].min < tr[rs(mid)].min) {
                tr[u].min = tr[ls(mid)].min;
                tr[u].cnt = tr[ls(mid)].cnt;
                tr[u].sec = min(tr[ls(mid)].sec, tr[rs(mid)].min);
            }
            else {
                tr[u].min = tr[rs(mid)].min;
                tr[u].cnt = tr[rs(mid)].cnt;
                tr[u].sec = min(tr[ls(mid)].min, tr[rs(mid)].sec);
            }
        }

        inline void apply_tag(int u, ui64 tag) {
            int len = tr[u].r - tr[u].l + 1;
            tr[u].sum -= tag * len;
            tr[u].min -= tag;
            tr[u].sec -= tag;
            tr[u].tag += tag;
        }

        inline void apply_mark(int u, ui64 tag) {
            const int len = tr[u].r - tr[u].l + 1;
            tr[u].sum -= tag * (len - tr[u].cnt);
            tr[u].sec -= tag;
            tr[u].mark += tag;
        }

        inline void pushdown(int u, int mid) {
            if (tr[u].tag) { 
                apply_tag(ls(mid), tr[u].tag);
                apply_tag(rs(mid), tr[u].tag);
                tr[u].tag = 0;
            }
            if (tr[u].mark) {
                if (tr[ls(mid)].min == tr[u].min) apply_mark(ls(mid), tr[u].mark);
                else apply_tag(ls(mid), tr[u].mark);
                if (tr[rs(mid)].min == tr[u].min) apply_mark(rs(mid), tr[u].mark);
                else apply_tag(rs(mid), tr[u].mark);
                tr[u].mark = 0;
            }
        }

        inline void build(int u, int l, int r, const vector<int>& a) {
            tr[u].l = l, tr[u].r = r;
            if (l == r) {
                tr[u].sum = tr[u].min = a[l];
                tr[u].cnt = 1;
                tr[u].sec = inf;
                return;
            }
            const int mid = (l + r) >> 1;
            build(ls(mid), l, mid, a);
            build(rs(mid), mid + 1, r, a);
            pushup(u, mid);
        }

        inline void defeat(int u, ui64 val) {
            const int len = tr[u].r - tr[u].l + 1;
            if (tr[u].min == val && len == tr[u].cnt) return;
            if (tr[u].l == tr[u].r) {
                tr[u].sum -= val;
                tr[u].min = tr[u].sum;
                return;
            }
            if (tr[u].min < val || tr[u].sec <= val * 2) {
                const int mid = (tr[u].l + tr[u].r) >> 1;
                pushdown(u, mid);
                defeat(ls(mid), val);
                defeat(rs(mid), val);
                return pushup(u, mid);
            }
            if (tr[u].min == val) apply_mark(u, val);
            else apply_tag(u, val);
        }

        inline void modify(int u, int l, int r, ui64 val) {
            if (l <= tr[u].l && tr[u].r <= r) return defeat(u, val);
            const int mid = (tr[u].l + tr[u].r) >> 1;
            pushdown(u, mid);
            if (l <= mid) modify(ls(mid), l, r, val);
            if (r > mid) modify(rs(mid), l, r, val);
            pushup(u, mid);
        }

        inline ui64 query(int u, int l, int r) {
            if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
            const int mid = (tr[u].l + tr[u].r) >> 1;
            ui64 res = 0;
            pushdown(u, mid);
            if (l <= mid) res += query(ls(mid), l, r);
            if (r > mid) res += query(rs(mid), l, r);
            return res;
        }

        inline void range_subtract(int l, int r, ui64 x) { modify(0, l, r, x); }
        inline ui64 range_sum(int l, int r) { return query(0, l, r); }
    };
}
using seg_tree::SegTree;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int n, m; scanf("%d %d", &n, &m);
    vector<int> a(n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    SegTree sgt(a);
    ui64 lst = 0;
    for (int i = 0, op, l, r, x; i < m; i++) {
        scanf("%d %d %d", &op, &l, &r);
        l ^= lst, r ^= lst, l--, r--;
        if (op == 1) {
            scanf("%d", &x), x ^= lst;
            if (x != 0) sgt.range_subtract(l, r, (ui64)x);
        }
        else {
            printf("%llu\n", lst = sgt.range_sum(l, r));
            lst &= 1048575;
        }
    }
    return 0;
}