倍增分块

pystraf11 · 2025-09-05 16:49:39 · 题解

Description

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

1 l r x：对每个 i\in[l,r] 执行 a_i\gets a_i-x\times [a_i>x]。
2 l r：求 \sum\limits_{i=l}^r a_i,\min\limits_{i=l}^r a_i,\max\limits_{i=l}^r a_i。

Limitations

1\le n,m\le 5\times 10^5

1\le a_i,x\le 10^9

1\le l\le r\le n

6\text{s},\textcolor{red}{64\text{MB}}

Solution

首先考虑一种势能线段树：

每个节点维护所管辖区间的最值，在执行 \operatorname{subtract} 时：

若当前 \max< x，操作没有效果，直接退出。

若当前 \min> x，所有数都会被影响，给当前节点打上一个减去 x 的标记。

但是这玩意的复杂度是错的，只要给一个 1,10^9 交替的序列，每次 \operatorname{subtract}(1,n,1) 就被卡成 O(nm) 了。

序列分块似乎也做不了，只能对值域分块，由于 V 可达 10^9，所以要用倍增分块，将 [b^i,b^{i+1}) 分为一块，总共有 \lceil \log_b V\rceil 块，其中 b 为底数。

对每个值域块，维护一棵上面所述的线段树，容易发现每个数最多减 b 次就会掉出该块管辖范围，至于这些掉出的元素，因为一个数最多掉出 O(\log_b V) 次，可以直接暴力找块插入。

这样做的时间复杂度为 O(nb\log n\log_b V)，空间复杂度为 O(n \log_b V)。

然而由于常数比较大，b 取 2 是不够的，需要调大。

空间限制很紧，但是强制在线无法逐块处理，注意到线段树的底下几层很浪费空间，于是若节点的长度小于一个阈值 L 时，直接暴力处理。

还有其他细节需要注意： - 线段树节点不要存 $l,r$，容易被卡。 - 处理插入元素时，不要给新插入的元素错误地打上标记。 - 区间的元素不再是 $r-l+1$ 个，需要维护 $\textit{cnt}$ 表示元素个数。 - 由于所有线段树底层共用一个 $a$，需要先判断是否在本块范围内再操作。 # Code $6.83\text{KB},4.37\text{s},12.50\text{MB}\;\texttt{(in total, C++20 with O2)}

只给主要部分.

namespace block {
    struct data {
        i64 sum;
        int max, min, cnt;

        inline data() : sum(0), max(0), min(inf), cnt(0) {}
        inline data(i64 _sum, int _max, int _min, int _cnt)
            : sum(_sum), max(_max), min(_min), cnt(_cnt) {}
    };

    inline data operator+(const data& a, const data& b) {
        return data(
            a.sum + b.sum,
            std::max(a.max, b.max),
            std::min(a.min, b.min),
            a.cnt + b.cnt
        );
    }

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

    struct segment_tree {
        int n, bl, br;
        vector<data> info;
        vector<int> tag;

        vector<int>::iterator a;
        vector<bool>::iterator fall;

        inline segment_tree() {}
        inline void init(int _n, int _bl, int _br) {
            n = _n, bl = _bl, br = _br;
            const int cap = std::max(1, n >> 3);
            info.resize(cap), tag.resize(cap);
        }

        inline void leaf_remove(int u, int l, int r, int ql, int qr, int v, vector<int>& trash) {
            data res;
            for (int i = l; i <= r; i++)
                if (bl <= a[i] && a[i] <= br) {
                    a[i] -= tag[u];
                    if (ql <= i && i <= qr && a[i] > v) {
                        a[i] -= v;
                        if (a[i] < bl) {
                            trash.push_back(i);
                            fall[i] = true;
                            continue;
                        }
                    }
                    res = res + data(a[i], a[i], a[i], 1);
                }

            info[u] = res;
            tag[u] = 0;
        }

        inline void leaf_insert(int u, int l, int r) {
            data res;
            for (int i = l; i <= r; i++)
                if (bl <= a[i] && a[i] <= br) {
                    if (!fall[i]) a[i] -= tag[u];
                    else fall[i] = false;
                    res = res + data(a[i], a[i], a[i], 1);
                }

            info[u] = res;
            tag[u] = 0;
        }

