「笔记」势能线段树

Intro.

Prob. A

给定一个长度为 $n$ 的数列 $a$ 和 $m$ 次操作，每次操作是下列操作中的一个：

1. 选定区间 $[l, r]$，然后令所有 $i \in [l, r], a_i \gets \sqrt {a_i}$；
2. 选定区间 $[l,r]$，查询 $\sum a_i, i \in [l, r]$。

回答每次询问。

Prob. B

给定一个长度为 $n$ 的数列 $a$ 和 $m$ 次操作，每次操作是下列操作中的一个：

1. 选定区间 $[l,r]$，查询 $\sum a_i, i \in [l, r]$。
2. 选定区间 $[l, r]$ 和一个数 $x$，然后令所有 $i \in [l, r], a_i \gets a_i \bmod x$；
3. 选定下标 $k$ 和一个数 $x$，令 $a_k \gets x$。

回答每次询问。

Sol.

考虑无论是 Prob. A 还是 Prob. B，运算都不具有结合律，所以对于这种区间查询问题，我们没有办法通过懒标记线段树解决。但是如果我们考虑这两个运算的性质，问题便迎刃而解了。

正如标题所说，能维护这两类东西的数据结构叫做势能线段树。其意义大概是这两个运算都具有操作后的值都不大于原值的性质。正如具有势能的物体从高到低滚下一般，对于某一个元素，它的值也只能不断变小。

因此我们在修改阶段做一个剪枝：维护修改区间内的最大值，如果最大值在操作后都不变化，那么可以直接跳过这个区间。

于是我们就做完了。

P4145 上帝造题的七分钟 2 / 花神游历各国

如上所述，考虑有 $\sqrt{x}<x, x \notin {0, 1}$ 同时有 $\sqrt{x}=x, x \in{0,1}$，于是我们同时维护区间最大值，如果区间最大值不大于 $1$，那么我们就直接跳过修改。

代码

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

using i64 = long long;
struct Node {
    i64 sum;
    i64 mx; 

    Node() : sum(0), mx(0) {} 
    Node(i64 v) : sum(v), mx(v) {}

    friend Node operator+(const Node &lhs, const Node &rhs) {
        Node res;
        res.sum = lhs.sum + rhs.sum;
        res.mx = std::max(lhs.mx, rhs.mx);
        return res;
    }
};

template <class S> struct SegTree {
    int n;
    std::vector<S> tree;

    void build(auto &&v, int p, int l, int r) {
        if (l == r) {
            tree[p] = S(v[l]); 
            return;
        }
        int mid = l + (r - l) / 2;
        build(v, 2 * p, l, mid);
        build(v, 2 * p + 1, mid + 1, r);
        pull(p);
    }

    void pull(int p) { tree[p] = tree[2 * p] + tree[2 * p + 1]; }

    S query(int ql, int qr, int p, int l, int r) {
        if (r < ql or qr < l)
            return S(); 
        if (ql <= l and r <= qr)
            return tree[p];
        int mid = l + (r - l) / 2;
        return query(ql, qr, 2 * p, l, mid) + 
               query(ql, qr, 2 * p + 1, mid + 1, r);
    }

    void update_adhoc(int ql, int qr, int p, int l, int r) {
        if (tree[p].mx <= 1) {
            return;
        }
        if (r < ql or qr < l) {
            return;
        }
        if (l == r) {
            tree[p].sum = sqrtl(tree[p].sum);
            tree[p].mx = tree[p].sum;
            return;
        }

        int mid = l + (r - l) / 2;
        update_adhoc(ql, qr, 2 * p, l, mid);
        update_adhoc(ql, qr, 2 * p + 1, mid + 1, r);
        
        pull(p);
    }

    SegTree(int n) : n(n), tree(4 * n) {}
    SegTree(auto &&v) : n(v.size()), tree(4 * n) {
        build(v, 1, 0, n - 1);
    }

    i64 Query(int l, int r) { 
        return query(l, r, 1, 0, n - 1).sum; 
    }
    
    void UpdateAdhoc(int l, int r) {
        update_adhoc(l, r, 1, 0, n - 1);
    }
};

