不想写平衡树

pystraf11 · 2025-10-03 21:09:43 · 题解

Description

给定序列 a=(a_1,a_2,\cdots,a_n)，执行 q 次操作：

• 1 l r x：对每个 i\in[l,r] 执行 a_i\gets x。
• 2 l r x：对每个 i\in[l,r] 执行 a_i\gets a_i+(i-l+1)x。
• 3 p x：在 a_p 前插入 x。
• 4 l r：求 \sum_{i=l}^r a_i。

Limitations

Solution

平衡树太难写了怎么办？用块状链表！

每块用 vector 维护块内元素，以及它们的和 \text{sum}，以及三个标记：

修改时，对每个块 b\in [\text{bel}_l,\text{bel}_r]：

• 如果是散块，直接暴力改，然后更新 \text{sum}。
• 如果是整块，对于操作 1，直接 \text{cov}\gets v 然后清除另两个标记，对于操作 2，先 \text{delta}\gets \text{delta}+v，再 \text{add}\gets \text{add}+(L_b - l) \times v（补上前面加的）。

对于插入，我们直接用 vector::insert，但是插入过多元素会导致块膨胀，进而让复杂度假掉，所以当块长大于 2B 时，要把该块拆成两个。

然后就做完了，时间复杂度 O(n+q\sqrt n)，空间复杂度 O(n+q)，注意块长要取固定的，不然一开始 n 过小然后大量插入就炸了。

::::info[code] 使用 list 实现。

细节很多，要注意。

#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;
}

// ai + add + delta * i

struct Block {
    vector<i64> seq;
    int L, R;
    i64 cov, add, delta, sum;

    inline Block() {}
    inline Block(const vector<i64>::iterator a, int l, int r) {
        int len = r - l + 1; seq.resize(len);
        L = l, R = r, cov = -1, add = delta = 0;
        for (int i = 0; i < len; i++) seq[i] = a[i];
        update_sum();
    }

    inline void update_sum() {
        sum = 0;
        for (i64 x : seq) sum += x;
    }

    inline void pushdown() {
        if (cov == -1 && add == 0 && delta == 0) return;
        int len = seq.size();
        for (int i = 0; i < len; i++) {
            if (cov != -1) seq[i] = cov;
            seq[i] += add + delta * (i + 1);
        }
        cov = -1, add = delta = 0;
        update_sum();
    }

    inline void modify(int l, int r, i64 cov_val, i64 add_val, i64 delta_val) {
        for (int i = l; i <= r; i++) {
            if (cov_val != -1) seq[i] = cov_val;
            seq[i] += add_val + delta_val * (i - l + 1);
        }
        update_sum();
    }

    inline void modify(i64 cov_val, i64 add_val, i64 delta_val) {
        if (cov_val != -1) {
            cov = cov_val;
            add = 0;
            delta = 0;
        } else {
            add += add_val;
            delta += delta_val;
        }
    }

    inline i64 ask(int l, int r) {
        i64 res = 0;
        for (int i = l; i <= r; i++) res += seq[i];
        return res;
    }

    inline i64 ask() {
        if (cov != -1) {
            i64 res = cov * seq.size();
            res += add * seq.size();
            res += delta * seq.size() * (seq.size() + 1) / 2;
            return res;
        } else {
            i64 res = sum;
            res += add * seq.size();
            res += delta * seq.size() * (seq.size() + 1) / 2;
            return res;
        }
    }

    inline void move() { L++; R++; }    
    inline void insert(int x, i64 v) {
        seq.insert(seq.begin() + x, v);
        R++;
        update_sum();
    }
};

constexpr int B = 800;
using iter = list<Block>::iterator;

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

    int n, q;
    cin >> n >> q;

    vector<i64> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    const int blocks = (n + B - 1) / B;
    list<Block> blks;

    for (int i = 0; i < blocks; i++) {
        int bl = i * B, br = min(bl + B, n) - 1;
        blks.emplace_back(a.begin() + bl, bl, br);
    }

    auto bel = [&](int x) {
        for (iter it = blks.begin(); it != blks.end(); it++)
            if (it->L <= x && x <= it->R) return it;
        return prev(blks.end());
    };

    auto refact = [&](iter b) {
        b->pushdown();
        int len = b->seq.size();
        int mid = len / 2;
        vector<i64> left(b->seq.begin(), b->seq.begin() + mid);
        vector<i64> right(b->seq.begin() + mid, b->seq.end());

        Block left_blk(left.begin(), b->L, b->L + mid - 1);
        Block right_blk(right.begin(), b->L + mid, b->R);

        iter next_it = next(b);
        blks.insert(next_it, left_blk);
        blks.insert(next_it, right_blk);
        blks.erase(b);
    };

    auto _modify = [&](iter b, int l, int r, i64 cov, i64 add, i64 delta) {
        b->pushdown();
        b->modify(l - b->L, r - b->L, cov, add, delta);
    };

    auto _ask = [&](iter b, int l, int r) {
        b->pushdown();
        return b->ask(l - b->L, r - b->L);
    };

    auto modify = [&](int l, int r, i64 cov, i64 add, i64 delta) {
        iter bl = bel(l), br = bel(r);
        if (bl == br) {
            _modify(bl, l, r, cov, add, delta);
            return;
        }

        _modify(bl, l, bl->R, cov, add, delta);
        i64 add_br = add + (br->L - l) * delta;
        _modify(br, br->L, r, cov, add_br, delta);

        iter it = next(bl);
        while (it != br) {
            i64 add_it = add + (it->L - l) * delta;
            it->modify(cov, add_it, delta);
            it++;
        }
    };

    auto ask = [&](int l, int r) {
        iter bl = bel(l), br = bel(r);
        if (bl == br) return _ask(bl, l, r);

        i64 res = _ask(bl, l, bl->R);
        res += _ask(br, br->L, r);

        iter it = next(bl);
        while (it != br) {
            res += it->ask();
            it++;
        }
        return res;
    };

    auto insert = [&](int x, i64 v) {
        iter b = bel(x);
        b->pushdown();
        b->insert(x - b->L, v);
        n++;

        iter it = next(b);
        while (it != blks.end()) {
            it->move();
            it++;
        }

        if (b->seq.size() >= 2 * B) refact(b);
    };

    for (int i = 0, op, l, r, x; i < q; i++) {
        cin >> op >> l, l--;
        if (op == 1) {
            cin >> r >> x, r--;
            modify(l, r, x, 0, 0);
        } else if (op == 2) {
            cin >> r >> x, r--;
            modify(l, r, -1, 0, x);
        } else if (op == 3) {
            cin >> x;
            insert(l, x);
        } else {
            cin >> r, r--;
            cout << ask(l, r) << '\n';
        }
    }

    return 0;
}
::::