        inline data leaf_query(int u, int l, int r, int ql, int qr) {
            data res;
            for (int i = l; i <= r; i++)
                if (bl <= a[i] && a[i] <= br) {
                    a[i] -= tag[u];
                    if (ql <= i && i <= qr)
                        res = res + data(a[i], a[i], a[i], 1);
                }

            tag[u] = 0;
            return res;
        }

        inline void pushup(int u) {
            info[u] = info[ls(u)] + info[rs(u)];
        }

        inline void apply(int u, int k) {
            tag[u] += k;
            info[u].sum -= 1LL * info[u].cnt * k;
            info[u].max -= k, info[u].min -= k;
        }

        inline void pushdown(int u) {
            if (tag[u]) {
                apply(ls(u), tag[u]);
                apply(rs(u), tag[u]);
                tag[u] = 0;
            }
        }

        void build(int u, int l, int r) {
            if (r - l < L) return void(info[u] = leaf_query(u, l, r, l, r));
            const int mid = (l + r) >> 1;
            build(ls(u), l, mid);
            build(rs(u), mid + 1, r);
            pushup(u);
        }

        void insert(int u, int l, int r, int i) {
            if (r - l < L) return leaf_insert(u, l, r);
            const int mid = (l + r) >> 1;
            pushdown(u);
            if (i <= mid) insert(ls(u), l, mid, i);
            else insert(rs(u), mid + 1, r, i);
            pushup(u);
        }

        void modify(int u, int l, int r, int ql, int qr, int v, vector<int>& trash) {
            if (info[u].max <= v) return;
            if (ql <= l && r <= qr && info[u].min - v >= bl) return apply(u, v);
            if (r - l < L) return leaf_remove(u, l, r, ql, qr, v, trash);

            const int mid = (l + r) >> 1;
            pushdown(u);
            if (ql <= mid) modify(ls(u), l, mid, ql, qr, v, trash);
            if (qr > mid) modify(rs(u), mid + 1, r, ql, qr, v, trash);
            pushup(u);
        }

        data query(int u, int l, int r, int ql, int qr) {
            if (ql <= l && r <= qr) return info[u];
            if (r - l < L) return leaf_query(u, l, r, ql, qr);

            const int mid = (l + r) >> 1;
            pushdown(u);
            if (qr <= mid) return query(ls(u), l, mid, ql, qr);
            else if (ql > mid) return query(rs(u), mid + 1, r, ql, qr);
            else return query(ls(u), l, mid, ql, qr) + query(rs(u), mid + 1, r, ql, qr);
        }

        inline void insert(int i) {
            insert(0, 0, n - 1, i);
        }

        inline void subtract(int l, int r, int v, vector<int>& trash) {
            modify(0, 0, n - 1, l, r, v, trash);
        }

        inline data query(int l, int r) {
            return query(0, 0, n - 1, l, r);
        }

        inline void build() {
            build(0, 0, n - 1);
        }
    };

    struct blocks {
        int n;
        vector<segment_tree> sgt;
        vector<int> trash;
        vector<bool> fall;
        vector<int>::iterator a;

        inline blocks() {}
        inline blocks(int _n) : n(_n) {}

        inline void init(vector<int>& a) {
            sgt.resize(B + 1);
            fall.resize(n);
            for (int j = 0; j <= B; j++) {
                const int bl = 1 << (j * B);
                const int br = (1 << ((j + 1) * B)) - 1;
                sgt[j].init(n, bl, br);
                sgt[j].a = a.begin();
                sgt[j].fall = fall.begin();
                sgt[j].build();
            }

            this->a = a.begin();
        }

        inline void subtract(int l, int r, int x) {
            for (int j = 0; j <= B; j++) {
                sgt[j].subtract(l, r, x, trash);
                if (j > 0) {
                    for (auto i : trash) 
                        for (int k = 0; k < j; k++)
                            if (sgt[k].bl <= a[i] && a[i] <= sgt[k].br) {
                                sgt[k].insert(i);
                                break;
                            }
                    trash.clear();
                }
            }
        }

        inline data query(int l, int r) {
            data res;
            for (int j = 0; j <= B; j++) res = res + sgt[j].query(l, r);
            return res;
        }
    };
}