using Seg = SegTree<Node>;

signed main() {
    int n;
    cin >> n;
    vector<i64> a(n);
    for (auto &x : a) cin >> x;
    Seg st(a); 
    int m;
    cin >> m;
    while (m--) {
        int k, l, r;
        cin >> k >> l >> r;
        l--, r--;
        if (l > r) swap(l, r);
        if (k == 0) {
            st.UpdateAdhoc(l, r);
        }
        if (k == 1) {
            cout << st.Query(l, r) << "\n";
        }
    }
}
auto FAST_IO = cin.tie(nullptr)->sync_with_stdio(false);

CF438D The Child and Sequence

同理，我们也是在区间修改的地方做剪枝。同样地维护区间最大值，如果区间最大值比当前模数小，那么取模之后还是原值，我们就跳过这个修改区间。

代码

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

#define dbg(x) std::println(std::cerr, "{}:\n{}", #x, x)

template <class S> struct SegTree {
    int n;
    std::vector<S> tree;

    void pull(int p) { tree[p] = tree[2 * p] + tree[2 * p + 1]; }

    void build(auto &&v, int p, int l, int r) {
        if (l == r) {
            tree[p] = S(v[l]);
            return;
        }
        int mid = l + (r - l) / 2;
        build(v, 2 * p, l, mid);
        build(v, 2 * p + 1, mid + 1, r);
        pull(p);
    }

    S query(int ql, int qr, int p, int l, int r) {
        if (ql > r or qr < l)
            return {};
        if (ql <= l and r <= qr)
            return tree[p];
        int mid = l + (r - l) / 2;
        return query(ql, qr, 2 * p, l, mid) + 
               query(ql, qr, 2 * p + 1, mid + 1, r);
    }

    void update(int pos, const S &val, int p, int l, int r) {
        if (l == r) {
            tree[p] = val;
            return;
        }
        int mid = l + (r - l) / 2;
        if (pos <= mid)
            update(pos, val, 2 * p, l, mid);
        else
            update(pos, val, 2 * p + 1, mid + 1, r);
        pull(p);
    }

    SegTree() : n(0) {}
    SegTree(int _n) : n(_n), tree(4 * n, {}) {}
    SegTree(auto &&v) : n(v.size()) {
        tree.resize(4 * n);
        build(v, 1, 0, n - 1);
    }

    S Query(int l, int r) { return query(l, r, 1, 0, n - 1); }

    void Update(int p, const S &v) { update(p, v, 1, 0, n - 1); }
};

struct Info {
    long long sum = 0;
    int mx = 0;

    Info() = default;
    Info(int val) : sum(val), mx(val) {}

    friend Info operator+(const Info &l, const Info &r) {
        Info res = {};
        res.sum = l.sum + r.sum;
        res.mx = max(l.mx, r.mx);
        return res;
    }
};

using Seg = SegTree<Info>;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> ina(n);
    for (auto &x : ina)
        cin >> x;

    Seg seg(ina);

    while (m--) {
        int op;
        cin >> op;
        if (op == 1) {
            int l, r;
            cin >> l >> r;
            l--, r--;
            cout << seg.Query(l, r).sum << "\n";
        }
        if (op == 2) {
            int l, r, x;
            cin >> l >> r >> x;
            l--, r--;
            auto modify = [&](this auto &&self, 
                 int ql, int qr, int x, int p, int l, int r) -> void {
                if (seg.tree[p].mx < x)
                    return;
                if (l == r) {
                    seg.tree[p].sum %= x;
                    seg.tree[p].mx %= x;
                    return;
                }
                int mid = l + (r - l) / 2;
                if (ql <= mid) {
                    self(ql, qr, x, 2 * p, l, mid);
                }
                if (qr > mid) {
                    self(ql, qr, x, 2 * p + 1, mid + 1, r);
                }
                seg.pull(p);
            };
            modify(l, r, x, 1, 0, n - 1);
        }
        if (op == 3) {
            int k, x;
            cin >> k >> x;
            k--;
            seg.Update(k, x);
        }
    }
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int T = 1;
    while (T--)
        solve();
    return 0;
}