title: 经典数据结构问题
categories:

ICPC
tags:
null
abbrlink: cecfa4d9
date: 2023-03-31 00:00:00

经典数据结构问题

静态区间颜色数

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    int m;
    cin >> m;
    int mx = *max_element(alls(a));
    vector<vector<pii>> q(n + 1);
    for (int i = 1; i <= m; i++) {
        int l, r;
        cin >> l >> r;
        q[r].push_back({l, i});
    }
    deb("?");
    Fwk<int> fwk(mx + 10);
    vector<int> last(mx + 1);
    auto add = [&](int l, int r, int x) {
        fwk.add(l, x);
        fwk.add(r + 1, -x);
    };
    vector<int> ans(m + 1);
    deb("?");
    for (int r = 1; r <= n; r++) {
        add(last[a[r]] + 1, r, 1);
        last[a[r]] = r;
        for (auto [l, id] : q[r]) {
            ans[id] = fwk.sum(l);
        }
    }
    for (int i = 1; i <= m; i++) cout << ans[i] << endl;
}

静态区间不同数之和

void solve() {
    int n, m;
    cin >> n;
    cin >> m;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    // int m;
    // cin >> m;
    int mx = *max_element(alls(a));
    vector<vector<pii>> q(n + 1);
    for (int i = 1; i <= m; i++) {
        int l, r;
        cin >> l >> r;
        q[r].push_back({l, i});
    }
    deb("?");
    Fwk<int> fwk(mx + 10);
    vector<int> last(mx + 1);
    auto add = [&](int l, int r, int x) {
        fwk.add(l, x);
        fwk.add(r + 1, -x);
    };
    vector<int> ans(m + 1);
    deb("?");
    for (int r = 1; r <= n; r++) {
        add(last[a[r]] + 1, r, a[r]);
        last[a[r]] = r;
        for (auto [l, id] : q[r]) {
            ans[id] = fwk.sum(l);
        }
    }
    for (int i = 1; i <= m; i++) cout << ans[i] << endl;
}

静态二维数点:多次询问一个矩形内有多少个点

void solve() {
    vector<int> vy;
    int n, m;
    cin >> n >> m;
    vector<a5> event;
    for (int i = 1; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        vy.push_back(y);
        event.push_back({x, 0, 0, y, 0});
    }
    Fwk<int> fwk(n + 1);
    for (int i = 1; i <= m; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        event.push_back({x1 - 1, 1, 1, y1 - 1, i});
        event.push_back({x2, 1, 1, y2, i});
        event.push_back({x1 - 1, 1, -1, y2, i});
        event.push_back({x2, 1, -1, y1 - 1, i});
    }
    sort(alls(vy));
    vy.erase(unique(alls(vy)), vy.end());
    sort(alls(event));
    vector<int> ans(m + 1);
    for (auto [x, ty, sgn, y, id] : event) {
        if (ty == 0) {
            int val = lower_bound(alls(vy), y) - vy.begin() + 1;
            assert(val <= n);
            fwk.add(val, 1);
        } else {
            int val = upper_bound(alls(vy), y) - vy.begin() + 1 - 1;
            assert(val <= n);
            ans[id] += sgn * fwk.sum(val);
        }
    }
    for (int i = 1; i <= m; i++) cout << ans[i] << endl;
}

矩形面积并：扫描线维护最小值出现次数

template <class Info, class Tag>
struct LazySegmentTree {
    int n;
    vector<Info> info;
    vector<Tag> tag;
    LazySegmentTree() : n(0) {}
    LazySegmentTree(int n_, Info v_ = Info()) { init(vector<Info>(n_ + 1, v_)); }
    LazySegmentTree(vector<Info> t_) { init(t_); }
    void init(vector<Info> a)  //[1,n]
    {
        n = a.size() - 1;
        info.assign((n << 2) + 1, Info());
        tag.assign((n << 2) + 1, Tag());
        function<void(int, int, int)> build = [&](int x, int l, int r) -> void {
            if (l == r) {
                info[x] = a[l];
                return;
            }
            int mid = (l + r) >> 1;
            build(x << 1, l, mid);
            build(x << 1 | 1, mid + 1, r);
            pushup(x);
        };
        build(1, 1, n);
    }
    void pushup(int x) { info[x] = info[x << 1] + info[x << 1 | 1]; }
    void apply(int p, const Tag& v) {
        info[p].apply(v);  // 标记更新自己
        tag[p].apply(v);   // 下传标记
    }
    void pushdown(int x) {
        apply(x << 1, tag[x]);
        apply(x << 1 | 1, tag[x]);
        tag[x] = Tag();
    }
    void update(int x, int l, int r, int p, const Info& v) {
        if (l == r) {
            info[x] = v;
            return;
        }
        int mid = (l + r) >> 1;
        pushdown(x);
        if (p <= mid)
            update(x << 1, l, mid, p, v);
        else
            update(x << 1 | 1, mid + 1, r, p, v);
        pushup(x);
    }
    void update(int p, const Info& v) { update(1, 1, n, p, v); }
    Info query(int x, int l, int r, int ql, int qr) {
        if (l > qr || r < ql)
            return Info();
        if (ql <= l && r <= qr)
            return info[x];
        int mid = (l + r) >> 1;
        pushdown(x);
        return query(x << 1, l, mid, ql, qr) +
               query(x << 1 | 1, mid + 1, r, ql, qr);
    }
    Info query(int ql, int qr) { return query(1, 1, n, ql, qr); }
    void rangeupdate(int x, int l, int r, int ql, int qr, const Tag& v) {
        if (l > qr || r < ql)
            return;
        if (ql <= l && r <= qr) {
            apply(x, v);
            return;
        }
        int mid = (l + r) >> 1;
        pushdown(x);
        rangeupdate(x << 1, l, mid, ql, qr, v);
        rangeupdate(x << 1 | 1, mid + 1, r, ql, qr, v);
        pushup(x);
    }
    void rangeupdate(int ql, int qr, const Tag& v) {
        rangeupdate(1, 1, n, ql, qr, v);
    }
    template <class F>
    int findFirst(int x, int l, int r, int ql, int qr, F pred) {
        if (l > qr || r < ql || !pred(info[x]))
            return -1;
        if (l == r)
            return l;
        int mid = (l + r) >> 1;
        pushdown(x);
        int res = findFirst(x << 1, l, mid, ql, qr, pred);
        if (res == -1)
            res = findFirst(x << 1 | 1, mid + 1, r, ql, qr, pred);
        return res;
    }
    template <class F>
    int findFirst(int l, int r, F pred) {
        return findFirst(1, 1, n, l, r, pred);
    }
    template <class F>
    int findLast(int x, int l, int r, int ql, int qr, F pred) {
        if (l > qr || r < ql || !pred(info[x]))
            return -1;
        if (l == r)
            return l;
        int mid = (l + r) >> 1;
        pushdown(x);
        int res = findLast(x << 1 | 1, mid + 1, r, ql, qr, pred);
        if (res == -1)
            res = findLast(x << 1, l, mid, ql, qr, pred);
        return res;
    }
    template <class F>
    int findLast(int l, int r, F pred) {
        return findLast(1, 1, n, l, r, pred);
    }
};
struct Tag {
    ll add = 0;
    void apply(const Tag& v) { add += v.add; }  // 标记怎么合并
};
struct Info {
    ll minv = 0, mincnt = 1;
    void apply(const Tag& v) { minv += v.add; }  // 标记怎么更新节点信息
};
Info operator+(const Info& a, const Info& b) {  // 维护的信息怎么合并
    if (a.minv == b.minv)
        return {a.minv, a.mincnt + b.mincnt};
    else if (a.minv < b.minv)
        return a;
    else
        return b;
}
#define a4 array<int, 4>
void solve() {
    int n;
    cin >> n;
    vector<a4> event;
    vector<int> vy;
    for (int i = 1; i <= n; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        event.push_back({x1, 1, y1, y2});
        event.push_back({x2, -1, y1, y2});
        vy.push_back(y1);
        vy.push_back(y2);
    }
    sort(alls(vy));
    vy.erase(unique(alls(vy)), vy.end());
    vector<Info> tmp(1);
    int nodecnt = 0;
    for (int i = 1; i < (int)vy.size(); i++) {
        tmp.push_back({0, vy[i] - vy[i - 1]});
        //cerr << "tmp" << i << " " << vy[i] - vy[i - 1] << endl;
        nodecnt++;
    }

    LazySegmentTree<Info, Tag> seg(tmp);
    ll ans = 0;
    sort(alls(event));
    int prex = 0;
    ll len = seg.query(1, nodecnt).mincnt;
    for (auto [x, op, y1, y2] : event) {
        int idy1 = lower_bound(alls(vy), y1) - vy.begin() + 1;
        int idy2 = lower_bound(alls(vy), y2) - vy.begin();
        deb(x, op, y1, y2);
        deb(idy1, idy2);
        ll d = len;
        deb(len);
        auto [val, cnt] = seg.query(1, nodecnt);
        if (val == 0)
            d -= cnt;
        deb(prex, x, d);
        ans += (ll)(x - prex) * d;
        prex = x;
        seg.rangeupdate(idy1, idy2, {op});
    }
    cout << ans << endl;
}

静态区间mex:注意线段树的单点修改是赋值操作

struct Tag {
    ll add = 0;
    void apply(const Tag& v) { add += v.add; }  // 标记怎么合并
};
struct Info {
    ll sum = 0, len = 1;
    void apply(const Tag& v) { sum += len * v.add; }  // 标记怎么更新节点信息
};
Info operator+(const Info& a, const Info& b) {  // 维护的信息怎么合并
    Info c = Info();
    c.sum = min(a.sum, b.sum);
    c.len = a.len + b.len;
    return c;
}
void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    vector<vector<pii>> q(m + 1);
    for (int i = 1; i <= m; i++) {
        int l, r;
        cin >> l >> r;
        q[r].push_back({l, i});
    }
    vector<int> ans(m + 1);
    LazySegmentTree<Info, Tag> seg(n + 10);
    ////map<int, int> mp;
    for (int r = 1; r <= n; r++) {
        a[r] = min(a[r], n + 3);
        seg.update(a[r] + 1, {r, 1});
        // mp[a[r] + 1] = r;
        for (auto [l, id] : q[r]) {
            deb(id, l, r);
            ans[id] = seg.findFirst(1, n + 2, [&](Info v) {
                if (v.sum < l)
                    return true;
                return false;
            });
        }
    }
    for (int i = 1; i <= m; i++) cout << ans[i] - 1 << endl;
}

找到每个数都出现k次的区间数量

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
#define R(i, l, r) for (int i = (l); i <= (r); ++i)
const int N = 5e5 + 5;
const ll P = 1e18;
int n, a[N];


__int128 hsh[N];
signed main() {
    int t;
    cin >> t;
    while (t--) {
        int k;
        cin >> n >> k;  
        mt19937_64 rnd(time(0));
        int ans=0;
        map<int,int>rdm;
      
        map<int, int> cnt;
        map<__int128, int> mp;
        for(int i=0;i<=n;i++)hsh[i]=0;
        R(i, 1, n) {
            hsh[i] = hsh[i - 1];
            cin >> a[i];
            if(rdm.count(a[i])==0)rdm[a[i]] = rnd() % P + 1;
            hsh[i] -= 1ll * cnt[a[i]] * rdm[a[i]];
            ++cnt[a[i]];
            cnt[a[i]] %= k;
            hsh[i] += 1ll * cnt[a[i]] * rdm[a[i]];
        }
        mp[0] = 1;
        map<int, int> cnt2;
        for (int i = 1, j = 0; i <= n; ++i) {
            ++cnt2[a[i]];
            while (cnt2[a[i]] > k) --cnt2[a[j]], (j ? --mp[hsh[j - 1]] : 1), ++j;
            ans += mp[hsh[i]];
            ++mp[hsh[i]];
        }
        cout << ans << '\n';
    }
    return 0;
}

线段树维护区间加等差数列

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define Pair pair<LL, LL>
#define ls rt << 1
#define rs rt << 1 | 1
#define PI acos(-1.0)
#define eps 1e-13
#define mod 998244353
#define MAXN 50001
#define MS 100005

int n, m;
int a[MS];
struct node {
    LL val;
    LL la;
} p[MS << 2];

void push_up(int rt) {
    p[rt].val = p[ls].val + p[rs].val;
}

void push_down(int rt, int l, int r) {
    if (p[rt].la) {
        int m = l + r >> 1;
        p[ls].val += p[rt].la * (m - l + 1);
        p[rs].val += p[rt].la * (r - m);
        p[ls].la += p[rt].la;
        p[rs].la += p[rt].la;
        p[rt].la = 0;
    }
}

void build(int l, int r, int rt) {
    if (l == r) {
        p[rt].val = a[l] - a[l - 1];
        return;
    }
    int m = l + r >> 1;
    build(l, m, ls);
    build(m + 1, r, rs);
    push_up(rt);
}

void modify(int L, int R, int l, int r, int rt, LL val) {
    if (L <= l && r <= R) {
        p[rt].val += val * (r - l + 1);
        p[rt].la += val;
        return;
    }
    int m = l + r >> 1;
    push_down(rt, l, r);
    if (m >= L)
        modify(L, R, l, m, ls, val);
    if (m < R)
        modify(L, R, m + 1, r, rs, val);
    push_up(rt);
}

LL query(int L, int R, int l, int r, int rt) {
    if (L <= l && r <= R) {
        return p[rt].val;
    }
    int m = l + r >> 1;
    push_down(rt, l, r);
    LL ans = 0;
    if (m >= L)
        ans += query(L, R, l, m, ls);
    if (m < R)
        ans += query(L, R, m + 1, r, rs);
    return ans;
}

inline void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, n, 1);
    while (m--) {
        int op;
        cin >> op;
        if (op == 1) {
            LL l, r, k, d;
            cin >> l >> r >> k >> d;
            modify(l, l, 1, n, 1, k);
            if (l + 1 <= r)
                modify(l + 1, r, 1, n, 1, d);
            if (r + 1 <= n)
                modify(r + 1, r + 1, 1, n, 1, -(d * (r - l) + k));
        } else if (op == 2) {
            int pos;
            cin >> pos;
            cout << query(1, pos, 1, n, 1) << "\n";
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    //	srand((unsigned)time(0));
    //	freopen("data.in","r",stdin);
    //	freopen("data.out","w",stdout);
    int ce = 1;
    //    cin >> ce;
    //    scanf("%d",&ce);
    while (ce--) solve();

    return 0;
}
/*


*/

线段树 3（区间最值操作、区间历史最值）

给出一个长度为 $n$ 的数列 $A$ ，同时定义一个辅助数组 $B$ ， $B$ 开始与 $A$ 完全相同。接下来进行了 $m$ 次操作，操作有五种类型，按以下格式给出：

1 l r k：对于所有的 $i\in[l,r]$ ，将 $A_i$ 加上 $k$ （ $k$ 可以为负数）。
2 l r v：对于所有的 $i\in[l,r]$ ，将 $A_i$ 变成 $\min(A_i,v)$ 。
3 l r：求 $\sum_{i=l}^{r}A_i$ 。
4 l r：对于所有的 $i\in[l,r]$ ，求 $A_i$ 的最大值。
5 l r：对于所有的 $i\in[l,r]$ ，求 $B_i$ 的最大值。

在每一次操作后，我们都进行一次更新，让 $B_i\gets\max(B_i,A_i)$ 。

#include <bits/stdc++.h>

#ifdef LOCAL
#include "debug.h"
#else
#define deb(...) 114514
#endif

using namespace std;

using LL = long long;
using pii = pair<int, int>;
using pll = pair<LL, LL>;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int Mod = 1e9 + 7;
const int N = 3e5 + 10;

class LSGT {
public:
    struct tag {
        LL addmax, addmax_, add, add_;
        tag() : addmax(0), addmax_(-INF), add(0), add_(-INF) {}
        tag(LL add) : addmax(add), addmax_(add), add(add), add_(add) {}
        tag(LL addmax, LL addmax_, LL add, LL add_) : addmax(addmax), addmax_(addmax_), add(add), add_(add_) {}
        bool empty() const {
            return addmax == 0 && addmax_ == -INF && add == 0 && add_ == -INF;
        }
        void apply(const tag &o) {
            add_ = max(add_, add + o.add_);
            addmax_ = max(addmax_, addmax + o.addmax_);
            add += o.add;
            addmax += o.addmax;
        }
    };
    struct info {
        LL cntM1, sum, M1, M2, len, b;
        info() : cntM1(1), sum(0), M1(-INF), M2(-INF), len(1), b(0) {}
        info(LL x) : cntM1(1), sum(x), M1(x), M2(-INF), len(1), b(x) {}
        info(LL cntM1, LL sum, LL M1, LL M2, LL len, LL b) : cntM1(cntM1), sum(sum), M1(M1), M2(M2), len(len), b(b) {}
        friend info operator+(const info &a, const info &b) {
            info res;
            res.len = a.len + b.len;
            res.sum = a.sum + b.sum;
            res.b = max(a.b, b.b);
            if (a.M1 == b.M1) {
                res.cntM1 = a.cntM1 + b.cntM1;
                res.M1 = a.M1;
                res.M2 = max(a.M2, b.M2);
            } else if (a.M1 > b.M1) {
                res.cntM1 = a.cntM1;
                res.M1 = a.M1;
                res.M2 = max(a.M2, b.M1);
            } else {
                res.cntM1 = b.cntM1;
                res.M1 = b.M1;
                res.M2 = max(b.M2, a.M1);
            }
            return res;
        }
        void apply(const tag &o) {
            sum += o.add * len - o.add * cntM1 + o.addmax * cntM1;
            b = max(b, M1 + o.addmax_);
            M1 += o.addmax;
            M2 += o.add;
        }
    };

private:
    std::vector<info> node;
    std::vector<tag> ta;
    int siz;
    void build(int idx, int l, int r) {
        if (l == r)
            return;
        int mid = (l + r) >> 1;
        build(idx << 1, l, mid), build(idx << 1 | 1, mid + 1, r);
        node[idx] = node[idx << 1] + node[idx << 1 | 1];
    }
    template <typename T>
    void build(int idx, int l, int r, const std::vector<T> &vec) {
        if (l == r) {
            node[idx] = vec[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(idx << 1, l, mid, vec), build(idx << 1 | 1, mid + 1, r, vec);
        node[idx] = node[idx << 1] + node[idx << 1 | 1];
    }
    void apply(int idx) {
        if (ta[idx].empty())
            return;
        LL maxx = max(node[idx << 1].M1, node[idx << 1 | 1].M1);
        if (node[idx << 1].M1 == maxx)
            node[idx << 1].apply(ta[idx]), ta[idx << 1].apply(ta[idx]);
        else
            node[idx << 1].apply({ta[idx].add, ta[idx].add_, ta[idx].add, ta[idx].add_}), ta[idx << 1].apply({ta[idx].add, ta[idx].add_, ta[idx].add, ta[idx].add_});
        if (node[idx << 1 | 1].M1 == maxx)
            node[idx << 1 | 1].apply(ta[idx]), ta[idx << 1 | 1].apply(ta[idx]);
        else
            node[idx << 1 | 1].apply({ta[idx].add, ta[idx].add_, ta[idx].add, ta[idx].add_}), ta[idx << 1 | 1].apply({ta[idx].add, ta[idx].add_, ta[idx].add, ta[idx].add_});
        ta[idx] = {};
    }
    void modify(int idx, int l, int r, int ql, int qr, tag add) {
        if (add.add == 0 && add.addmax >= node[idx].M1)
            return;
        if (ql <= l && qr >= r && (add.add != 0 || add.addmax > node[idx].M2)) {
            if (add.add == 0) {
                add.addmax = -node[idx].M1 + add.addmax;
                add.addmax_ = add.addmax;
            }
            ta[idx].apply(add);
            node[idx].apply(add);
            return;
        }
        apply(idx);
        int mid = (l + r) >> 1;
        if (ql <= mid)
            modify(idx << 1, l, mid, ql, qr, add);
        if (qr > mid)
            modify(idx << 1 | 1, mid + 1, r, ql, qr, add);
        node[idx] = node[idx << 1] + node[idx << 1 | 1];
    }
    info query(int idx, int l, int r, int ql, int qr) {
        if (ql <= l && qr >= r)
            return node[idx];
        apply(idx);
        int mid = (l + r) >> 1;
        if (qr <= mid)
            return query(idx << 1, l, mid, ql, qr);
        else if (ql > mid)
            return query(idx << 1 | 1, mid + 1, r, ql, qr);
        else
            return query(idx << 1, l, mid, ql, qr) + query(idx << 1 | 1, mid + 1, r, ql, qr);
    }

public:
    LSGT(const int size) : node(size << 2), ta(size << 2), siz(size) {
        build(1, 1, siz);
    }
    template <typename T>
    LSGT(const std::vector<T> &vec) : node(vec.size() << 2), ta(vec.size() << 2), siz(vec.size() - 1) {
        build(1, 1, siz, vec);
    }
    void modify(int ql, int qr, const tag &add) {
        modify(1, 1, siz, ql, qr, add);
    }
    info query(int ql, int qr) {
        return query(1, 1, siz, ql, qr);
    }
};

void solve() {
    int n, m;
    cin >> n;
    cin >> m;
    vector<int> arr(n + 1);
    for (int i = 1; i <= n; i++) cin >> arr[i];
    LSGT tr(arr);
    while (m--) {
        int op;
        cin >> op;
        int l, r;
        cin >> l >> r;
        if (op == 1) {
            int x;
            cin >> x;
            if (x)
                tr.modify(l, r, x);
        } else if (op == 2) {
            int x;
            cin >> x;
            tr.modify(l, r, {x, 0, 0, 0});
        } else if (op == 3) {
            cout << tr.query(l, r).sum << '\n';
        } else if (op == 4) {
            cout << tr.query(l, r).M1 << '\n';
        } else if (op == 5) {
            cout << tr.query(l, r).b << '\n';
        }
    }
}

signed main() {
#ifdef LOCAL
    clock_t tttttttt = clock();
    freopen("in.txt", "r", stdin);
#endif
#ifndef LOCAL
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#endif
    //*****************************************************************
    int t = 1;
    // cin >> t;
    while (t--) solve();
//*****************************************************************
#ifdef LOCAL
    cerr << "Time Used: " << fixed << setprecision(3) << (clock() - tttttttt) / (CLOCKS_PER_SEC / 1000.0) << " ms" << endl;
#endif
    return 0;
}

区间限制最大值最小值, 区间加, 查询区间最小值最大值,区间和

class LSGT {
public:
    struct tag {
        LL add, Min, Max;
        tag() : add(0), Min(INF), Max(-INF) {}
        tag(LL add) : add(add), Min(INF), Max(-INF) {}
        tag(LL add, LL Min, LL Max) : add(add), Min(Min), Max(Max) {}
        bool empty() const {
            return add == 0 && Min == INF && Max == -INF;
        }
        void apply(const tag &o) {
            add += o.add;
            if (Min != INF)
                Min += o.add;
            if (Max != -INF)
                Max += o.add;
            if (Min <= o.Max) {
                Min = Max = o.Max;
            } else if (Max >= o.Min) {
                Min = Max = o.Min;
            } else {
                Min = min(o.Min, Min);
                Max = max(Max, o.Max);
            }
        }
    };
    struct info {
        LL cntM1, sum, M1, M2, len, cntm1, m1, m2;
        info() : cntM1(1), sum(0), M1(0), M2(-INF), len(1), cntm1(1), m1(0), m2(INF) {}
        info(LL x) : cntM1(1), sum(x), M1(x), M2(-INF), len(1), cntm1(1), m1(x), m2(INF) {}
        info(LL cntM1, LL sum, LL M1, LL M2, LL len, LL cntm1, LL m1, LL m2) : cntM1(cntM1), sum(sum), M1(M1), M2(M2), len(len), cntm1(cntm1), m1(m1), m2(m2) {}
        friend info operator+(const info &a, const info &b) {
            info res;
            res.len = a.len + b.len;
            res.sum = a.sum + b.sum;
            if (a.M1 == b.M1) {
                res.cntM1 = a.cntM1 + b.cntM1;
                res.M1 = a.M1;
                res.M2 = max(a.M2, b.M2);
            } else if (a.M1 > b.M1) {
                res.cntM1 = a.cntM1;
                res.M1 = a.M1;
                res.M2 = max(a.M2, b.M1);
            } else {
                res.cntM1 = b.cntM1;
                res.M1 = b.M1;
                res.M2 = max(b.M2, a.M1);
            }
            if (a.m1 == b.m1) {
                res.cntm1 = a.cntm1 + b.cntm1;
                res.m1 = a.m1;
                res.m2 = min(a.m2, b.m2);
            } else if (a.m1 < b.m1) {
                res.cntm1 = a.cntm1;
                res.m1 = a.m1;
                res.m2 = min(a.m2, b.m1);
            } else {
                res.cntm1 = b.cntm1;
                res.m1 = b.m1;
                res.m2 = min(a.m1, b.m2);
            }
            return res;
        }
        void apply(const tag &o) {
            sum += o.add * len;
            M1 += o.add;
            M2 += o.add;
            m1 += o.add;
            m2 += o.add;
            if (M1 == m1) {
                if (M1 > o.Min) {
                    sum -= (M1 - o.Min) * cntM1;
                    m1 = M1 = o.Min;
                }
                if (m1 < o.Max) {
                    sum -= (m1 - o.Max) * cntm1;
                    M1 = m1 = o.Max;
                }
                return;
            }
            if (o.Min == o.Max) {
                sum = len * o.Min;
                M1 = m1 = o.Min;
                cntm1 = cntM1 = len;
                return;
            }
            if (M1 > o.Min) {
                sum -= (M1 - o.Min) * cntM1;
                if (M1 == m2)
                    m2 = M1 = o.Min;
                else
                    M1 = o.Min;
            }
            if (m1 < o.Max) {
                sum -= (m1 - o.Max) * cntm1;
                if (m1 == M2)
                    m1 = M2 = o.Max;
                else
                    m1 = o.Max;
            }
        }
    };

private:
    std::vector<info> node;
    std::vector<tag> ta;
    int siz;
    void build(int idx, int l, int r) {
        if (l == r)
            return;
        int mid = (l + r) >> 1;
        build(idx << 1, l, mid), build(idx << 1 | 1, mid + 1, r);
        node[idx] = node[idx << 1] + node[idx << 1 | 1];
    }
    template <typename T>
    void build(int idx, int l, int r, const std::vector<T> &vec) {
        if (l == r) {
            node[idx] = vec[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(idx << 1, l, mid, vec), build(idx << 1 | 1, mid + 1, r, vec);
        node[idx] = node[idx << 1] + node[idx << 1 | 1];
    }
    void apply(int idx) {
        if (ta[idx].empty())
            return;
        ta[idx << 1].apply(ta[idx]);
        ta[idx << 1 | 1].apply(ta[idx]);
        node[idx << 1].apply(ta[idx]);
        node[idx << 1 | 1].apply(ta[idx]);
        ta[idx] = {};
    }
    void modify(int idx, int l, int r, int ql, int qr, const tag &add) {
        if (!add.add && add.Min >= node[idx].M1 && add.Max <= node[idx].m1)
            return;
        if (ql <= l && qr >= r && add.Min > node[idx].M2 && add.Max < node[idx].m2) {
            ta[idx].apply(add);
            node[idx].apply(add);
            return;
        }
        apply(idx);
        int mid = (l + r) >> 1;
        if (ql <= mid)
            modify(idx << 1, l, mid, ql, qr, add);
        if (qr > mid)
            modify(idx << 1 | 1, mid + 1, r, ql, qr, add);
        node[idx] = node[idx << 1] + node[idx << 1 | 1];
    }
    info query(int idx, int l, int r, int ql, int qr) {
        if (ql <= l && qr >= r)
            return node[idx];
        apply(idx);
        int mid = (l + r) >> 1;
        if (qr <= mid)
            return query(idx << 1, l, mid, ql, qr);
        else if (ql > mid)
            return query(idx << 1 | 1, mid + 1, r, ql, qr);
        else
            return query(idx << 1, l, mid, ql, qr) + query(idx << 1 | 1, mid + 1, r, ql, qr);
    }

public:
    LSGT(const int size) : node(size << 2), ta(size << 2), siz(size) {
        build(1, 1, siz);
    }
    template <typename T>
    LSGT(const std::vector<T> &vec) : node(vec.size() << 2), ta(vec.size() << 2), siz(vec.size() - 1) {
        build(1, 1, siz, vec);
    }
    void modify(int ql, int qr, const tag &add) {
        modify(1, 1, siz, ql, qr, add);
    }
    info query(int ql, int qr) {
        return query(1, 1, siz, ql, qr);
    }
};

void solve() {
    int n, m;
    cin >> n;
    vector<int> arr(n + 1);
    for (int i = 1; i <= n; i++) cin >> arr[i];
    LSGT tr(arr);
    cin >> m;
    while (m--) {
        int op;
        cin >> op;
        int l, r;
        cin >> l >> r;
        if (op == 1) {
            int x;
            cin >> x;
            // 区间加 x
            tr.modify(l, r, {x});
        } else if (op == 2) {
            int x;
            cin >> x;
            // 区间取max(x,a[i])
            tr.modify(l, r, {0, INF, x});
        } else if (op == 3) {
            int x;
            cin >> x;
            // 区间取min(x,a[i])
            tr.modify(l, r, {0, x, -INF});
        } else if (op == 4) {
            // 区间求和
            cout << tr.query(l, r).sum << '\n';
        } else if (op == 5) {
            // 区间最大值
            cout << tr.query(l, r).M1 << '\n';
        } else if (op == 6) {
            // 区间最小值
            cout << tr.query(l, r).m1 << '\n';
        }
    }
}

signed main() {
#ifdef LOCAL
    clock_t tttttttt = clock();
    freopen("in.txt", "r", stdin);
#endif
#ifndef LOCAL
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#endif
    //*****************************************************************
    int t = 1;
    // cin >> t;
    while (t--) solve();
//*****************************************************************
#ifdef LOCAL
    cerr << "Time Used: " << fixed << setprecision(3) << (clock() - tttttttt) / (CLOCKS_PER_SEC / 1000.0) << " ms" << endl;
#endif
    return 0;
}

在线静态区间mex

#include <bits/stdc++.h>

using namespace std;
const int N = 200005;

int tot = 0;
struct node {
    int ls, rs;
    int v;
} seg[N * 24];
int rt[N], a[N];
int n, m;

void pushup(int k)
{
    seg[k].v = min(seg[seg[k].ls].v, seg[seg[k].rs].v);
}
int modify(int old, int l, int r, int pos, int v)
{
    int p = ++tot;
    seg[p] = seg[old];
    if (l == r)
    {
        seg[p].v = v;
        return p;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid)
        seg[p].ls = modify(seg[old].ls, l, mid, pos, v);
    else
        seg[p].rs = modify(seg[old].rs, mid + 1, r, pos, v);
    pushup(p);
    return p;
}
int query(int p, int l, int r, int pos)
{
    if (l == r)
    {
        return l;
    }
    int mid = (l + r) >> 1;
    if (seg[seg[p].ls].v < pos)
        return query(seg[p].ls, l, mid, pos);
    else
        return query(seg[p].rs, mid + 1, r, pos);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        rt[i] = modify(rt[i - 1], 0, n, a[i], i);
    }
    while (m--)
    {
        int l, r;
        cin >> l >> r;
        cout << query(rt[r], 0, n, l) << '\n';
    }
}

单点修改区间颜色数:容易证明 k维莫队，块大小取 $\frac{n}{m^\frac{1}{k}}$ 时时间复杂度最优。

#include <bits/stdc++.h>
using namespace std;
const int N = 133334;
struct Modify {
    int pos, x; // a[pos] -> x
} M[N];
struct Query {
    int l, r, t, idx;
};
char opt;
vector<Query> Q;
int n, m, q, t, l, r, a[N];
int cur, ans[N], cnt[1000010];
inline void optimizeIO(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
}
inline void init(void) {
    const int B = n / pow(m, 1.0 / 3);
    sort(Q.begin(), Q.end(), [=](Query &x, Query &y) {
        if (x.l / B != y.l / B) return x.l < y.l;
        if (x.r / B != y.r / B) return x.r < y.r;
        return (x.r / B) & 1 ? x.t < y.t : x.t > y.t;
    });
}
inline void add(int val) {
    if (cnt[val]++ == 0) ++cur;
}
inline void del(int val) {
    if (--cnt[val] == 0) --cur;
}
inline void upd(int t, int l, int r) { // 维护由于时间造成的变化
    if (l <= M[t].pos && M[t].pos <= r) {
        del(a[M[t].pos]), add(M[t].x);
    }
    // 这是一个很巧妙的操作。
    // 由于做完这次操作之后，再一次做这个操作一定是相反的操作，
    // 所以可以直接交换当前位置的值和操作更改后的值。
    swap(a[M[t].pos], M[t].x); 
}
inline void MoAlgo(void) {
    int l = 1, r = 0, t = 0; // 当前状态
    for (int i = 0; i < q; i++) {
        while (Q[i].l < l) add(a[--l]);
        while (r < Q[i].r) add(a[++r]);
        while (l < Q[i].l) del(a[l++]);
        while (Q[i].r < r) del(a[r--]);
        while (t < Q[i].t) upd(++t, l, r);
        while (Q[i].t < t) upd(t--, l, r);
        ans[Q[i].idx] = cur;
    }
}
int main(int argc, char const *argv[]) {
    optimizeIO(), cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    // q -> 询问的个数，等于 Q.size()
    // t -> 当前时间戳
    for (int i = 1; i <= m; i++) {
        cin >> opt >> l >> r;
        if (opt == 'R') M[++t] = {l, r};
        else Q.push_back({l, r, t, ++q});
    }
    init(), MoAlgo();
    for (int i = 1; i <= q; i++) {
        cout << ans[i] << '\n';
    }
    return 0;
}

dx实现

// 带修莫队 O(n^(5/3))
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;

const int N = 1000005;
int n, m, B, mq, mr, a[N];
int sum, cnt[N], ans[N];
struct Q {  // 询问
    int l, r, id, tim;
    // 按l/B、r/B和tim排序
    bool operator<(Q &b) {
        if (l / B != b.l / B)
            return l < b.l;
        if (r / B != b.r / B)
            return r < b.r;
        return tim < b.tim;
    }
} q[N];
struct R {  // 替换
    int p, c;
} R[N];

void add(int x) {
    if (!cnt[x])
        sum++;  // x第一次则累计
    cnt[x]++;   // x出现次数
}
void del(int x) {
    cnt[x]--;
    if (!cnt[x])
        sum--;
}
int main() {
    scanf("%d%d", &n, &m);
    B = pow(n, 0.66);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= m; i++) {  // 操作
        char c[2];
        int l, r;
        scanf("%s%d%d", c, &l, &r);
        if (c[0] == 'Q')
            q[++mq] = {l, r, mq, mr};
        else
            R[++mr] = {l, r};
    }
    sort(q + 1, q + 1 + mq);
    for (int i = 1, l = 1, r = 0, x = 0; i <= mq; i++) {
        while (l > q[i].l) add(a[--l]);  // 左扩展
        while (r < q[i].r) add(a[++r]);  // 右扩展
        while (l < q[i].l) del(a[l++]);  // 左删除
        while (r > q[i].r) del(a[r--]);  // 右删除
        while (x < q[i].tim) {           // 时间戳变大，替换
            int p = R[++x].p;
            // 位置p介于[l,r]，先删旧数，后加新数
            if (l <= p && p <= r)
                del(a[p]), add(R[x].c);
            swap(a[p], R[x].c);  // 交换a,R的对应数
        }
        while (x > q[i].tim) {  // 时间戳变小，还原
            int p = R[x].p;
            if (l <= p && p <= r)
                del(a[p]), add(R[x].c);
            swap(a[p], R[x--].c);
        }
        ans[q[i].id] = sum;
    }
    for (int i = 1; i <= mq; i++) printf("%d\n", ans[i]);
}

区间修改区间颜色数

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
using ll = long long;
int n, QT, a[N], qt, rq, pr[N], mp[N], mt;
struct Q {
    int l, r, d, p;
} q[N * 6], q2[N * 6];
struct odt {
    int l, r;
    mutable int d;
    bool operator<(const odt &z)
        const { return l < z.l; }
};
struct rag {
    int l, r;
    bool operator<(const rag &z)
        const { return r < z.r; }
};
void addp(int x, int d) { q[++rq] = {pr[x], x, d}; }
void cgpr(int x, int y) {
    if (pr[x] != y)
        addp(x, -1), pr[x] = y, addp(x, 1);
}
struct RGdt : set<rag> {
    void add(int l, int r) {
        auto it = lower_bound({0, r});
        if (it != end())
            cgpr(it->l, r);
        if (it != begin())
            --it, cgpr(l, it->r);
        else
            cgpr(l, 0);
        insert({l, r});
    }
    void del(int l, int r) {
        erase({l, r});
        auto it = lower_bound({0, r});
        if (it != end()) {
            if (it != begin()) {
                auto at = it;
                --at;
                cgpr(it->l, at->r);
            } else
                cgpr(it->l, 0);
        }
    }
} lt[N];
struct Odt : set<odt> {
    set<odt>::iterator split(int r) {
        if (r > n)
            return end();
        auto it = lower_bound({r});
        if (it != end() && it->l == r)
            return it;
        --it;
        int L = it->l, R = it->r, D = it->d;
        lt[D].erase({L, R}), lt[D].insert({L, r - 1});
        lt[D].insert({r, R});
        erase(it), insert({L, r - 1, D});
        auto res = insert({r, R, D}).first;
        return res;
    }
} ADT;
ll ct[N], ans[N];
void solve(int l, int r) {
    if (l >= r)
        return;
    int i, x, y, md = l + r >> 1;
    solve(l, md), solve(md + 1, r);
    for (x = md + 1, y = l; x <= r; ++x) {
        while (y <= md && q[y].l <= q[x].l) {
            if (!q[y].p)
                for (i = q[y].r; i <= n; i += i & -i) ct[i] += q[y].d;
            ++y;
        }
        if (q[x].p)
            for (i = q[x].r; i; i -= i & -i) ans[q[x].p] += q[x].d * ct[i];
    }
    for (x = l; x < y; ++x)
        if (!q[x].p)
            for (i = q[x].r; i <= n; i += i & -i) ct[i] -= q[x].d;
    merge(q + l, q + md + 1, q + md + 1, q + r + 1, q2 + l, [&](Q x, Q y) {
        return x.l < y.l;
    });
    for (i = l; i <= r; ++i) q[i] = q2[i];
}
int main() {
    ios::sync_with_stdio(false);
    int i, j, A, l, r, d, qi;
    cin >> n >> QT;
    for (i = 1; i <= n; ++i) cin >> a[i], mp[++mt] = a[i];
    for (qi = 1; qi <= QT; ++qi) {
        cin >> q2[qi].p >> q2[qi].l >> q2[qi].r;
        if (q2[qi].p == 1) {
            cin >> q2[qi].d;
            mp[++mt] = q2[qi].d;
        }
    }
    sort(mp + 1, mp + mt + 1), unique(mp + 1, mp + mt + 1) - mp - 1;
    for (i = 1; i <= n; ++i) a[i] = lower_bound(mp + 1, mp + mt + 1, a[i]) - mp;
    for (qi = 1; qi <= QT; ++qi)
        if (q2[qi].p == 1)
            q2[qi].d = lower_bound(mp + 1, mp + mt + 1, q2[qi].d) - mp;
    for (i = 1; i <= n; ++i) {
        ADT.insert({i, i, a[i]});
        if (lt[a[i]].size()) {
            auto it = lt[a[i]].end();
            --it;
            pr[i] = it->r;
        }
        lt[a[i]].insert({i, i});
        addp(i, 1);
    }
    for (qi = 1; qi <= QT; ++qi) {
        A = q2[qi].p, l = q2[qi].l, r = q2[qi].r, d = q2[qi].d;
        if (A == 1) {
            auto R = ADT.split(r + 1), L = ADT.split(l);
            auto it = L;
            lt[it->d].del(it->l, it->r);
            for (++it; it != R; ++it) cgpr(it->l, it->l - 1), lt[it->d].del(it->l, it->r);
            ADT.erase(L, R);
            ADT.insert({l, r, d});
            lt[d].add(l, r);
        } else {
            ++qt, q[++rq] = {l - 1, r, 1, qt};
            q[++rq] = {l - 1, l - 1, -1, qt};
        }
    }
    solve(1, rq);
    for (i = 1; i <= qt; ++i)
        printf("%lld\n", ans[i]);
    return 0;
}

给你一个数组 $\{a_i\}$ 支持两种操作：

1、查询区间 $[l,r]$ 中每个数字出现次数的mex。

2、单点修改某一个位置的值。

mex指的是一些数字中最小的未出现的自然数。值得注意的是，因为 $\{a_i\}$ 是正整数，所以 $0$ 的出现次数为 $0$ ，即操作 $1$ 的答案不会是 $0$ 。

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

struct Query {
    int l, r, t, id;
};

struct Change {
    int pos, v;
};

const int MAXN = 100000 * 2 + 5;

Query q[MAXN];
Change c[MAXN];
int v[MAXN], cnt[MAXN], tot[MAXN], ans[MAXN], a[MAXN];
int cntQ, cntC;
int n, m, t, siz, mex = 1;

bool cmp(Query& a, Query& b) {
    if(a.l / t != b.l / t) {
        return a.l < b.l;
    }
    if(a.r / t != b.r / t) {
        return a.r < b.r;
    }
    return a.t < b.t;
}

void add(int x) {
    tot[cnt[x]]--;
    if(tot[cnt[x]] == 0) {
        mex = min(mex, cnt[x]);
    }
    cnt[x]++;
    tot[cnt[x]]++;
    if(tot[cnt[x]] == 1 && mex == cnt[x]) {
        for(int i = mex; i <= siz; i++) {
            if(tot[i + 1] == 0) {
                mex = i + 1;
                break;
            }
        }
    }
}

void del(int x) {
    tot[cnt[x]]--;
    if(tot[cnt[x]] == 0) {
        mex = min(mex, cnt[x]);
    }
    cnt[x]--;
    tot[cnt[x]]++;
    if(tot[cnt[x]] == 1 && mex == cnt[x]) {
        for(int i = mex; i <= siz; i++) {
            if(tot[i + 1] == 0) {
                mex = i + 1;
                break;
            }
        }
    }
}

void modify(int i, int t) {
    if(q[i].l <= c[t].pos && c[t].pos <= q[i].r) {
        del(a[c[t].pos]);
        add(c[t].v);
    }
    swap(a[c[t].pos], c[t].v);
}

int main() {
    scanf("%d%d", &n, &m);
    t = pow(n, 2.0 / 3);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        v[++siz] = a[i];
    }
    for(int i = 1; i <= m; i++) {
        int op;

        scanf("%d", &op);
        if(op == 1) {
            cntQ++;
            scanf("%d%d", &q[cntQ].l, &q[cntQ].r);
            q[cntQ].t = cntC;
            q[cntQ].id = cntQ;
        } else {
            cntC++;
            scanf("%d%d", &c[cntC].pos, &c[cntC].v);
            v[++siz] = c[cntC].v;
        }
    }
    sort(v + 1, v + siz + 1);
    siz = unique(v + 1, v + siz + 1) - (v + 1);
    for(int i = 1; i <= n; i++) {
        a[i] = lower_bound(v + 1, v + siz + 1, a[i]) - v;
    }
    for(int i = 1; i <= cntC; i++) {
        c[i].v = lower_bound(v + 1, v + siz + 1, c[i].v) - v;
    }
    sort(q + 1, q + cntQ + 1, cmp);
    int l = 1, r = 0, t = 0;
    for(int i = 1; i <= cntQ; i++) {
        while(l > q[i].l) add(a[--l]);
        while(r < q[i].r) add(a[++r]);
        while(l < q[i].l) del(a[l++]);
        while(r > q[i].r) del(a[r--]);
        while(t < q[i].t) modify(i, ++t);
        while(t > q[i].t) modify(i, t--);
        ans[q[i].id] = mex;
    }
    for(int i = 1; i <= cntQ; i++) {
        printf("%d\n", ans[i]);
    }

    return 0;
}

莫队：小z的袜子(区间内选到相同颜色的数的概率)

// 普通莫队 O(n*sqrt(n))
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;

const int N = 50005;
int n, m, B, a[N];
int sum, cnt[N], ans1[N], ans2[N];
struct Q {
    int l, r, id;
    // 按l所在块的编号l/B和r排序
    bool operator<(const Q &x) const {
        if (l / B != x.l / B)
            return l < x.l;
        if ((l / B) & 1)
            return r < x.r;
        return r > x.r;
    }
} q[N];

void add(int x) {
    sum += cnt[x];  // 当前x与前面每个x组合成双
    cnt[x]++;       // x的出现次数
}
void del(int x) {
    cnt[x]--;
    sum -= cnt[x];
}
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
int main() {
    scanf("%d%d", &n, &m);
    B = sqrt(n);                  // 块的大小
    for (int i = 1; i <= n; i++)  // 颜色
        scanf("%d", &a[i]);
    for (int i = 1; i <= m; i++)  // 询问
        scanf("%d%d", &q[i].l, &q[i].r), q[i].id = i;
    sort(q + 1, q + m + 1);
    for (int i = 1, l = 1, r = 0; i <= m; i++) {
        if (q[i].l == q[i].r) {
            ans1[q[i].id] = 0, ans2[q[i].id] = 1;
            continue;
        }
        while (l > q[i].l) l--, add(a[l]);  // 左扩展
        while (r < q[i].r) r++, add(a[r]);  // 右扩展
        while (l < q[i].l) del(a[l]), l++;  // 左删除
        while (r > q[i].r) del(a[r]), r--;  // 右删除
        ans1[q[i].id] = sum;
        ans2[q[i].id] = 1ll * (r - l + 1) * (r - l) / 2;
    }
    for (int i = 1; i <= m; i++) {
        if (ans1[i]) {
            int g = gcd(ans1[i], ans2[i]);
            ans1[i] /= g, ans2[i] /= g;  // 最简分数
        } else
            ans2[i] = 1;
        printf("%d/%d\n", ans1[i], ans2[i]);
    }
}

李超线段树

// 李超线段树 O(nlognlogn)
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;

const double eps = 1e-9;
const int N = 100005;
#define M1 39989
#define M2 1000000000
#define ls u << 1
#define rs u << 1 | 1
typedef pair<double, int> pdi;
int n, cnt, lastans;
struct line {
    double k, b;  // 斜率,截距
} p[N];
int tr[N << 2];  // 线段编号

int cmp(double a, double b) {  // 比a,b
    if (a - b > eps)
        return 1;
    if (b - a > eps)
        return -1;
    return 0;
}
double Y(int id, int x) {  // 求Y值
    return p[id].k * x + p[id].b;
}
void change(int u, int l, int r, int L, int R, int id) {  // 修改
    int mid = (l + r) >> 1;
    if (L <= l && r <= R) {
        int cm = cmp(Y(id, mid), Y(tr[u], mid));
        if (cm == 1 || (!cm && id < tr[u]))
            swap(id, tr[u]);
        int cl = cmp(Y(id, l), Y(tr[u], l));
        if (cl == 1 || (!cl && id < tr[u]))
            change(ls, l, mid, L, R, id);
        int cr = cmp(Y(id, r), Y(tr[u], r));
        if (cr == 1 || (!cr && id < tr[u]))
            change(rs, mid + 1, r, L, R, id);
        return;
    }
    if (L <= mid)
        change(ls, l, mid, L, R, id);
    if (mid < R)
        change(rs, mid + 1, r, L, R, id);
}
pdi pmax(pdi a, pdi b) {  // Y值大且编号小
    if (cmp(a.first, b.first) == 1)
        return a;
    else if (cmp(a.first, b.first) == -1)
        return b;
    else
        return a.second < b.second ? a : b;
}
pdi query(int u, int l, int r, int x) {  // 查询
    if (l == r)
        return {Y(tr[u], x), tr[u]};
    int mid = (l + r) >> 1;
    pdi t = {Y(tr[u], x), tr[u]};
    if (x <= mid)
        return pmax(t, query(ls, l, mid, x));
    else
        return pmax(t, query(rs, mid + 1, r, x));
}
int main() {
    int op, x0, y0, x1, y1, x;
    double k, b;
    scanf("%d", &n);
    while (n--) {
        scanf("%d", &op);
        if (op == 1) {  // 插入一条线段
            scanf("%d%d%d%d", &x0, &y0, &x1, &y1);
            x0 = (x0 + lastans - 1) % M1 + 1,
            x1 = (x1 + lastans - 1) % M1 + 1;
            y0 = (y0 + lastans - 1) % M2 + 1,
            y1 = (y1 + lastans - 1) % M2 + 1;
            if (x0 > x1)
                swap(x0, x1), swap(y0, y1);
            if (x0 == x1)
                k = 0, b = max(y0, y1);
            else
                k = 1.0 * (y1 - y0) / (x1 - x0), b = y0 - k * x0;
            p[++cnt] = {k, b};
            change(1, 1, M1, x0, x1, cnt);
        } else {
            scanf("%d", &x);  // 查询最大值
            x = (x + lastans - 1) % M1 + 1;
            lastans = query(1, 1, M1, x).second;
            printf("%d\n", lastans);
        }
    }
}

李超树dp

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;

#define ll long long
#define ls u << 1
#define rs u << 1 | 1
const int N = 100005, M = 1000005;

ll h[N], s[N], k[N], b[N], f[N];
int n, tr[M << 2];  // 优势线段的编号

ll Y(int id, int x) {  // 求Y值
    return k[id] * x + b[id];
}
void change(int u, int l, int r, int id) {  // 修改
    int mid = l + r >> 1;
    if (Y(id, mid) < Y(tr[u], mid))
        swap(id, tr[u]);
    if (Y(id, l) < Y(tr[u], l))
        change(ls, l, mid, id);
    if (Y(id, r) < Y(tr[u], r))
        change(rs, mid + 1, r, id);
}
ll query(int u, int l, int r, int x) {  // 查询
    if (l == r)
        return Y(tr[u], x);
    int mid = l + r >> 1;
    ll ans = Y(tr[u], x);
    if (x <= mid)
        return min(ans, query(ls, l, mid, x));
    else
        return min(ans, query(rs, mid + 1, r, x));
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%lld", h + i);
    for (int i = 1; i <= n; ++i) scanf("%lld", s + i), s[i] += s[i - 1];
    k[0] = 0, b[0] = 1e18;  // 第0条线段
    k[1] = -2 * h[1];
    b[1] = h[1] * h[1] - s[1];
    change(1, 1, M, 1);  // 插入第一条线段
    for (int i = 2; i <= n; ++i) {
        f[i] = h[i] * h[i] + s[i - 1] + query(1, 1, M, h[i]);
        k[i] = -2 * h[i];
        b[i] = f[i] + h[i] * h[i] - s[i];
        change(1, 1, M, i);
    }
    printf("%lld", f[n]);
}

普通斜率优化

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;
const int N = 500010;
int n,m,q[N];
LL s[N],f[N];

LL dy(int i,int j){return f[i]+s[i]*s[i]-f[j]-s[j]*s[j];}
LL dx(int i,int j){return s[i]-s[j];}
int main(){
  while(~scanf("%d%d",&n,&m)){
    for(int i=1;i<=n;i++)scanf("%lld",&s[i]),s[i]+=s[i-1];

    int h=1,t=0;
    for(int i=1;i<=n;i++){
      while(h<t && dy(i-1,q[t])*dx(q[t],q[t-1])
                 <=dx(i-1,q[t])*dy(q[t],q[t-1])) t--;
      q[++t]=i-1;      
      while(h<t && dy(q[h+1],q[h])
                 <=dx(q[h+1],q[h])*2*s[i]) h++;
      int j=q[h];
      f[i]=f[j]+(s[i]-s[j])*(s[i]-s[j])+m;
    }
    printf("%lld\n",f[n]);
  }
}

单点修改，权值线段树合并

struct SegmentTree {
#define mid ((l + r) >> 1)
    struct TREE {
        int l, r;
        int cnt;
    } tr[N * 20];  /// 2nlogn
    int tot;
    void push_up(int cur) {
        tr[cur].cnt = tr[tr[cur].l].cnt + tr[tr[cur].r].cnt;
    }
    void change(int &cur, int l, int r, int pos, int x) {
        if (!cur)
            cur = ++tot;
        if (l == r) {
            tr[cur].cnt = 1;
            return;
        }
        if (pos <= mid)
            change(tr[cur].l, l, mid, pos, x);
        else
            change(tr[cur].r, mid + 1, r, pos, x);
        push_up(cur);
    }
    int merge(int a, int b, int l, int r) {
        if (!a || !b)
            return a | b;
        if (l == r)
            return tr[a].cnt ? a : b;
        int cur = ++tot;
        tr[cur].l = merge(tr[a].l, tr[b].l, l, mid);
        tr[cur].r = merge(tr[a].r, tr[b].r, mid + 1, r);
        push_up(cur);
        return cur;
    }
    int query(int cur, int l, int r, int ql, int qr) {
        if (!cur || ql < l || qr > r || ql > qr)
            return 0;
        if (l == ql && r == qr)
            return tr[cur].cnt;
        if (qr <= mid)
            return query(tr[cur].l, l, mid, ql, qr);
        else if (ql > mid)
            return query(tr[cur].r, mid + 1, r, ql, qr);
        return query(tr[cur].l, l, mid, ql, mid) + query(tr[cur].r, mid + 1, r, mid + 1, qr);
    }
} seg;

楼房重建

// 线段树+递归合并 nlognlogn
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;

const int N = 100005;
#define ls u << 1
#define rs u << 1 | 1
#define mid ((l + r) >> 1)
double mx[N << 2];
int sum[N << 2];
// mx:区间最大斜率, sum:区间可见楼房数

int dfs(int u, int l, int r, double mls) {  // 求右分支sum
    if (mx[u] <= mls)
        return 0;  // 剪枝
    if (l == r)
        return mx[u] > mls;  // 叶子
    if (mx[ls] <= mls)
        return dfs(rs, mid + 1, r, mls);
    else
        return dfs(ls, l, mid, mls) + sum[u] - sum[ls];
}
void pushup(int u, int l, int r) {  // 上传
    mx[u] = max(mx[ls], mx[rs]);
    sum[u] = sum[ls] + dfs(rs, mid + 1, r, mx[ls]);
}
void change(int u, int l, int r, int x, double v) {  // 点修
    if (l == r) {
        mx[u] = v;
        sum[u] = 1;
        return;
    }
    if (x <= mid)
        change(ls, l, mid, x, v);
    else
        change(rs, mid + 1, r, x, v);
    pushup(u, l, r);
}
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        change(1, 1, n, x, (double)y / x);
        printf("%d\n", sum[1]);
    }
}

势能线段树：区间开方

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;

const int N = 100005;
#define LL long long
#define ls u << 1
#define rs u << 1 | 1
#define mid ((l + r) >> 1)
LL a[N];
LL sum[N << 2], mx[N << 2];
// sum:区间和，mx:区间最大

void pushup(int u) {  // 上传
    sum[u] = sum[ls] + sum[rs];
    mx[u] = max(mx[ls], mx[rs]);
}
void build(int u, int l, int r) {  // 建树
    sum[u] = mx[u] = a[l];
    if (l == r)
        return;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    pushup(u);
}
void change(int u, int l, int r, int x, int y) {  // 区修
    if (mx[u] == 1)
        return;  // 优化
    if (l == r) {
        sum[u] = sqrt(sum[u]);
        mx[u] = sqrt(mx[u]);
        return;
    }
    if (x <= mid)
        change(ls, l, mid, x, y);
    if (y > mid)
        change(rs, mid + 1, r, x, y);
    pushup(u);
}
LL query(int u, int l, int r, int x, int y) {  // 区查
    if (x <= l && r <= y)
        return sum[u];
    LL s = 0;
    if (x <= mid)
        s += query(ls, l, mid, x, y);
    if (y > mid)
        s += query(rs, mid + 1, r, x, y);
    return s;
}
int main() {
    int n, m, opt, l, r;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
    build(1, 1, n);
    scanf("%d", &m);
    while (m--) {
        scanf("%d%d%d", &opt, &l, &r);
        if (l > r)
            swap(l, r);
        if (opt == 0)
            change(1, 1, n, l, r);
        else
            printf("%lld\n", query(1, 1, n, l, r));
    }
    return 0;
}

给出一个动态的区间，以及m*m次询问，每次询问给出一段区间 [l,r]，要求出这段区间中最大连续子段和

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

#define ls u << 1
#define rs u << 1 | 1
const int N = 500010;
int n, m, a[N];
struct Tree {  // 线段树
    int l, r;
    // 区间和,最大左子段和,最大右子段和,最大子段和
    int sum, lmx, rmx, mx;
} tr[N * 4];

void pushup(Tree &u, Tree l, Tree r) {
    u.sum = l.sum + r.sum;
    u.lmx = max(l.lmx, l.sum + r.lmx);
    u.rmx = max(r.rmx, r.sum + l.rmx);
    u.mx = max(max(l.mx, r.mx), l.rmx + r.lmx);
}
void build(int u, int l, int r) {  // 建树
    tr[u] = {l, r, a[r], a[r], a[r], a[r]};
    if (l == r)
        return;
    int m = l + r >> 1;
    build(ls, l, m);
    build(rs, m + 1, r);
    pushup(tr[u], tr[ls], tr[rs]);
}
void change(int u, int x, int v) {  // 点修
    if (tr[u].l == tr[u].r) {
        tr[u] = {x, x, v, v, v, v};
        return;
    }
    int m = tr[u].l + tr[u].r >> 1;
    if (x <= m)
        change(ls, x, v);
    else
        change(rs, x, v);
    pushup(tr[u], tr[ls], tr[rs]);
}
Tree query(int u, int x, int y) {  // 区查
    if (x <= tr[u].l && tr[u].r <= y)
        return tr[u];
    int m = tr[u].l + tr[u].r >> 1;
    if (y <= m)
        return query(ls, x, y);
    if (x > m)
        return query(rs, x, y);
    Tree T;  // 开一个临时节点，存储拼凑结果
    pushup(T, query(ls, x, m), query(rs, m + 1, y));
    return T;
}
// Tree query(int u,int x,int y){ //区查
//   if(x>tr[u].r||y<tr[u].l)
//     return {tr[u].l,tr[u].r,0,-1e9,-1e9,-1e9};
//   if(x<=tr[u].l && tr[u].r<=y) return tr[u];
//   Tree T; //开一个临时节点，存储拼凑结果
//   pushup(T,query(ls,x,y),query(rs,x,y));
//   return T;
// }
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    build(1, 1, n);
    while (m--) {
        int k, x, y;
        scanf("%d%d%d", &k, &x, &y);
        if (k == 1) {
            if (x > y)
                swap(x, y);
            printf("%d\n", query(1, x, y).mx);
        } else
            change(1, x, y);
    }
    return 0;
}

0 l r 把 $[l, r]$ 区间内的所有数全变成 $0$ ；
1 l r 把 $[l, r]$ 区间内的所有数全变成 $1$ ；
2 l r 把 $[l,r]$ 区间内的所有数全部取反，也就是说把所有的 $0$ 变成 $1$ ，把所有的 $1$ 变成 $0$ ；
3 l r 询问 $[l, r]$ 区间内总共有多少个 $1$ ；
4 l r 询问 $[l, r]$ 区间内最多有多少个连续的 $1$ 。

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;

#define ls u << 1
#define rs u << 1 | 1
const int N = 100005;
int n, m, a[N];
struct tree {
    int l, r;
    int b, lb, rb, mb, c, lc, rc, mc;
    int len, tag, rev;
} tr[N << 2];
// b:区间1的个数,      c:区间0的个数
// lb:区间左起1的长度, lc:区间左起0的长度
// rb:区间右起1的长度, rc:区间右起0的长度
// mb:区间1的最长长度, mc:区间0的最长长度
// len:区间的长度
// tag:区间赋值标记,无标记:-1,有标记:0或1
// rev:区间取反标记,无标记: 0,有标记:1

void pushup(tree& u, tree l, tree r) {  // 上传
    u.b = l.b + r.b;
    u.lb = l.c ? l.lb : l.b + r.lb;
    u.rb = r.c ? r.rb : r.b + l.rb;
    u.mb = max(max(l.mb, r.mb), l.rb + r.lb);
    u.c = l.c + r.c;
    u.lc = l.b ? l.lc : l.c + r.lc;
    u.rc = r.b ? r.rc : r.c + l.rc;
    u.mc = max(max(l.mc, r.mc), l.rc + r.lc);
}
void pd(int u, int opt) {  // 操作区间
    tree& t = tr[u];
    if (opt == 0) {  // 区间赋值为0
        t.b = t.lb = t.rb = t.mb = 0;
        t.c = t.lc = t.rc = t.mc = t.len;
        t.tag = 0;
        t.rev = 0;
    }
    if (opt == 1) {  // 区间赋值为1
        t.b = t.lb = t.rb = t.mb = t.len;
        t.c = t.lc = t.rc = t.mc = 0;
        t.tag = 1;
        t.rev = 0;
    }
    if (opt == 2) {  // 区间取反
        swap(t.b, t.c);
        swap(t.lb, t.lc);
        swap(t.rb, t.rc);
        swap(t.mb, t.mc);
        t.rev ^= 1;
    }
}
void pushdown(int u) {  // 下传
    tree& t = tr[u];
    if (t.tag == 0)
        pd(ls, 0), pd(rs, 0);
    if (t.tag == 1)
        pd(ls, 1), pd(rs, 1);
    if (t.rev)
        pd(ls, 2), pd(rs, 2);
    t.tag = -1;
    t.rev = 0;
}
void build(int u, int l, int r) {  // 建树
    int t = a[l];
    tr[u] = {l, r, t, t, t, t,
             t ^ 1, t ^ 1, t ^ 1, t ^ 1, r - l + 1, -1, 0};
    if (l == r)
        return;
    int m = l + r >> 1;
    build(ls, l, m);
    build(rs, m + 1, r);
    pushup(tr[u], tr[ls], tr[rs]);
}
void change(int u, int x, int y, int k) {  // 区修
    if (y < tr[u].l || tr[u].r < x)
        return;
    if (x <= tr[u].l && tr[u].r <= y) {
        pd(u, k);
        return;
    }
    pushdown(u);
    change(ls, x, y, k);
    change(rs, x, y, k);
    pushup(tr[u], tr[ls], tr[rs]);
}
tree query(int u, int x, int y) {  // 区查
    if (x > tr[u].r || y < tr[u].l)
        return {};
    if (x <= tr[u].l && tr[u].r <= y)
        return tr[u];
    pushdown(u);
    tree T;  // 开一个临时节点，存储拼凑结果
    pushup(T, query(ls, x, y), query(rs, x, y));
    return T;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    build(1, 1, n);

    for (int i = 1; i <= m; i++) {
        int opt, l, r;
        scanf("%d%d%d", &opt, &l, &r);
        ++l, ++r;
        if (opt < 3)
            change(1, l, r, opt);
        else {
            tree t = query(1, l, r);
            printf("%d\n", opt == 3 ? t.b : t.mb);
        }
    }
    return 0;
}

静态区间第k小

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

#define N 200005
#define lc(x) tr[x].l
#define rc(x) tr[x].r
struct node{
  int l,r,s; //s:节点值域中有多少个数
}tr[N*20];
int root[N],idx;
int n,m,a[N];
vector<int> b;

void build(int &x,int l,int r){
  x=++idx;
  if(l==r) return;
  int m=l+r>>1;
  build(lc(x),l,m);
  build(rc(x),m+1,r);
}
void insert(int x,int &y,int l,int r,int k){
  y=++idx; tr[y]=tr[x]; tr[y].s++;
  if(l==r) return;
  int m=l+r>>1;
  if(k<=m) insert(lc(x),lc(y),l,m,k);
  else insert(rc(x),rc(y),m+1,r,k);
}
int query(int x,int y,int l,int r,int k){
  if(l==r) return l;
  int m=l+r>>1;
  int s=tr[lc(y)].s-tr[lc(x)].s;
  if(k<=s) return query(lc(x),lc(y),l,m,k);
  else return query(rc(x),rc(y),m+1,r,k-s);
}
int main(){
  scanf("%d%d",&n,&m);
  for(int i=1; i<=n; i++){
    scanf("%d",&a[i]); b.push_back(a[i]);
  }
  sort(b.begin(),b.end());
  b.erase(unique(b.begin(),b.end()),b.end());
  int bn=b.size();

  build(root[0],1,bn);
  for(int i=1; i<=n; i++){
    int id=lower_bound(b.begin(),b.end(),a[i])-b.begin()+1;
    insert(root[i-1],root[i],1,bn,id);
  }
  while(m--){
    int l,r,k; scanf("%d%d%d",&l,&r,&k);
    int id=query(root[l-1],root[r],1,bn,k)-1;
    printf("%d\n",b[id]);
  }
  return 0;
}

权值线段树+离散化实现平衡树,需要动态地维护一个可重集合 $M$ ，并且提供以下操作：

向 $M$ 中插入一个数 $x$ 。
从 $M$ 中删除一个数 $x$ （若有多个相同的数，应只删除一个）。
查询 $M$ 中有多少个数比 $x$ 小，并且将得到的答案加一。
查询如果将 $M$ 从小到大排列后，排名位于第 $x$ 位的数。
查询 $M$ 中 $x$ 的前驱（前驱定义为小于 $x$ ，且最大的数）。
查询 $M$ 中 $x$ 的后继（后继定义为大于 $x$ ，且最小的数）。

对于操作 3,5,6，不保证当前可重集中存在数 $x$ 。

// 权值线段树+离散化 nlogn
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;

const int N = 100005;
#define ls u << 1
#define rs u << 1 | 1
#define mid ((l + r) >> 1)
int n, m, id;
int opt[N], a[N], b[N];
// opt:操作序号 a:数x b:备份数组
int sum[N << 2];  // 区间数的出现次数之和

void pushup(int u) {  // 上传
    sum[u] = sum[ls] + sum[rs];
}
void change(int u, int l, int r, int x, int k) {  // 插删即点修
    if (l == r) {
        sum[u] += k;
        return;
    }
    if (x <= mid)
        change(ls, l, mid, x, k);
    else
        change(rs, mid + 1, r, x, k);
    pushup(u);
}
int q_rank(int u, int l, int r, int x, int y) {  // 排名即前缀和
    if (x <= l && r <= y)
        return sum[u];
    int s = 0;
    if (x <= mid)
        s += q_rank(ls, l, mid, x, y);
    if (y > mid)
        s += q_rank(rs, mid + 1, r, x, y);
    return s;
}
int q_num(int u, int l, int r, int x) {  // 排名x的数
    if (l == r)
        return l;
    if (x <= sum[ls])
        return q_num(ls, l, mid, x);
    else
        return q_num(rs, mid + 1, r, x - sum[ls]);
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &opt[i], &a[i]);
        if (opt[i] != 4)
            b[++m] = a[i];  // 备份
    }
    sort(b + 1, b + m + 1);                // 排序
    m = unique(b + 1, b + 1 + m) - b - 1;  // 去重
    for (int i = 1; i <= n; i++) {
        if (opt[i] != 4)
            id = lower_bound(b + 1, b + m + 1, a[i]) - b;
        if (opt[i] == 1)
            change(1, 1, m, id, 1);  // 插入x
        if (opt[i] == 2)
            change(1, 1, m, id, -1);  // 删除x
        if (opt[i] == 3)              // x的排名
            printf("%d\n", id > 1 ? q_rank(1, 1, m, 1, id - 1) + 1 : 1);
        if (opt[i] == 4)  // 排名为x的数
            printf("%d\n", b[q_num(1, 1, m, a[i])]);
        if (opt[i] == 5) {  // x的前驱
            int rk = q_rank(1, 1, m, 1, id - 1);
            printf("%d\n", b[q_num(1, 1, m, rk)]);
        }
        if (opt[i] == 6) {  // x的后继
            int rk = q_rank(1, 1, m, 1, id) + 1;
            printf("%d\n", b[q_num(1, 1, m, rk)]);
        }
    }
}

动态区间第k小

给定一个含有 $n$ 个数的序列 $a_1,a_2 \dots a_n$ ，需要支持两种操作：

Q l r k 表示查询下标在区间 $[l,r]$ 中的第 $k$ 小的数
C x y 表示将 $a_x$ 改为 $y$

// 整体二分+树状数组 O(nlognlogV)
#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

const int N = 300005;
#define lowbit(x) (x & -x)
int n, m, a[N], ans[N];

struct Q {
    // 查询: [x,y]第k小，id编号，opt=1
    // 原数: x位置，y值，opt=0
    int x, y, k, id, opt;
};
vector<Q> q;  // 数据序列

struct BIT {
    vector<int> s;
    void init(int n) { s.resize(n); }
    void add(int x, int k) {
        while (x <= n) s[x] += k, x += lowbit(x);
    }
    int sum(int x) {
        int t = 0;
        while (x) t += s[x], x -= lowbit(x);
        return t;
    }
    int sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }
} tree;  // 树状数组

void solve(vector<Q> q, int L, int R) {
    if (!q.size())
        return;
    if (L == R) {
        for (auto i : q)
            if (i.opt)
                ans[i.id] = L;
        return;
    }
    int mid = L + R >> 1;
    vector<Q> q1, q2;
    for (auto i : q) {
        if (!i.opt) {  // 若是原数，按值分流
            if (i.y <= mid)
                tree.add(i.x, i.k),   // 加入贡献
                    q1.push_back(i);  // 分流到左边
            else
                q2.push_back(i);  // 分流到右边
        } else {                  // 若是查询，按个数分流
            int s = tree.sum(i.x, i.y);
            if (s >= i.k)
                q1.push_back(i);  // 分流到左边
            else
                i.k -= s, q2.push_back(i);  // 分流到右边
        }
    }
    for (auto i : q1)
        if (!i.opt)
            tree.add(i.x, -i.k);  // 减去贡献
    solve(q1, L, mid);
    solve(q2, mid + 1, R);  // 分治
}
int main() {
    scanf("%d%d", &n, &m);
    char ch[2];
    int x, y, k;
    tree.init(n + 1);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]), q.push_back({i, a[i], 1, 0, 0});
    for (int i = 1; i <= m; i++) {
        scanf("%s%d%d", ch, &x, &y);
        if (ch[0] == 'C')
            q.push_back({x, a[x], -1, 0, 0}),         // 旧数贡献-1
                q.push_back({x, a[x] = y, 1, 0, 0});  // 新数贡献+1
        else
            scanf("%d", &k), q.push_back({x, y, k, i, 1});
    }
    memset(ans, -1, sizeof ans);
    solve(q, 0, 1e9);  // 整体二分
    for (int i = 1; i <= m; i++)
        if (~ans[i])
            printf("%d\n", ans[i]);
}

线段树优化建图

const int MAXN = 5e5 + 5;
const int D = 5e5;
const int INF = 0x3f3f3f3f3f3f3f3fll;
int n, m, s;
int id[MAXN];
int dis[MAXN << 1];
vector<pair<int, int>> g[MAXN << 1];
void build(int x, int l, int r) {
  if (l == r) {
    id[l] = x;
    return;
  }
  int mid = l + r >> 1;
  g[x].push_back({x << 1, 0});
  g[x].push_back({x << 1 | 1, 0});
  g[(x << 1) + D].push_back({x + D, 0});
  g[(x << 1 | 1) + D].push_back({x + D, 0});
  build(x << 1, l, mid);
  build(x << 1 | 1, mid + 1, r);
}
void add(int x, int l, int r, int L, int R, int v, int w, int op) {
  if (L <= l && r <= R) {
    if (op)
      g[v].push_back({x, w});
    else
      g[x + D].push_back({v, w});
    return;
  }
  int mid = l + r >> 1;
  if (L <= mid) add(x << 1, l, mid, L, R, v, w, op);
  if (R > mid) add(x << 1 | 1, mid + 1, r, L, R, v, w, op);
}
void dijkstra(int s) {
  vector<int> vis(MAXN * 2, 0);
  priority_queue<pair<int, int>> q;
  memset(dis, INF, sizeof(dis));
  dis[s] = 0;
  q.push({0, s});
  while (!q.empty()) {
    int x = q.top().second;
    q.pop();
    if (vis[x]) continue;
    vis[x] = 1;
    for (auto [y, w] : g[x]) {
      dis[y] = min(dis[y], dis[x] + w);
      q.push({-dis[y], y});
    }
  }
}
// op 1 : v->u 单向边
// op 2 : v->[l,r]
// op 3 :[l,r]-> v
void solve() {
  cin >> n >> m >> s;
  build(1, 1, n);
  for (int i = 1; i <= n; i++) {
    int x = id[i];
    g[x].push_back({x + D, 0});
    g[x + D].push_back({x, 0});
  }
  while (m--) {
    int op;
    cin >> op;
    if (op == 1) {
      int v, u, w;
      cin >> v >> u >> w;
      g[id[v]].push_back({id[u], w});
    } else if (op == 2) {
      int v, l, r, w;
      cin >> v >> l >> r >> w;
      add(1, 1, n, l, r, id[v], w, 1);
    } else {
      int v, l, r, w;
      cin >> v >> l >> r >> w;
      add(1, 1, n, l, r, id[v], w, 0);
    }
  }
  dijkstra(id[s]);
  for (int i = 1; i <= n; i++) {
    if (dis[id[i]] == INF)
      cout << "-1 ";
    else
      cout << dis[id[i]] << ' ';
  }
}