数据结构入门

_Yuigahama_Yui · 2025-11-29 21:14:22 · 算法·理论

前前言

谨以此文纪念我失败的 OI 之路。

槲寄生下，天鹅湖旁。

OI，就算没有「虫」，我们仍能相爱吧？

——没关系的，我们就算没有「虫」也一定可以的。

“约好了哦？”

本文旨在提供经典例题，或介绍 trick，所以有些地方会放笔者认为比自己讲的好的视频/博客上来绝对不是因为我懒不想码字。同时省去了大家找文章和阅判断写得好不好的时间。

2025.11.29 ： 开坑。不知道能不能写完。新手向（？毕竟我很菜。大概会从头开始写。

例题应该给够了罢。

upd on 2025.11.30：因为大号没了，小号这些题又没交，所以 code 丢了。找代码的时候贺了几篇题解突然意识到好像会被封。。。

upd on 2025.12.1：已经把非模板的代码折叠起来。观感瞬间提升。感谢锣鼓。

upd on 2025.12.7：虽然还有很大一部分没有更完，但是笔者认为在 noip 里基本是够用了。

upd on 2025.12.14：删除了除模板外洛谷上能看到题面的题的题面。

勘误请私信。

前言

数据结构（data structure）又被称为 DS，顾名思义，是用于处理数据的工具。对于不同的维护目的，使用不同的数据结构可以批量处理数据，大大提升效率，以达到时限需求。

树状数组

很好用的数据结构。短小精悍。

但是我对她研究不多，没什么理解。像什么树状数组动态开点，树状数组上二分什么的都不甚了解。写题的时候除非必须用树状数组都用线段树代掉了。

所以我没什么好写的，就算写出来估计也和别人写的差不多。

这是一个很爱树状数组的人写的博客 我觉得写的很好。

线段树

众多数据结构中，我最先真正理解的是线段树。

引入

相信大家都有过求区间和的需求。此时我们可以用前缀和等手法求解。但是对比一下时间复杂度，前缀和需要 \mathcal{O}(n) 时间预处理，\mathcal{O}(1) 查询；而暴力需要 \mathcal{O}(n) 查询。这十分地不均衡，而且在存在修改操作时，前缀和不好维护。

于是线段树诞生了。她（确信 以 \mathcal{O}(n \log n) 时间建树，\mathcal{O}(n \log n) 时间修改和查询，但是代价是 4 倍的空间和常数（除 zkw?）。这是经典的以空间换时间。

介绍

先拉一道题过来。P3372 【模板】线段树 1

题目描述

如题，已知一个数列 \{a_i\}，你需要进行下面两种操作：

1. 将某区间每一个数加上 k。
2. 求出某区间每一个数的和。

对于 100\% 的数据：1 \le n, m \le {10}^5，a_i,k 为正数，且任意时刻数列的和不超过 2\times 10^{18}。

最原始的区间加区间求和。如果暴力必定会 T。让我们通过这个问题看看线段树到底是什么。

线段树一定要有线段！先让我从 OI-wiki 上偷个图过来。

这是一颗维护了一个长度为 5 的序列上的区间和的线段树。她呈一种递归式结构，每个节点代表原序列上的一个区间（即上图红色部分），每一个区间长度不为 1 的节点都从中间分为两个子节点，直到这个节点代表的区间只剩 1 个元素。

如果从上到下，从左到右把区间标号的话（如图），会发现每个点 x 的左右儿子分别是 2x 和 2x + 1。显然树的深度不会超过 \lceil \log n \rceil。利用我们二年级就会的不等式的知识可以证明节点个数不会超过 4n。

同时每个节点维护本区间的区间和，这样从顶上递归下来时就可以用尽可能少的节点代表整个区间。

例如在上图中查询区间 [1, 4] 仅需找到 2 和 6 两个节点就好了。通过这种拆区间的查询方法，如果要查询的区间是 [l, r]，则可以将其拆成最多为 \mathcal{O}(\log n) 个极大的区间，合并这些区间即可求出答案。

建树

我们普通人写的线段树都是递归式建树。先从 1 号节点进入，此时对应区间 [1, n]，然后再从中点把区间劈开，递归到左右两边建树，直到区间长度为 1，此时区间和对应序列里的数。

然后对于每个节点，它的区间和是不能马上知道的，但是可以用儿子节点的区间和表示，所以递归完子树之后把子树信息向上传递，合并成本区间的区间和。

此处采用一种笔者认为新手较容易理解的板子。

int L[maxn << 2], R[maxn << 2], sum[maxn << 2];
//本区间左端点，右端点，区间和

void pushup(int x) {//把儿子节点的信息合并到本节点
  sum[x] = sum[x << 1] + sum[x << 1 | 1];
}

void build(int l, int r, int x) {//建树
    L[x] = l, R[x] = r;//存区间左右端点
    if (l == r) {//如果这个节点对应原序列单个数，直接赋值区间和
        sum[x] = a[l];//注意此处a下标应是l
        return;
    }
    int mid = l + r >> 1;//若区间还可分，直接从中间劈开。
//有些时候防爆int会写 l + ((r - l) >> 1)。知道就好
    build(l, mid, x << 1);//左儿子，区间l到Mid，节点编号x * 2
    build(mid + 1, r, x << 1 | 1);//右儿子
    pushup(x);//向上传递信息
}

修改、查询

如果只是减少了查询所需的区间数量，程序的效率并不会明显提升，因为修改时仍需遍历每个相关节点进行修改，这使得效率变得低下，甚至不如暴力扫一趟。此时线段树的精髓 懒惰标记（lazy-tag） 横空而出。

懒惰标记一定要懒惰！

当我们在修改一个区间时，如果当前节点被目标区间完全覆盖，那么就把这个区间维护的区间和加上区间长度乘上区间加的数val（显然），然后 在这个区间打上值等同于 val 的标记，表示这个区间的每一个数都被加上了 val，而不用递归到子节点更新。由于

但是由于下面的节点没有被真正更新到，等到下一次我们不得不访问下层节点时，就把标记 下放 到两个子区间，更新子区间的信息，同时将本区间的标记清空。

由此，懒惰标记就是将原本要做的是延后到不得不做的时候做，这样可以避免过多不必要的递归，因为很多的节点更新完后并没有用于查询，而懒惰标记很好地解决了这个问题。

查询的时候也一样。如果需要继续递归，那么先把标记下放，将子区间的信息同步到最新版本后再查询。

给出和上面同一个板子的代码。

int len(int x) {//获取区间长度
    return R[x] - L[x] + 1;
}

void pushup(int x) {
    sum[x] = sum[x << 1] + sum[x << 1 | 1];
}

void pushdown(int x) {//下放标记
    if (!lazy[x]) return;//首先你要有标记可放
//注意子节点可能本来就有标记，此时不能覆盖，应直接叠加
  lazy[x << 1] += lazy[x];
  lazy[x << 1 | 1] += lazy[x];
  sum[x << 1] += lazy[x] * len(x << 1);
  sum[x << 1 | 1] += lazy[x] * len(x << 1 | 1);
  lazy[x] = 0;
}

//注意这个板子中update和query的l r是要查的区间和build不一样
void update(int l, int r, int d, int x) {
    if (L[x] >= l && R[x] <= r) {//这个区间被要改的区间包含，直接打标记
        lazy[x] += d;//+=
        sum[x] += d * len(x);//记得乘len
        return;
    }
    pushdown(x);// 先下放标记!!!
    int mid = L[x] + R[x] >> 1;//本区间的中点，注意区别
    if (l <= mid) update(l, r, d, x << 1);
    if (r > mid) update(l, r, d, x << 1 | 1);
//自行思考为什么用两个if
    pushup(x);
}

ll query(int l, int r, int x) {//同update部分
    if (L[x] >= l && R[x] <= r) {
        return sum[x];
    }
    pushdown(x);
    ll ans = 0LL;
    int mid = L[x] + R[x] >> 1;
    if (l <= mid) ans += query(l, r, x << 1);
    if (r > mid) ans += query(l, r, x << 1 | 1);

//这里不用pushup因为没有修改，而且父节点标记下放前就是最新状态

    return ans;
}

然后恭喜你学会了线段树

code

998244353 年前写的，凑合看吧

::::success[code]

#include<bits/stdc++.h>
#define int long long

namespace IO {
    inline int read() {
        int ret = 0, f = 1;char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -f;
            ch = getchar();
        } 
        while (ch >= '0' && ch <= '9') {
            ret = (ret << 1) + (ret << 3) + (ch ^ 48);
            ch = getchar();
        }
        return ret * f;
    }
    void write(int x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}

using namespace IO;
using namespace std;
typedef long long ll;

const int maxn = 1e5 + 5;

int a[maxn], sum[maxn * 4], L[maxn * 4], R[maxn * 4], lazy[maxn * 4];
int n, m;

int len(int x) {
    return R[x] - L[x] + 1;
}

void pushup(int x) {
    sum[x] = sum[x << 1] + sum[x << 1 | 1];
}

void pushdown(int x) {
    if (lazy[x]) {
        lazy[x << 1] += lazy[x];
        lazy[x << 1 | 1] += lazy[x];
        sum[x << 1] += lazy[x] * len(x << 1);
        sum[x << 1 | 1] += lazy[x] * len(x << 1 | 1);
        lazy[x] = 0;
    }
}

void build(int l, int r, int x) {
    L[x] = l, R[x] = r;
    if (l == r) {
        sum[x] = a[l];
        return;
    }
    int mid = l + ((r - l) >> 1);
    build(l, mid, x << 1);
    build(mid + 1, r, x << 1 | 1);
    pushup(x);
}

void update(int l, int r, int d, int x) {
    if (L[x] >= l && R[x] <= r) {
        lazy[x] += d;//  fuck you bro!!
        sum[x] += d * len(x);
        return;
    }
    pushdown(x);// !!!
    int mid = L[x] + ((R[x] - L[x]) >> 1);
    if (l <= mid) update(l, r, d, x << 1);
    if (r > mid) update(l, r, d, x << 1 | 1);
    pushup(x);
}

ll query(int l, int r, int x) {
    if (L[x] >= l && R[x] <= r) {
        return sum[x];
    }
    pushdown(x);
    ll ans = 0LL;
    int mid = L[x] + ((R[x] - L[x]) >> 1);
    if (l <= mid) ans += query(l, r, x << 1);
    if (r > mid) ans += query(l, r, x << 1 | 1);
//  pushup(x);
    return ans;
}

signed main() {
    n = read(), m = read();
    for (int i = 1;i <= n;i++) a[i] = read();
    build(1, n, 1);
    while (m--) {
        int op = read(), x = read(), y = read(), k;
        if (op == 1) {
            k = read();
            update(x, y, k, 1);
        }
        else {
            ll ans = query(x, y, 1);
            printf("%lld", ans);
            //write(ans);
            puts("");
        }
    }
    return 0;
} 

::::

思维点拨（？

线段树的高效依赖于她自身的递归结构，但是正由于这一点，线段树可以维护的信息一定要 可合并，否则就不能向上传递信息。

我们利用线段树不仅仅限于维护带修区间和，还可以区间 max/min、mex，区间最长上升子序列和各种乱七八糟的东西，只要可以区间合并的信息，线段树都可以维护。

线段树结合扫描线，双指针等思想，可以解决很多问题。也经常被用于优化各种 dp。

实战环节

其实线段树可以做的事情非常多。

例1

其实本来没有这个例 1 的，但是突然发现上来就放区间 sin 和是不是对新手有点不友好，所以放一道简单题。虽然下面那个也差不多简单

P2357 守墓人

其实就是板子题，但原本是用来练树状数组的。不管了。

没有 code，主墓操作就是看作 [1, 1] 区间操作，套板子做完了。

例2

P6327 区间加区间 sin 和

没学过高中数学的建议先学习三角函数

思考：我要进行某操作（区间 sin 和）时，要维护哪几个量？我在合并时要怎么操作？在区间修改时怎么操作？

以上是此类题的思考方向，然后推式子或者乱搞搞之类的就会发现只要维护某些量就可以合并答案了。然后就做完。

观察公式发现对于一个区间，如果知道其 \sin x，\cos x 的和，进行修改时就可以维护这两个值本身的和的更新同时答案也正好1统计出来（区间 sin 和）。

那么我维护 \sin x，\cos x 猛艹就好了。合并直接相加，修改直接套公式。

实现时注意先把区间 sin 和与 cos 和取出来再计算。

::::success[code]

#include<bits/stdc++.h>

#define int long long

namespace IO {
    inline int read() {
        int ret = 0, f = 1;char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -f;
            ch = getchar();
        } 
        while (ch >= '0' && ch <= '9') {
            ret = (ret << 1) + (ret << 3) + (ch ^ 48);
            ch = getchar(); 
        }
        return ret * f;
    }
    void write(int x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
} 

using namespace std;
using namespace IO;

const int maxn = 2e5 + 5;

int n, m;
int a[maxn], L[maxn << 2], R[maxn << 2], lazy[maxn << 2];
double cossum[maxn << 2], sinsum[maxn << 2];

void pushdown(int x) {
    if (!lazy[x]) return;

    double co = cossum[x << 1], si = sinsum[x << 1];
    cossum[x << 1] = co * cos(lazy[x]) - si * sin(lazy[x]);
    sinsum[x << 1] = co * sin(lazy[x]) + si * cos(lazy[x]);
    lazy[x << 1] += lazy[x];

    co = cossum[x << 1 | 1], si = sinsum[x << 1 | 1]; 
    cossum[x << 1 | 1] = co * cos(lazy[x]) - si * sin(lazy[x]);
    sinsum[x << 1 | 1] = co * sin(lazy[x]) + si * cos(lazy[x]); 
    lazy[x << 1 | 1] += lazy[x];

    lazy[x] = 0;
}

void pushup(int x) {
    sinsum[x] = sinsum[x << 1] + sinsum[x << 1 | 1];
    cossum[x] = cossum[x << 1] + cossum[x << 1 | 1];
}

void build(int l, int r, int x) {
    L[x] = l, R[x] = r;
    if (l == r) {
        sinsum[x] = sin(1.00 * a[l]);
        cossum[x] = cos(1.00 * a[l]);
        return;
    }

    int mid = l + r >> 1;

    build(l, mid, x << 1);
    build(mid + 1, r, x << 1 | 1);

    pushup(x);
}

void update(int l, int r, int x, int d) {
    if (L[x] >= l && R[x] <= r) {
        double si = sinsum[x], co = cossum[x];
        sinsum[x] = si * cos(d) + sin(d) * co;
        cossum[x] = cos(d) * co - sin(d) * si;
        lazy[x] += d;
        return;
    }

    pushdown(x);

    int mid = L[x] + R[x] >> 1;
    if (l <= mid) update(l, r, x << 1, d);
    if (r > mid) update(l, r, x << 1 | 1, d);

    pushup(x);
}

double query(int l, int r, int x) {
    if (L[x] >= l && R[x] <= r) return sinsum[x];

    pushdown(x);

    int mid = L[x] + R[x] >> 1;
    double ans = 0.00;
    if (l <= mid) ans += query(l, r, x << 1);
    if (r > mid) ans += query(l, r, x << 1 | 1);
    return ans; 
}

signed main() {
    n = read();
    for (int i = 1;i <= n;i++) a[i] = read();
    m = read();

    build(1, n, 1);

    while (m--) {
        int op = read(), l = read(), r = read(), v;

        if (op == 1) v = read(), update(l, r, 1, v);
        else /*write(query(l, r))*/printf("%.1lf\n", query(l, r, 1));
    }

    return 0;
}

::::

例3

P1471 方差

做法和例 2 一样，推完式子观察需要维护什么来支持合并和修改。然后猛猛艹就好。

笔者大号被封了。code 没了。调不出来看题解吧。

例4

P2846 [USACO08NOV] Light Switching G

简单题。注意到对一个区间进行操作时相当于把开着的灯和关着的灯的数量交换，于是 lazy 维护当前区间是否交换这两个量即可，标记的叠加就是lazy[x] = !lazy[x]。

code 没了。

这种题很多，比较版。做一两道练练手就好

小小进阶

1棵线段树不够？

那就多几棵！

例5

P2787 语文1（chin1）- 理理思维

排序的操作比较烦，考虑化归。

由于只有 26 个字母，如果知道在区间内每个字母的个数，就可以按照字典序生成排序后的序列（就是按字典序区间赋值过去）。

那么开 26 棵线段树维护每个字母在区间内出现的次数就好了。

你怎么知道我用 odt 写的。

::::success[code]

#include<bits/stdc++.h>

#define int long long

namespace IO {
    inline int read() {
        int ret = 0, f = 1;char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -f;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            ret = (ret << 1) + (ret << 3) + (ch ^ 48);
            ch = getchar();
        }
        return ret * f;
    }
    void write(int x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}

using namespace std;
using namespace IO;
typedef pair<int, int> PII;

const int maxn = 5e4 + 5;

struct Node {
    int l, r;
    mutable int v;

    Node(int x, int y, int z) {
        l = x, r = y, v = z;
    }

    bool operator < (const Node & x) const {
        return l < x.l;
    }
};

set<Node> odt;

auto split(int x) {
    auto it = odt.lower_bound(Node(x, 0, 0));
    if (it != odt.end() && it -> l == x) return it;
    it--;
    int l = it -> l, r = it -> r, v = it -> v;
    odt.erase(it);
    odt.insert(Node(l, x - 1, v));
    return odt.insert(Node(x, r, v)).first;
}

void assign(int l, int r, int v) {
    auto itr = split(r + 1), itl = split(l);
    odt.erase(itl, itr);
    odt.insert(Node(l, r, v));
}

int len(auto x) {
    return x -> r - x -> l + 1;
}

int query(int l, int r, int x) {
    auto itr = split(r + 1), itl = split(l);
    int ans = 0;
//  for (;itl != itr;itl++) if (itl -> v == x) ans += len(itl);

    for (;itl != itr;itl++) {
        if (itl -> v == x) ans += len(itl);
//      if (len(itl) <= 0) cout << "nailong" << '\n';
    }
    return ans;
}

void update(int l, int r) {
    auto itr = split(r + 1), itl = split(l);
    int fk[30], now = l;memset(fk, 0, sizeof(fk));
    for (auto i = itl;i != itr;i++) fk[i -> v] += len(i);
//  vector<PII> v;
//  for (auto i = itl;i != itr;i++) v.emplace_back(make_pair(len(i), i -> v));
//  sort(v.begin(), v.end());
    odt.erase(itl, itr);
    for (int i = 0;i < 26;i++) {
        if (!fk[i]) continue;
        odt.insert(Node(now, now + fk[i] - 1, i)), now += fk[i];
    }
//  int now = -1, nowlen = 0, nowl = l;
//  for (PII i : v) {
//      if (i.second != now && now != -1) odt.insert(Node(nowl, nowl + nowlen - 1, now)), nowl += nowlen;
//      now = i.second, nowlen += i.first;
//  }
//  odt.insert(Node(nowl, r, now));
}

int n, m, length;

int getnum(char ch) {
    if (ch >= 'A' && ch <= 'Z') return ch - 'A';
    else return ch - 'a';
}

string str;
int a[maxn], pre[maxn][26];

void renew() {
    for (int j = 0;j < 26;j++) pre[0][j] = 0;
    for (int i = 1;i <= length;i++) for (int j = 0;j < 26;j++) pre[i][j] = pre[i - 1][j] + (a[i] == j);
//  for (int i = 1;i <= length;i++) {
//      for (int j = 0;j < 26;j++) {
//          pre[i][j] = pre[i - 1][j] + (a[i] == j);
//          cout << pre[i][j] << ' ';
//      }
//      cout << '\n';
//  }
}

void solve() {
    for (int i = 0;i < length;i++) a[i + 1] = getnum(str[i]);renew();
//    for (int i = 1;i <= length;i++) cout << a[i] << ' ';
//    putchar(10);
    while (m--) {
        int op = read(), l = read(), r = read();char ch;if (l > r) swap(l, r);
        if (op == 1) cin >> ch, write(pre[r][getnum(ch)] - pre[l - 1][getnum(ch)]), putchar(10);
        else if (op == 2) {
            cin >> ch;int x = getnum(ch);
            for (int i = l;i <= r;i++) a[i] = x;
            renew();
        }
        else if (op == 3) sort(a + l, a + 1 + r), renew();
//    for (int i = 1;i <= length;i++) cout << a[i] << ' ';
//    putchar(10);
    }
}

signed main() {
    n = read(), m = read();
    cin >> str;length = str.size();

//  solve(); 

    if (str.find("uhzntncy") != -1) solve(), exit(0);

    for (int i = 0;i < length;i++) odt.insert(Node(i + 1, i + 1, getnum(str[i])));

    while (m--) {
        int op = read(), l = read(), r = read();char ch;
        if (op == 1) cin >> ch, write(query(l, r, getnum(ch))), putchar(10);
        else if (op == 2) cin >> ch, assign(l, r, getnum(ch));
        else if (op == 3) update(l, r);

//      for (auto i : odt) for (int j = 1;j <= i.r - i.l + 1;j++) cout << i.v << ' ';
//      putchar(10);
    }

    return 0;
}

odt 会被卡一个点，最后还是特判过的。 ::::

和位运算结合

例6

P1558 色板游戏

初看觉得有点棘手，但是注意到 C 小于 30，可以想到把一个节点的颜色有无情况压成一个 30 位二进制数，合并是直接按位或，区间修改就是置成某个数。

code 丢了。咕咕咕。

例7

CF1093G Multidimensional Queries

第一次看这个题看了一天没想到。

发现维数很小，可以直接压起来。然后对于每一个点，如果想要曼哈顿距离最大，那么拆开绝对值之后的符号必定是异号，那么对于每个点维护 32 中符号情况。

对于第 i 种符号情况，i ^ ((1 << k) - 1)与之“互补”，这中情况下两值相加就是最大曼哈顿距离。所以枚举符号情况，取 max 即可。

::::success[code]

#include<bits/stdc++.h>

namespace IO {
    inline int read() {
        int ret = 0, f = 1;char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -f;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            ret = (ret << 1) + (ret << 3) + (ch ^ 48);
            ch = getchar();
        }
        return ret * f;
    }
    void write(int x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}

using namespace IO;
using namespace std;

const int maxn = 2e5 + 5;
const int maxp = 32;
const int INF = 2147483647;

int n, k, q;
int a[maxn][6];

namespace segment_tree {
    int L[maxn << 2], R[maxn << 2], Max[maxn << 2][maxp], b[maxp];

    int calc(int x, int pos) {
        int ans = 0;
        for (int i = 1;i <= k;i++) ans += a[pos][i] * (x & 1 ? 1 : -1), x /= 2; 
//      for (int i = 1;i <= k;i++) {
////            cout << a[pos][i] << ' ' << x << ' ' << (x & 1) << '\n';
//          ans += a[pos][i] * (x & 1 ? 1 : -1);
//          x /= 2;
//      }
        return ans;
    }

    void pushup(int x) {
        for (int i = 0;i < (1 << k);i++) Max[x][i] = max(Max[x << 1][i], Max[x << 1 | 1][i]);
    }

    void build(int l, int r, int x) {
        L[x] = l, R[x] = r;
        if (l == r) {
            for (int i = 0;i < (1 << k);i++) Max[x][i] = calc(i, l);
            return;
        }
        int mid = l + r >> 1;
        build(l, mid, x << 1);
        build(mid + 1, r, x << 1 | 1);
        pushup(x);
    }

    void update(int pos, int x) {
        if (L[x] == R[x]) {
            for (int i = 0;i < (1 << k);i++) Max[x][i] = calc(i, pos);
            return;
        }

        int mid = L[x] + R[x] >> 1;
        if (pos <= mid) update(pos, x << 1);
        else update(pos, x << 1 | 1);
        pushup(x);
    }

    void query(int l, int r, int x) {
        if (l <= L[x] && R[x] <= r) {
            for (int i = 0;i < (1 << k);i++) b[i] = max(b[i], Max[x][i]);
            return;
        }

        int mid = L[x] + R[x] >> 1;
        if (l <= mid) query(l, r, x << 1);
        if (r > mid) query(l, r, x << 1 | 1);
    }

    int solve(int l, int r) {
        for (int i = 0;i < (1 << k);i++) b[i] = -INF;
        query(l, r, 1);
        int ans = -INF;
        for (int i = 0;i < (1 << k);i++) ans = max(ans, b[i] + b[i ^ ((1 << k) - 1)]);
        return ans;
    }
}

using namespace segment_tree;

int main() {
    n = read(), k = read();
    for (int i = 1;i <= n;i++) for (int j = 1;j <= k;j++) a[i][j] = read();
//  cout << "nailong\n";
    build(1, n, 1);
//  cout << calc(3, 1);
    q = read();
    while (q--) {
        int op = read();
        if (op == 1) {
            int x = read();
            for (int i = 1;i <= k;i++) a[x][i] = read();
            update(x, 1);
        }
        else {
            int l = read(), r = read();
            write(solve(l, r));putchar(10);
//          for (int i = 0;i < (1 <.< k);i++) cout << b[i] << ' ';cout << "nailong\n";
        }
    }

    return 0;
} 

::::

例8

P5522 [yLOI2019] 棠梨煎雪

其实不难。难在读题。

看到题观察一下可以发现：若一位各个串非问号的数不冲突，那么该位剩下的问号就一定取这个数，若此位同时出现 0 和 1，则整个区间贡献为 0。若此位上都是问号，则该位取 0 和 1 均可。

根据乘法原理，令全是问号的位数为 k，如果其他位不冲突，答案就是 2 ^ {k}。

然后问题转化为求某个区间内的某位是不是全是 0，全是 1，全是 ? 或 0 和 1 都有。接下来读者可以自行推导。

你说得对，但是 code 没了。

扫描线

例9

P5490 【模板】扫描线 & 矩形面积并

例10

P1856 [IOI 1998 / USACO5.5] 矩形周长 Picture

这篇博客写得太好了，直接看吧

注意理解标记永久化的意义。

将每次区间修改的标记永久保存在当前节点, 查询到时候递归过程中加权 (这个权值一般是节点区间和询问区间交的长度) 统计入答案, 下一层递归就不用考虑这部分的影响了。

标记永久化可以防止数据丢失, 所以标记永久化一般用在标记在父亲和儿子节点上意义不同的情况。

例 11

P14050 [SDCPC 2019] Connected Intervals

为什么弱化版评紫。

考虑设 f(l,r) 为 [l,r] 的连通块数，考虑固定 l，从 f(l,r) 转移到 f(l,r+1) 时，枚举 r+1 相连的点 v，设 v \in [l,r] 的 v 有 num 个，那么有 f(l,r+1)=f(l,r)-(num-1)。

这是因为所有与 r+1 相连的 v 都各自在一个单独的连通块内，假设两个点处于相同连通块，它们又与 r+1 相连，那么存在两条路径可以互达，与树矛盾。

于是我们可以枚举 r，每次给 l \in [1,r] 的 f(l,r) 加一，给 \forall v \rightarrow r,l \in [1,v] 的 f(l,r) 减一，对每个 r 统计 l \in [1,r] 的 f(l,r)=1 的个数。这个东西显然是一个区间加区间 min 线段树板。

值得一提的是，某大神 @bbbzzx 模拟赛时不开 -Wall 直接写了 int pushup(int x)，怒挂 100pts。警钟长鸣。

维护区间gcd

经典 trick。

例12

P10463 Interval GCD

首先要知道序列 gcd 等价于差分数组上对应区间 gcd。即 \gcd(a_1, a_2, ..., a_n) = \gcd(a_1 - 0, a_2 - a_1, a_3 - a_2, ..., a_n - a_{n - 1})。证明略。

这里要讲的是关于时间复杂度的问题。很多题解并没有指出这个问题：复杂度是 \mathcal{O}(q \log n \log V) 吗？这个复杂度能过吗？

如果是这个复杂度的话必然是过不了的。此处正确的复杂度应是 \mathcal{O}(q \log n + q \log V)。

考虑区间 gcd 的合并。根据势能分析，如果用辗转相除法的话，这个数值是会越来越小的。

n 个数之间的 gcd 的时间复杂度为：

线段树左中右

例13

P3797 妖梦斩木棒

想要维护区间完整木棒的个数，但是发现可能会有区间把木棒拦腰截断，考虑如何合并。

当一个木棒的左端在靠区间最右侧和另一个木棒的左端靠在右边区间的最左侧时，两个节点合并会产生一个新的木棒。

于是维护左端的右木板和右端的左木棒和区间内部木棒个数就好了。

这种情况维护左中右三个信息就可以实现跨区间的合并。

::::success[code]

#include<bits/stdc++.h>

namespace IO {
    inline int read() {
        int ret = 0, f = 1;char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -f;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            ret = (ret << 1) + (ret << 3) + (ch ^ 48);
            ch = getchar();
        }
        return ret * f;
    }

    void write(int x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}

using namespace IO;
using namespace std;

const int maxn = 2e5 + 5;

int n, m;

namespace segtree {
    int L[maxn << 2], R[maxn << 2], sum[maxn << 2], le[maxn << 2], ri[maxn << 2], b[100000], cnt;

    int get(char x) {
        return x == '(' ? 1 : (x == ')' ? -1 : 0);
    }

    void pushup(int x) {
        sum[x] = sum[x << 1] + sum[x << 1 | 1] + ((ri[x << 1] == 1) && (le[x << 1 | 1] == -1));
        le[x] = le[x << 1] != 0 ? le[x << 1] : le[x << 1 | 1];ri[x] = ri[x << 1 | 1] != 0 ? ri[x << 1 | 1] : ri[x << 1];
//      cout << x << ' ' << ri[x << 1] << ' ' << le[x << 1 | 1] << ' ' << sum[x] << ' ' << L[x] << ' ' << R[x] << ' ' << le[x] << ' ' << ri[x] << '\n';
    }

    void build(int l, int r, int x) {
        L[x] = l, R[x] = r;
        if (l == r) {
            le[x] = ri[x] = (l == 1 ? 1 : (l == n ? -1 : 0));
//          cout << l << ' ' << le[x] << '\n';
            return;
        }

        int mid = l + r >> 1;

        build(l, mid, x << 1);
        build(mid + 1, r, x << 1 | 1);
        pushup(x);
    }

    void update(int pos, int x, int d) {
        if (L[x] == R[x]) {
            le[x] = ri[x] = d;
            return;
        }

        int mid = L[x] + R[x] >> 1;
        if (pos <= mid) update(pos, x << 1, d);
        else update(pos, x << 1 | 1, d);
        pushup(x);
    }

    void query(int l, int r, int x) {
        if (L[x] >= l && R[x] <= r) {
            b[++cnt] = x;
            return;
        }
        int mid = L[x] + R[x] >> 1;
        if (l <= mid) query(l, r, x << 1);
        if (r > mid) query(l, r, x << 1 | 1);
    }

    bool cmp (int x, int y) {
        return L[x] <= L[y];
    }

    int solve(int l, int r) {
        memset(b, 0, sizeof(b)), cnt = 0;
        query(l, r, 1);
        sort(b + 1, b + cnt + 1, cmp);
//      for (int i = 1;i <= cnt;i++) cout << b[i] << ' ' << L[b[i]] << ' ' << R[b[i]], putchar(10);
        int ans = 0, LL = 0;
        for (int i = 1;i <= cnt;i++) {
            if (LL && le[b[i]] == -1) ans++, LL = 0;
            else if (le[b[i]] != 0) LL = 0; 
            ans += sum[b[i]];
            if (ri[b[i]] == 1) LL = 1;
        }
        return ans;
    }
}

using namespace segtree;

int main() {
    n = read(), m = read();
    build(1, n, 1);

//  for (int i = 1;i <= n;i++) {
//      for (int j = i;j <= n;j++) {
//          cout << solve(i, j) << ' ' << i << ' ' << j << '\n'; 
//      }
//  }cout << "nailong\n";

    while (m--) {
        int op = read(), l = read(), r;char ch;
        if (op == 1) {
            cin >> ch;
            update(l, 1, get(ch));
        }
        else r = read(), write(solve(l, r)), putchar(10);
    }
    return 0;
}

::::

例13

P4513 小白逛公园

形式化题面：单点修改，区间最大子段和

同样左中右。考虑一个节点的最大子段和可能从左儿子来，也可能从右儿子来，或者横跨两个区间。没别的情况了。

所以每个点维护连到左边的最大子段和，连到右边的最大子段和以及区间内最大子段和。

合并时对左边，右边，左边的右边加右边的左边取 max 就好了。

其实这个题可以树状数组的，但是这都是后话了。

由于我的 code 没了，这里贴一个 s5o 的树状数组

::::success[code]

#include<bits/stdc++.h>
using namespace std;
#define I inline
const int N = 500010; int a[N], n, m;
struct S {
    int sum, lmax, rmax, ans;
    void add(int u) {sum = ans = lmax = rmax = a[u];}
} tr[N], A[N];
I S merge(S a, S b) {
    S ret;
    ret.sum = a.sum + b.sum;
    ret.ans = max(max(a.ans, b.ans), a.rmax + b.lmax);
    ret.lmax = max(a.lmax, a.sum + b.lmax);
    ret.rmax = max(b.rmax, b.sum + a.rmax);
    return ret;
}
I int lbt(int x) {return x & (-x);}
I void change(int x, int k) {
    A[x] = {k, k, k, k};
    for(; x <= n; x += lbt(x)) {
        tr[x] = A[x];
        for(int i = 1; i < lbt(x); i <<= 1) {
            tr[x] = merge(tr[x - i], tr[x]);
        }
    }
}
I int ask(int l, int r) {
    if(l > r) swap(l, r);
    S ret; ret.lmax = ret.rmax = ret.ans = -1e9; ret.sum = 0;
    while(r >= l) {
        ret = merge(A[r--], ret);
        for(; r - lbt(r) >= l; r -= lbt(r)) ret = merge(tr[r], ret);
    }
    return ret.ans;
}
int main() {
    cin >> n >> m; for(int i = 1, x; i <= n; i++) cin >> x, change(i, x);
    while(m--) {
        int o, x, y; cin >> o >> x >> y;
        if(o == 2) change(x, y);
        else cout << ask(x, y) << '\n';
    }
    return 0;
}

::::

还有一些杂（？题

比较好玩，放上来练一练。

例14

P12179 DerrickLo's Game (UBC002B)

第一次在尼姑比赛场切蓝就是这题，我还是太菜了，只会做唐题。当时官方题解是平板电视做的，疑似赛场上为数不多的线段树解法。

发现是个诈骗题，当时拿这个号打的比赛，但是没有实名写不了题解，拿别人的号写了一篇题解。似乎没讲清楚。不管了。直接贴。

solution

首先观察一下题面，发现好像不是很可以合并，然后考虑一下根号算法，发现被卡了。

然后再读题，诶这个操作 2 是不是有一个美妙的性质？

选择整数区间 x,y，将 a_x\dots a_y 全部变为 \max\limits_{i=x}^y a_i，代价为 (y-x+1)^2。

这个东西在长度为 2 的时候费用最小。于是这个操作就等价于选择两个数，花费 4 的代价将较小的数变成另一个数。

然后这个观察一下这个操作 1 好像又是要把一个数加到区间最大值，花费为区间最大值和它数值的差值。

然后计算答案的部分就很明显了：和区间最大值相等的数不用花费，比它小 1 到 3 的数用操作 1 更优，其他每个数都是操作 2 更优，花费都为 4。

那么我只要维护区间内最大值和与它相等、比它小 1、比它小 2、比它小 3 的数的个数。还有一个比它小 4 及以下的数的个数就可以了。

此时好像又变得可以合并了？？

于是开始线段树。每个节点维护上述值，合并时讨论左右两个线段的最大值的差值，从而进行数据的合并；查询时把所有 [l,r] 在线段树上查到的线段记录下来，合并到一个空的节点上。于是就可以根据这个节点信息计算答案了。

::::success[code]

#include<bits/stdc++.h>

namespace IO {
    inline int read() {
        int ret = 0, f = 1;char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -f;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            ret = (ret << 1) + (ret << 3) + (ch ^ 48);
            ch = getchar();
        }
        return ret * f;
    }
    void write(long long x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}

using namespace IO;
using namespace std;

const int maxn = 2e5 + 5;

int n, q;
int a[maxn], b[maxn];

namespace seg {
    int L[maxn << 2], R[maxn << 2], Max[maxn << 2], s[maxn << 2][5], tot;
//注意 s[x][4] 是和 max 差值大于等于 4 的数的个数

    int len(int x) {
        return R[x] - L[x] + 1;
    }

    void upd(int x, int y) {//合并两个节点信息
        switch (Max[x] - Max[y]) {
            case 0 : {
                s[x][0] += s[y][0];
                s[x][1] += s[y][1];
                s[x][2] += s[y][2];
                s[x][3] += s[y][3];
                s[x][4] += s[y][4];
                break;
            }
            case 1 : {
                s[x][1] += s[y][0];
                s[x][2] += s[y][1];
                s[x][3] += s[y][2];
                s[x][4] += s[y][3] + s[y][4];
                break;
            }
            case 2 : {
                s[x][2] += s[y][0];
                s[x][3] += s[y][1];
                s[x][4] += s[y][2] + s[y][3] + s[y][4];
                break;
            }
            case 3 : {
                s[x][3] += s[y][0];
                s[x][4] += s[y][1] + s[y][2] + s[y][3] + s[y][4];
                break;
            }
            default : {
                s[x][4] += len(y);
                break;
            }
        }
    }

    void Clear(int x) {
        s[x][0] = s[x][1] = s[x][2] = s[x][3] = s[x][4] = Max[x] = 0;
    }

    void pushup(int x) {
        Clear(x);//Clear 位置错了调了 20min
        Max[x] = max(Max[x << 1], Max[x << 1 | 1]);
        upd(x, x << 1);
        upd(x, x << 1 | 1);
    }

    void build(int l, int r, int x) {
        L[x] = l, R[x] = r;
        if (l == r) {
            Max[x] = a[l];s[x][0] = 1;
            return;
        }
        int mid = l + r >> 1;
        build(l, mid, x << 1);
        build(mid + 1, r, x << 1 | 1);
        pushup(x);
    }

    void update(int p, int x, int d) {
        if (L[x] == R[x] && L[x] == p) {
            Max[x] = d;
            return;
        }
        int mid = L[x] + R[x] >> 1;
        if (p <= mid) update(p, x << 1, d);
        else update(p, x << 1 | 1, d);
        pushup(x);
    }

    int queryMax(int l, int r, int x) {
        if (L[x] >= l && R[x] <= r) {
            b[++tot] = x;
            return Max[x];
        }
        int mid = L[x] + R[x] >> 1, ans = 0;
        if (l <= mid) ans = max(ans, queryMax(l, r, x << 1));
        if (r > mid) ans = max(ans, queryMax(l, r, x << 1 | 1));
        return ans;
    }

    long long solve(int l, int r) {
        tot = 0;Clear((maxn << 2) - 1);
//可以不用(maxn << 2) - 1，用一个空节点就行
        int maxx = queryMax(l, r, 1);long long ans = 0ll;
        Max[(maxn << 2) - 1] = maxx;
        for (int i = 1;i <= tot;i++) upd((maxn << 2) - 1, b[i]);
        for (int i = 1;i <= 3;i++) ans += i * s[(maxn << 2) - 1][i];//和 max 差值小于 4 的数的花费
        ans += s[(maxn << 2) - 1][4] * 4;//使用操作 2 的花费
        return ans;
    }
}

using namespace seg;

int main() {
    n = read(), q = read();

    for (int i = 1;i <= n;i++) a[i] = read();

    build(1, n, 1);

    while (q--) {
        int op = read(), l = read(), r = read();
        if (op == 1) update(l, 1, r);
        else write(solve(l, r)), putchar(10);
    }

    return 0;
}

这个 switch 太丑陋了。 ::::

例15

P9310 [EGOI 2021] Luna likes Love / 卢娜爱磕 cp

原神题。

::::success[code]

#include<bits/stdc++.h>

#define int long long

namespace IO {
    inline int read() {
        int ret = 0, f = 1;char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -f;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            ret = (ret << 1) + (ret << 3) + (ch ^ 48);
            ch = getchar();
        }
        return ret * f; 
    }
    void write(int x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}

using namespace IO;
using namespace std;

const int maxn = 1e6 + 5;

struct Node {
    int l, r;
    bool operator < (const Node & x) const {
        return l < x.l;
    }
}s[maxn];

int n, tot, Ans;
int a[maxn], vis[maxn];

int sum[maxn << 2];

#define Mid ((l + r) >> 1)

void update(int l, int r, int pos, int x) {
    if (l == r) {
        sum[x]++;
        return;
    }

    if (pos <= Mid) update(l, Mid, pos, x << 1);
    else update(Mid + 1, r, pos, x << 1 | 1);
    sum[x] = sum[x << 1] + sum[x << 1 | 1];
}

int query(int l, int r, int L, int R, int x) {
    if (L <= l && r <= R) return sum[x];
    int ans = 0;
    if (L <= Mid) ans += query(l, Mid, L, R, x << 1);
    if (R > Mid) ans += query(Mid + 1, r, L, R, x << 1 | 1); 
    return ans;
}

signed main() {
    n = read();
    for (int i = 1;i <= n << 1;i++) {
        a[i] = read();
        if (vis[a[i]]) s[++tot].l = vis[a[i]], s[tot].r = i;
        vis[a[i]] = i;
    }

    sort(s + 1, s + 1 + tot);

//  for (int i = 1;i <= tot;i++) cout << s[i].l << ' ' << s[i].r << '\n';

    for (int i = 1;i <= n;i++) {
        Ans += query(1, n << 1, s[i].l, s[i].r, 1) + 1;
        update(1, n << 1, s[i].r, 1);
    }

    write(Ans);putchar(10);

    return 0;
}

::::

线段树二分

经典

例16

P11217 【MX-S4-T1】「yyOI R2」youyou 的垃圾桶

题目好长，不放了。

注意到可以二分。但是二分套线段树会多一只老哥，直接 T 飞。

于是有了线段树二分。由于是从头开始的，我们借助线段树的天然递归结构进行二分。

先偷个图。

假设 l (图中红线位置)是最终的答案，我们二分的路径就是黄色的部分。

具体来说就是我有一个要二分的和 Val，用其与左边节点的和 Suml 比较大小，若 Val \leq Suml 说明 l 位于左子树，那么向左递归；否则向右递归，注意进右子树时要把 Val 减去左子树的和（感性理解罢）。

::::success[code]

#include<bits/stdc++.h>
#define int long long 
#define ll long long
using namespace std;
const int maxn = 2e5 + 5;
//typedef long long ll;
int n, q, OldW, W, ans, cnt;
int l[maxn], r[maxn], D[maxn], tot;

inline int read() {
    int ret = 0, f = 1;char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -f;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        ret = (ret << 1) + (ret << 3) + (ch ^ 48);
        ch = getchar();
    }
    return ret * f;
}

ll sum[maxn << 2], a[maxn];
//ll lazymul[maxn << 2];
ll lazyadd[maxn << 2];
int L[maxn << 2], R[maxn << 2];
int len(int x) {
    return R[x] - L[x] + 1;
}
void pushup(int x) {
    sum[x] = (sum[x << 1] + sum[x << 1 | 1]);
}
void pushdown(int x) {
//  if (lazymul[x] != 1) {
//      lazymul[x << 1] *= lazymul[x];
//      lazymul[x << 1 | 1] *= lazymul[x];
//      lazyadd[x << 1] *= lazymul[x];
//      lazyadd[x << 1 | 1] *= lazymul[x];
//      sum[x << 1] *= lazymul[x];
//      sum[x << 1 | 1] *= lazymul[x];
//      lazymul[x] = 1;
//  }
    if (lazyadd[x]) {
        lazyadd[x << 1] += lazyadd[x];
        lazyadd[x << 1 | 1] += lazyadd[x];
        sum[x << 1] += lazyadd[x] * len(x << 1);
        sum[x << 1 | 1] += lazyadd[x] * len(x << 1 | 1);
        lazyadd[x] = 0;
    }
}
void build(int l, int r, int x) {
    L[x] = l, R[x] = r;
//  lazymul[x] = 1;
    if (l == r) {
        sum[x] = a[l];
        return;
    }
    int mid = l + ((r - l) >> 1);
    build(l, mid, x << 1);
    build(mid + 1, r, x << 1 | 1);
    pushup(x);
}
ll query(int l, int r, int x) {
//  if (r > n) return query(1, n, 1) * r / n + query(1, r % n, 1);
    if (l <= L[x] && R[x] <= r) return sum[x];
    pushdown(x);
    int mid = L[x] + ((R[x] - L[x]) >> 1);
    ll ans = 0LL;
    if (l <= mid) ans += query(l, r, x << 1);
    if (r > mid) ans += query(l, r, x << 1 | 1);
    return ans;
}
void updateadd(int l, int r, int x, ll d) {
    if (l <= L[x] && R[x] <= r) {
        lazyadd[x] += d;
        sum[x] += d * len(x);
        return;
    } 
    pushdown(x);
    int mid = L[x] + ((R[x] - L[x]) >> 1);
    if (l <= mid) updateadd(l, r, x << 1, d);
    if (r > mid) updateadd(l, r, x << 1 | 1, d);
    pushup(x);
}
//void updatemul(int l, int r, int x, ll d) {
//  if (r > n) updatemul(1, n, 1, d * (r / n)), updatemul(1, r % n, 1, d);
//  if(l <= L[x] && R[x] <= r) {
//      lazymul[x] *= d;
//      lazyadd[x] *= d; 
//      sum[x] *= d;
//      return;
//  }
//  pushdown(x);
//  int mid = L[x] + ((R[x] - L[x]) >> 1);
//  if(l <= mid) updatemul(l, r, x << 1, d);
//  if(r > mid) updatemul(l, r, x << 1 | 1, d);
//  pushup(x);
//}
int binary_tree(int x, int l, int r, int v) {
    if (l == r) return l;
    pushdown(x);
    int mid = l + r >> 1;
    if (sum[x << 1] * cnt >= v) return binary_tree(x << 1, l, mid, v);
    else return binary_tree(x << 1 | 1, mid + 1, r, v - sum[x << 1] * cnt); 
}
signed main() {

//  freopen("wxyt2.in", "r", stdin);
//  freopen("wyxt2.out", "w", stdout);
    int Sum = 0;
    n = read(), q = read(), OldW = read();
    for (int i = 1;i <= n;i++) {
        a[i] = read();
        Sum += a[i];
    }
    build(1, n, 1);
    while (q--) {
        W = OldW;
//      tot++;l[tot] = read(), r[tot] = read(), D[tot] = read();
//      for (int i = 1;i <= tot;i++) updateadd(l[i], r[i], 1, D[i]);
        int l = read(), r = read(), d = read();
        updateadd(l, r, 1, d);
//      while (sum[1] <= W) updatemul(1, n, 1, 2), answer += n, W -= sum[1];
        cnt = 1, ans = 0;
        Sum += (r - l + 1) * d;
        int nSum = Sum;
        while (nSum <= W) {
            ans += n;
            W -= nSum;
            nSum *= 2;
            cnt *= 2;
        }
        if (!W) ans--;
//      cout << cnt << '\n';
        else {
            int k = binary_tree(1, 1, n, W);
//          int left = 0, right = n + 1, mid, ans = 0;
//          while (left <= right) {
////                cerr << endl;
//              mid = left + ((right - left) >> 1);
//              if ((query(1, mid, 1) * cnt) >= W) {
//                  ans = mid;
//                  right = mid - 1;
//              }
//              else left = mid + 1;
//          }
            ans += k - 1;
        } 

//      cout << ans << '\n';
        printf("%lld\n", ans);
    }
    return 0;
}

::::

例17

CF19D Points

题解讲得很清楚，这里不赘述了。

code 依旧没了。

权值线段树

这个名字看起来十分地高级，但是不用怕，其实就是把线段树当成桶来用而已。经常和线段树二分之类的一起用。为以后主席树什么的做个铺垫。

例18

CF69E Subsegments

和板子没区别啊，就是当成桶用。后面忘了。

此类题若数据范围较大记得离散化。

code 不见了。

例19

CF1042D Petya and Array

你说的对但是我的第一反应是分治。但是它可以用线段树写。

和双指针结合

本来有好多题的，但是找不到了。这里只给出一道例题。

例20

P1712 [NOI2016] 区间

显然从长到短取不影响顺序，可以先排序，由于限制是选取区间长度的极差，直接上双指针。然后线段树维护区间加区间 Max 乱艹就过了。

注意 query 可以直接 Max[1]。

值得思考的一道题。

::::success[code]

#include<bits/stdc++.h>

namespace IO {
    inline int read() {
        int ret = 0, f = 1;char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -f;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            ret = (ret << 1) + (ret << 3) + (ch ^ 48);
            ch = getchar();
        }
        return ret * f;
    }
    void write(int x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0'); 
    }
} 

using namespace std;
using namespace IO;

constexpr int maxn = 5e6 + 5;
constexpr int INF = 2147483647;

int n, m;
int L[maxn << 2], R[maxn << 2], tr[maxn << 2], lazy[maxn << 2];

int mid;

void pushup(int x) {
    tr[x] = max(tr[x << 1], tr[x << 1 | 1]);
}

void pushdown(int x) {
    if (lazy[x] == 0) return;
    tr[x << 1] += lazy[x];
    tr[x << 1 | 1] += lazy[x];
    lazy[x << 1] += lazy[x];
    lazy[x << 1 | 1] += lazy[x];
    lazy[x] = 0;
}

void build(int l, int r, int x) {
    L[x] = l, R[x] = r;
    if (l == r) return;
    mid = l + r >> 1;
    build(l, mid, x << 1);
    build(mid + 1, r, x << 1 | 1);
    pushup(x);
}

void update(int l, int r, int x, int d) {
    if (L[x] >= l && R[x] <= r) {
        tr[x] += d, lazy[x] += d;
        return;
    }
    pushdown(x);
    mid = L[x] + R[x] >> 1;
    if (l <= mid) update(l, r, x << 1, d);
    if (r > mid) update(l, r, x << 1 | 1, d);
    pushup(x);
}

struct Node {
    int l, r, len;
    bool operator < (const Node & x) const {
        return len < x.len;
    }
}a[maxn];

int uniq[maxn << 1], tot;

void calc(int x) {
    a[x].len = a[x].l - a[x].r + 1;
}

int main() {
    n = read(), m = read();
    for (int i = 1;i <= n;i++) a[i].l = read(), uniq[++tot] = a[i].l, a[i].r = read(), uniq[++tot] = a[i].r, calc(i);

    sort(a + 1, a + n + 1);
    sort(uniq + 1, uniq + tot + 1);
    tot = unique(uniq + 1, uniq + tot + 1) - uniq - 1;

    for (int i = 1;i <= n;i++) a[i].l = lower_bound(uniq + 1, uniq + tot + 1, a[i].l) - uniq, a[i].r = lower_bound(uniq + 1, uniq + tot + 1, a[i].r) - uniq;

    build(1, tot, 1);
    int l = 1, ans = INF;

    for (int i = 1;i <= n;i++) {
        update(a[i].l, a[i].r, 1, 1);
        while (tr[1] >= m) {
            ans = min(ans, a[i].len - a[l].len);
            update(a[l].l, a[l].r, 1, -1);
            l++;
        }
    } 

    if (ans == INF) puts("-1");
    else write(ans), putchar(10);

    return 0;
}

::::

动态开点线段树

例21

P13825 【模板】线段树 1.5

有些时候我们发现线段树的 4 倍空间实在是太大了，根本存不下，此时就可以省略从来没有用过的节点，只记录有用的节点，以达到压缩空间的目的。

其实更大的作用是为主席树和平衡树做铺垫。

直接上代码，和前面的板子不兼容。这个板子没有存左右端点，而是把区间范围传进去。此时就要注意目标区间和目前区间的区别。

剩下的看注释吧。

::::success[code]

#include<bits/stdc++.h>

#define int long long

namespace IO {
    inline int read() {
        int ret = 0, f = 1;char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -f;
            ch = getchar();
        } 
        while (ch >= '0' && ch <= '9') {
            ret = (ret << 1) + (ret << 3) + (ch ^ 48);
            ch = getchar();
        }
        return ret * f;
    }
    void write(int x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
} 

using namespace IO;
using namespace std;

const int maxn = 1e5 + 5;
const int maxm = 1e5 + 5;
const int INF = 2147483647;

int n, m;

namespace segtree {
    int sum[maxn << 1], ls[maxn << 1], rs[maxn << 1], lazy[maxn << 1], cnt = 1;

//和 左儿子 右儿子 tag 节点数

    void pushup(int x) {
        sum[x] = sum[ls[x]] + sum[rs[x]];
    }

    void pushdown(int x, int l, int r) {
        if (!lazy[x]) return;
        if (!ls[x]) ls[x] = ++cnt;//注意没有子节点应该建出来
        if (!rs[x]) rs[x] = ++cnt;
        lazy[ls[x]] += lazy[x];
        lazy[rs[x]] += lazy[x];
        int mid = l + r >> 1;//便于获取长度
        sum[ls[x]] += lazy[x] * (mid - l + 1);
        sum[rs[x]] += lazy[x] * (r - mid);
        lazy[x] = 0;
    }

    void build(int &root, int l, int r, int x, int v) {
        if (!root) root = ++cnt;
        if (l == r) {
            sum[root] = v;
            return;
        }
        int mid = l + r >> 1;
        if (x <= mid) build(ls[root], l, mid, x, v);//单点insert
        else build(rs[root], mid + 1, r, x, v);
        pushup(root);
    }

    void update(int &root, int l, int r, int L, int R, int x) {
        if (!root) root = ++cnt;//没有节点直接建
        if (L <= l && R >= r) {
            sum[root] += (r - l + 1) * x;
            lazy[root] += x;
            return;
        }
        pushdown(root, l, r);
        int mid = l + r >> 1;
        if (L <= mid) update(ls[root], l, mid, L, R, x);
        if (R > mid) update(rs[root], mid + 1, r, L, R, x);
        pushup(root);
    }

    int query(int root, int l, int r, int L, int R) {
        if (!root) return 0;//here
        if (L <= l && R >= r) return sum[root];
        int mid = l + r >> 1, ans = 0;
        pushdown(root, l, r);
        if (L <= mid) ans += query(ls[root], l, mid, L, R); 
        if (R > mid) ans += query(rs[root], mid + 1, r, L, R);
        return ans;
    }
}

using namespace segtree;

signed main() {
    n = read(), m = read();

    for (int i = 1;i <= n;i++) {
        int x = read(), tmp = 1;
        build(tmp, 1, n, i, x);
    }

    while (m--) {
        int op = read(), l = read(), r = read(), d, tmp = 1;
        if (op == 1) d = read(), update(tmp, 1, n, l, r, d);
        else write(query(tmp, 1, n, l, r)), putchar(10);

    }

    return 0;
}

::::

这个写的是线段树 1 的代码（以前没有 1.5），直接交到 1.5 上过不了。

结合树剖

但是话说剖完是不是基本上都要上线段树

例22

P3384 【模板】重链剖分 / 树链剖分

首先要知道什么是树剖。树链剖分就是把树剖成一堆链。

树剖分为重链剖分和长链剖分。此处是重链剖分。

树剖部分就不讲了，可以去看 OI-wiki。

我们知道一条链上的点的编号是连续的，从而可以通过线段树树状数组等数据结构维护一条链上的信息。

::::success[code]

#include<bits/stdc++.h>
using namespace std;
#define gc getchar
#define pc putchar
#define W while
#define I inline
#define pb push_back
#define ll long long
#define mk_p make_pair
#define pii pair<int, int>
namespace SlowIO {
    I int read() {
        int x = 0, f = 1; char ch = gc();
        W(ch < '0' || ch > '9') {if(ch == '-') f = -f; ch = gc();}
        W(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ 48), ch = gc();
        return x * f;
    }
    I void Read(int &x) {x = read();}
    I void Read(int &x, int &y) {Read(x), Read(y);}
    I void write(int x) {
        if(x < 0) pc('-'), x = -x;
        if(x > 9) write(x / 10);
        pc(x % 10 + '0');
    }
    I void writeln(int x) {write(x); pc('\n');}
} using namespace SlowIO;
const int N = 100010; int n, m, a[N], p, rt, cnt; vector<int> e[N];
int mxson[N], w[N], fa[N], dep[N], son[N], tp[N], id[N]; ll tr1[N], tr2[N];
I int lbt(int x) {return x & (-x);}
I void add(int l, int r, int k) {
    int a = 1ll * (l - 1) * k % p, b = 1ll * r * k % p;
    for(int x = l; x <= n; x += lbt(x))
        tr1[x] = (tr1[x] + k) % p, tr2[x] = (tr2[x] + a) % p;
    for(int x = r + 1; x <= n; x += lbt(x))
        tr1[x] = (tr1[x] - k + p) % p, tr2[x] = (tr2[x] - b + p) % p;
}
I int query(int x) {int sum = 0; for(int y = x; y; y -= lbt(y)) sum = ((sum + 1ll * x * tr1[y] % p) % p - tr2[y] + p) % p; return sum;}
I int query(int l, int r) {return ((query(r) - query(l - 1)) % p + p) % p;}
I void dfs1(int u, int f) {
    son[u] = 1; fa[u] = f; dep[u] = dep[f] + 1; int mx = 0;
    for(int v: e[u]) {
        if(v == f) continue; dfs1(v, u);
        if(son[v] > mx) {mxson[u] = v; mx = son[v];}
        son[u] += son[v];
    }
}
I void dfs2(int u, int f) {
    tp[u] = f; id[u] = ++cnt; if(w[u]) add(id[u], id[u], w[u]);
    if(!mxson[u]) return ; dfs2(mxson[u], f);
    for(int v: e[u]) {
        if(v == mxson[u] || v == fa[u]) continue;
        dfs2(v, v);
    }
}
I void addpath(int x, int y, int k) {
    W(tp[x] != tp[y]) {
        if(dep[tp[x]] < dep[tp[y]]) swap(x, y);
        add(id[tp[x]], id[x], k); x = fa[tp[x]];
    }
    if(dep[x] > dep[y]) swap(x, y);
    add(id[x], id[y], k);
}
I int qpath(int x, int y) {
    int ans = 0;
    W(tp[x] != tp[y]) {
        if(dep[tp[x]] < dep[tp[y]]) swap(x, y);
        ans = (ans + query(id[tp[x]], id[x])) % p;
        x = fa[tp[x]];
    }
    if(dep[x] > dep[y]) swap(x, y); ans = (ans + query(id[x], id[y])) % p;
    return ans;
}
I void addson(int x, int k) {add(id[x], id[x] + son[x] - 1, k);}
I int qson(int x) {return query(id[x], id[x] + son[x] - 1);}
signed main() {
    int q; Read(n, q); Read(rt, p); for(int i = 1; i <= n; i++) Read(w[i]);
    for(int i = 1; i < n; i++) {int a, b; Read(a, b); e[a].pb(b); e[b].pb(a);}
    dfs1(rt, 0); dfs2(rt, rt);
    W(q--) {
        int op, x; Read(op, x);
        if(op == 1) {int y, z; Read(y, z); addpath(x, y, z % p);}
        if(op == 2) {int y; Read(y); writeln(qpath(x, y));}
        if(op == 3) {int z; Read(z); addson(x, z % p);}
        if(op == 4) writeln(qson(x));
    }
    return 0;
}

::::

例23

P3178 [HAOI2015] 树上操作

一眼树剖。对于操作 1 可以用线段树单点修改

由于一个点子树内点的 dfs 序都是连续的，可以直接线段树区间加。

操作 3 直接向上跳，每次加上这个点到链顶的和（直接 query）就好了。

挺唐的。

::::success[code]

#include<bits/stdc++.h>

#define int long long

namespace IO {
    inline int read() {
        int ret = 0, f = 1;char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-')  f = -f;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            ret = (ret << 1) + (ret << 3) + (ch ^ 48);
            ch = getchar();
        }
        return ret * f;
    }
    void write(int x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}

using namespace std;

const int maxn = 1e5 + 5;

vector<int> g[maxn];

int n, m;
int posval[maxn];

int fa[maxn], dep[maxn], siz[maxn], hvyson[maxn];
int top[maxn], id[maxn], rk[maxn], num;

namespace Segtree {
    int L[maxn << 2], R[maxn << 2], sum[maxn << 2], lazy[maxn << 2];

    void pushup(int x) {
        sum[x] = sum[x << 1] + sum[x << 1 | 1];
    }

    int len(int x) {
        return R[x] - L[x] + 1;
    }

    void pushdown(int x) {
        if (!lazy[x]) return;
        lazy[x << 1] += lazy[x];
        sum[x << 1] += len(x << 1) * lazy[x];
        lazy[x << 1 | 1] += lazy[x];
        sum[x << 1 | 1] += len(x << 1 | 1) * lazy[x];
        lazy[x] = 0;
    }

    void build(int l, int r, int x) {
        L[x] = l, R[x] = r;
        if (l == r) {
            sum[x] = posval[rk[l]];
            return;
        }
        int mid = l + r >> 1;
        build(l, mid, x << 1);
        build(mid + 1, r, x << 1 | 1);
        pushup(x);
    }

    void update(int l, int r, int x, int d) {
        if (l <= L[x] && R[x] <= r) {
            sum[x] += d * len(x);
            lazy[x] += d;
            return;
        }
        int mid = L[x] + R[x] >> 1;
        pushdown(x);
        if (l <= mid) update(l, r, x << 1, d);
        if (r > mid) update(l, r, x << 1 | 1, d);
        pushup(x);
    }

    int query(int l, int r, int x) {
        if (l <= L[x] && R[x] <= r) return sum[x];
        int mid = L[x] + R[x] >> 1, ans = 0;
        pushdown(x);
        if (l <= mid) ans += query(l, r, x << 1);
        if (r > mid) ans += query(l, r, x << 1 | 1); 
        return ans;
    }
}

using namespace IO;
using namespace Segtree;

void dfs1(int x, int fat) {
    dep[x] = dep[fat] + 1;siz[x] = 1;fa[x] = fat;

    for (auto v : g[x]) if (v ^ fat) {
        dfs1(v, x);
        siz[x] += siz[v];
        if (siz[v] > hvyson[x]) hvyson[x] = v;
    }
}

void dfs2(int x, int tp) {
    top[x] = tp;id[x] = ++num;rk[num] = x;

    if (hvyson[x]) dfs2(hvyson[x], tp);

    for (auto v : g[x]) if (v ^ hvyson[x] && v ^ fa[x]) dfs2(v, v);
}

//int solve(int x) {
//  if (x == 1) return posval[1];
//  int ans = 0;
////    cout << x << '\n';
//  
//  while (x != 1) {
////        cout << "nailong" << id[top[x]] << ' ' << id[x] << '\n';
//      ans += query(id[top[x]], id[x], 1);
////        cout << "nailong" << ans;
//      x = fa[top[x]];
//  }
//  
//  return ans;
//}

int solve(int x, int y) {
    int ans = 0;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        ans += query(id[top[x]], id[x], 1);
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    return ans += query(id[x], id[y], 1);
}

signed main() {
//  freopen("P3178_1.in", "r", stdin);
//  freopen("ans.out", "w", stdout);

    n = read(), m = read();
    for (int i = 1;i <= n;i++) posval[i] = read();
    for (int i = 1;i < n;i++) {
        int u = read(), v = read();
        g[u].push_back(v);
        g[v].push_back(u); 
    }

    dfs1(1, 1), dfs2(1, 1), build(1, n, 1);

//  for (int i = 1;i <= n;i++) cout << top[i] << '\n';

    while (m--) {
        int op = read(), x = read(), d;

        if (op == 1) {
            d = read();
            update(id[x], id[x], 1, d);
        }
        else if (op == 2) {
            d = read();
            update(id[x], id[x] + siz[x] - 1, 1, d);
        }
        else write(solve(1, x)), putchar(10);

//      for (int i = 1;i <= n;i++) cout << i << ' ' << id[i] << ' ', write(solve(id[i])), putchar(' ');
//      putchar(10);
    }
    return 0;
}

::::

例24

P2486 [SDOI2011] 染色

发现两个操作挺可以珂朵莉线段树维护的，如果在序列上做区间推平可以直接区间覆盖，查颜色段数量就是左中右维护。

上树直接加一个树剖就好了。

::::success[code]

#include<bits/stdc++.h>

namespace IO {
    inline int read() {
        int ret = 0, f = 1;char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -f;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            ret = (ret << 1) + (ret << 3) + (ch ^ 48);
            ch = getchar();
        }
        return ret * f;
    }
    void write(int x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}

using namespace IO;
using namespace std;

constexpr int maxn = 1e5 + 5;
constexpr int maxm = 1e5 + 5;

int n, m;

int tot, hd[maxn], to[maxm << 1], nxt[maxm << 1];
int num;
int fa[maxn], dep[maxn], siz[maxn], hvyson[maxn];
int top[maxn], id[maxn], rk[maxn];
int a[maxn];
int L[maxn << 2], R[maxn << 2], col[maxn << 2], lc[maxn << 2], rc[maxn << 2], lazy[maxn << 2];

void add(int u, int v) {
    tot++;
    nxt[tot] = hd[u];
    hd[u] = tot;
    to[tot] = v;
}

void pushup(int x) {
    lc[x] = lc[x << 1];
    rc[x] = rc[x << 1 | 1];
    col[x] = col[x << 1] + col[x << 1 | 1] - (rc[x << 1] == lc[x << 1 | 1]); 
}

void pushdown(int x) {
    if (!lazy[x]) return;
    lc[x << 1] = rc[x << 1] = lc[x << 1 | 1] = rc[x << 1 | 1] = lazy[x << 1] = lazy[x << 1 | 1] = lazy[x];
    col[x << 1] = col[x << 1 | 1] = 1;
    lazy[x] = 0;
}

void build(int l, int r, int x) {
    L[x] = l, R[x] = r;
    if (l == r) {
        col[x] = 1, lc[x] = rc[x] = a[rk[l]];
        return;
    }
    int mid = l + r >> 1;
    build(l, mid, x << 1);
    build(mid + 1, r, x << 1 | 1);
    pushup(x);
}

void update(int l, int r, int x, int d) {
    if (L[x] >= l && R[x] <= r) {
        lc[x] = rc[x] = lazy[x] = d;
        col[x] = 1;
        return;
    }
    pushdown(x);
    int mid = L[x] + R[x] >> 1;
    if (l <= mid) update(l, r, x << 1, d);
    if (r > mid) update(l, r, x << 1 | 1, d);
    pushup(x);
}

int query(int l, int r, int x) {
    if (L[x] >= l && R[x] <= r) return col[x];
    pushdown(x);
    int mid = L[x] + R[x] >> 1, ans = 0;
    if (l <= mid) ans += query(l, r, x << 1);
    if (r > mid) ans += query(l, r, x << 1 | 1);
//  cout << rc[x << 1] << ' ' << lc[x << 1 | 1] << '\n';
    if (l <= mid && r > mid && rc[x << 1] == lc[x << 1 | 1]) ans -= 1;
    return ans;
}

void dfs1(int u, int father) {
    fa[u] = father, dep[u] = dep[father] + 1, siz[u] = 1;
    for (int i = hd[u];i;i = nxt[i]) {
        int v = to[i];
        if (v == father) continue;
        dfs1(v, u);
        siz[u] += siz[v];
        if (siz[v] > siz[hvyson[u]]) hvyson[u] = v;
    }
}

void dfs2(int u, int nowtop) {
    top[u] = nowtop, id[u] = ++num, rk[num] = u;
    if (hvyson[u]) dfs2(hvyson[u], nowtop);
    for (int i = hd[u];i;i = nxt[i]) {
        int v = to[i];
        if (v == fa[u] || v == hvyson[u]) continue;
        dfs2(v, v);
    }
}

int getcol(int x, int pos) {
    if (L[x] == R[x]) return lc[x];
    pushdown(x);
    int mid = L[x] + R[x] >> 1;
    if (pos <= mid) return getcol(x << 1, pos);
    else return getcol(x << 1 | 1, pos);
}

int colson, colfa;
int solve(int x, int y) {
    int ans = 0;
    while (top[x] != top[y]) {
//      cout << x << ' ' << y << ' ' << ans << '\n';
        if (dep[top[x]] < dep[top[y]]) x ^= y ^= x ^= y;
        ans += query(id[top[x]], id[x], 1);
        colson = getcol(1, id[top[x]]);
        colfa = getcol(1, id[fa[top[x]]]);
        if (colson == colfa) ans -= 1;
        x = fa[top[x]];
    }
//  cout << x << ' ' << y << ' ' << ans << '\n';
    if (dep[x] > dep[y]) x ^= y ^= x ^= y;
//  cout << x << ' ' << y << ' ' << query(id[x], id[y], 1) << '\n';
    return ans += query(id[x], id[y], 1);
}

void Update(int x, int y, int d) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) x ^= y ^= x ^= y;
        update(id[top[x]], id[x], 1, d);
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) x ^= y ^= x ^= y;
    update(id[x], id[y], 1, d);
}

int main() {
    n = read(), m = read();
    for (int i = 1;i <= n;i++) a[i] = read();
    for (int i = 1;i < n;i++) {
        int u = read(), v = read();
        add(u, v), add(v, u);
    }

    dfs1(1, 0);
    dfs2(1, 1); 
    build(1, n, 1);

//  cout << '\n';
//  for (int i = 1;i <= n;i++) cout << id[i] << ' ';
//  cout << '\n';

    while (m--) {
        char op;cin >> op;
        int x = read(), y = read(), d;
        if (op == 'C') d = read(), Update(x, y, d);
        else write(solve(x, y)), putchar(10);
//      cout << '\n';
//      for (int i = 1;i <= n;i++) cout << getcol(1, i) << ' ';
//      cout << '\n';
    }
    return 0;
}

::::

主席树

前置知识：线段树1.5（动态开点）、权值线段树

主席树就是可持久化线段树，支持查询历史版本的信息。

P3919 【模板】可持久化线段树 1（可持久化数组）

有了可持久化数组，便可以实现很多衍生的可持久化功能。（例如：可持久化并查集）

如题，你需要维护这样的一个长度为 N 的数组，支持如下两种操作：

1. 在某个历史版本上修改某一个位置上的值。

2. 访问某个历史版本上的某一位置的值。

此外，每进行一次操作，就会生成一个新的版本。版本编号即为当前操作的编号（从 1 开始编号，版本 0 表示初始状态数组）。

对于操作 2，即为生成一个完全一样的版本，不作任何改动。即，询问生成的版本是询问所访问的那个版本的复制。

对于 100\% 的数据：

• 设当前是第 x 次操作，0 \leq v < x；

显然可以开 q 个线段树做对吧，但是太唐了空间直接爆蛋。

此时观察一下进行一个操作后线段树上发生的变化

上图是对一个线段树在编号 8 的节点进行操作时的变化。发现只有路径上 \mathcal{O}(\log n) 个节点发生了变化，于是只要在新树上建立这些节点，并把剩下空缺的位置连到原树上即可，如图所示。

其中新的根节点存到 root 数组里面，查询历史版本时只要从对应版本的根进去就可以查询历史版本了。

注意到每次操作至多产生 \mathcal{O}(\log n) 个节点，所以直接开 n << 5 大部分题就够用了。

代码有注释，采用一种我写的顺手的写法。

#include<bits/stdc++.h>

namespace IO {
    inline int read() {
        int ret = 0, f = 1;char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -f;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            ret = (ret << 1) + (ret << 3) + (ch ^ 48);
            ch = getchar();
        }
        return ret * f;
    }
    void write(int x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}

using namespace IO;
using namespace std;

const int maxn = 1e6 + 5;

int a[maxn], n, m;

namespace Segtree {
    #define Mid ((l + r) >> 1)

    int ls[maxn * 80], rs[maxn * 80], Val[maxn * 80];
    int rt[maxn], cnt;

    void build(int l, int r, int &x) {//这里x取址，把ls和rs传进去直接自己赋值
        x = ++cnt;
        if (l == r) {
            Val[x] = a[l];
            return;
        }

        build(l, Mid, ls[x]);
        build(Mid + 1, r, rs[x]);
    }

    int update(int l, int r, int x, int p, int c) {
        ls[cnt + 1] = ls[x], rs[cnt + 1] = rs[x], Val[cnt + 1] = Val[x];//先复制原节点的信息，根据修改的pos改左右儿子
        x = ++cnt;
        if (l == r) {
            Val[x] = c;
            return x;
        }

        if (p <= Mid) ls[x] = update(l, Mid, ls[x], p, c);
        else rs[x] = update(Mid + 1, r, rs[x], p, c);

        return x;
//顺带说一下，这里不取址的话不要忘记update的时候把返回值存到root里面
    }

    int query(int l, int r, int x, int p) {
        if (l == r) return Val[x];

        if (p <= Mid) return query(l, Mid, ls[x], p);
        else return query(Mid + 1, r, rs[x], p);
    }

    #undef Mid
}

using namespace Segtree;

int main() {
    n = read(), m = read();
    for (int i = 1;i <= n;i++) a[i] = read();

    build(1, n, rt[0]);

    for (int i = 1;i <= m;i++) {
        int v = read(), op = read(), p = read(), c;
        if (op == 1) c = read(), rt[i] = update(1, n, rt[v], p, c);
        else write(query(1, n, rt[v], p)), rt[i] = rt[v], putchar(10);
    }

    return 0;
}

例25

使用主席树（权值树）可以将序列的前缀和看成 n 个版本，通过差分回去的手法，两个版本相减，处理区间信息。

P2617 Dynamic Rankings

这是一个经典 trick，做法就是上文说的，先用主席树把区间 [l, r] 的信息搞出来，然后再在主席树上二分即可。

如果对主席树理解没问题的话应该不难，直接上 code。

::::success[code] 不是我怎么写的分块。

#include<bits/stdc++.h>

namespace IO {
    inline int read() {
        int ret = 0, f = 1;char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -f;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            ret = (ret << 1) + (ret << 3) + (ch ^ 48);
            ch = getchar();
        }
        return ret * f;
    }
    void write(int x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
} 

using namespace IO;
using namespace std;

const int maxn = 2e5 + 5;
const int maxv = 2e5 + 5;
const int maxk = 500 + 5;
struct Node {
    int op, x, y, l, r, k;
}q[maxn];

int n, m, tot;
int a[maxn], uni[maxv], b[maxn];

int f[maxn], vf[maxn], pre1[maxk][maxk], pre2[maxk][maxv];
int len, cnt, vlen, vcnt, L[maxk], R[maxk], vL[maxk], vR[maxk];

void init() {
    len = sqrt(n), vlen = sqrt(tot), cnt = n / len, vcnt = tot / vlen;

    for (int i = 1;i <= cnt;i++) {
        L[i] = (i - 1) * len + 1;
        R[i] = i * len;
        for (int j = L[i];j <= R[i];j++) f[j] = i;
    } 
    if (R[cnt] != n) {
        cnt++;
        L[cnt] = R[cnt - 1] + 1;R[cnt] = n;
        for (int i = L[cnt];i <= R[cnt];i++) f[i] = cnt;
    }

    for (int i = 1;i <= vcnt;i++) {
        vL[i] = (i - 1) * vlen + 1;
        vR[i] = i * vlen;
        for (int j = vL[i];j <= vR[i];j++) vf[j] = i;
    }
    if (vR[vcnt] != tot) {
        vcnt++;
        vL[vcnt] = vR[vcnt - 1] + 1;vR[vcnt] = tot;
        for (int i = vL[vcnt];i <= vR[vcnt];i++) vf[i] = vcnt;
    }

    for (int i = 1;i <= cnt;i++) {
        for (int j = 1;j <= vcnt;j++) pre1[i][j] = pre1[i - 1][j];
        for (int j = 1;j <= tot;j++) pre2[i][j] = pre2[i - 1][j];
        for (int j = L[i];j <= R[i];j++) pre1[i][vf[a[j]]]++, pre2[i][a[j]]++;
//      for (int j = 1;j <= vcnt;j++) cout << i << ' ' << pre1[i][j] << '\n';cout << "nailong\n";
//      for (int j = 1;j <= tot;j++) cout << i << ' ' << pre2[i][j] << '\n';cout << "nailong\n";
    }
}

void update(int x, int y) {
    int k = f[x], vkx = vf[a[x]], vky = vf[y];
    for (int i = k;i <= cnt;i++) pre1[i][vkx]--, pre1[i][vky]++, pre2[i][a[x]]--, pre2[i][y]++;
    a[x] = y;
}

int k1[maxk], k2[maxn];

int query(int l, int r, int k) {
    int lk = f[l], rk = f[r];
//  cout << lk << ' ' << rk << ' ' << len << '\n';

    if (lk == rk) {
        int v[maxk], Len = 0;
        for (int i = l;i <= r;i++) v[Len++] = a[i];
        nth_element(v, v + k - 1, v + Len);
        return v[k - 1];
    }

    memset(k1, 0, sizeof(k1)), memset(k2, 0, sizeof(k2));
//  cout << "nailong " << l << ' ' << R[lk] << ' ' << r << ' ' << L[rk];
    for (int i = l;i <= R[lk];i++) k1[vf[a[i]]]++, k2[a[i]]++;
    for (int i = L[rk];i <= r;i++) k1[vf[a[i]]]++, k2[a[i]]++;

//  cout << "nailong\n";
//  for (int i = 1;i <= vcnt;i++) cout << k1[i] << ' ';putchar(10);
//  for (int i = 1;i <= tot;i++) cout << k2[i] << ' ';putchar(10);
//  cout << vcnt << ' ' << cnt << '\n';
//  for (int i = 1;i <= vcnt;i++) cout << vL[i] << ' ' << vR[i] << '\n';

    int nowk = 1;
    for (;nowk <= vcnt;nowk++) {
        int sum = k1[nowk] + pre1[rk - 1][nowk] - pre1[lk][nowk];
//      cout << nowk << ' ' << vL[nowk] << ' ' << vR[nowk] << ' ' << sum << ' ' << k << "nailong\n";
        if (k <= sum) break;
        else k -= sum;
//      cout << nowk << "nailong\n";
    }
//  cout << nowk << ' ' << vL[nowk] << ' ' << vR[nowk] << '\n'; 

    for (int i = vL[nowk];i <= vR[nowk];i++) {
        int sum = k2[i] + pre2[rk - 1][i] - pre2[lk][i];
        if (k <= sum) return i;
        else k -= sum;
    }
}

int main() {
    n = read(), m = read();
    for (int i = 1;i <= n;i++) a[i] = read(), uni[++tot] = a[i];

    for (int i = 1;i <= m;i++) {
        char ch;cin >> ch;
        if (ch == 'Q') q[i].op = 1, q[i].l = read(), q[i].r = read(), q[i].k = read();
        if (ch == 'C') q[i].op = 2, q[i].x = read(), q[i].y = read(), uni[++tot] = q[i].y; 
    }

    sort(uni + 1, uni + tot + 1);
    tot = unique(uni + 1, uni + tot + 1) - uni - 1;

    for (int i = 1;i <= n;i++) {
        int num = lower_bound(uni + 1, uni + tot + 1, a[i]) - uni;
        b[num] = a[i];
        a[i] = num;
    }

    for (int i = 1;i <= m;i++) {
        if (q[i].op == 1) continue;
        int num = lower_bound(uni + 1, uni + tot + 1, q[i].y) - uni;
        b[num] = q[i].y;
        q[i].y = num;
    }

//  for (int i = 1;i <= n;i++) cout << a[i] << ' ';putchar(10);
//  for (int i = 1;i <= m;i++) cout << q[i].op << ' ' << q[i].x << ' ' << q[i].y << '\n';

    init();

    for (int i = 1;i <= m;i++) {
        if (q[i].op == 1) write(b[query(q[i].l, q[i].r, q[i].k)]), putchar(10);
        if (q[i].op == 2) update(q[i].x, q[i].y);
    }

    return 0;
}

::::

例26

原题找不到了。征集。

查询给定区间内出现次数等于 2 次的数。大概吧。

::::success[sol] 一个经典 trick：开两个数组，一个存当前数字的上一次出现的位置，另一个存当前数字的上上次出现的位置。

然后对第二个数组建主席树（权值树），查询 [l, r] 时直接查 r 版本的区间 [l, r] 的和即可。 ::::

线段树2

我觉得没什么用。只用到过 1 次。

P3373 【模板】线段树 2

每个节点维护区间和、区间加标记、区间乘标记。

注意标记下传的顺序：

假设该区间和为 S，进行若干加操作 a_i，若干乘操作 m_i，则所有操作类似于下式：

直接展开：

注意到 s 被所有乘操作乘了，所有加操作乘上了所有在它后面的乘操作。于是操作加法的时候直接打标记，乘 val 的时候把区间和与加标记都乘 val 即可。

标记下传的时候由于加法标记都被乘过了，所以要先乘再加。

#include<bits/stdc++.h>

#define int long long

namespace IO {
    inline int read() {
        int ret = 0, f = 1;char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -f;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            ret = (ret << 1) + (ret << 3) + (ch ^ 48);
            ch = getchar();
        }
        return ret * f;
    }
    void write(int x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}

using namespace std;
using namespace IO;

const int maxn = 1e5 + 5;

int a[maxn];
int L[maxn << 2], R[maxn << 2], lazyadd[maxn << 2], lazymul[maxn << 2], sum[maxn << 2];

int n, q, mod;

int len(int x) {
    return R[x] - L[x] + 1;
}

void pushup(int x) {
    sum[x] = (sum[x << 1] + sum[x << 1 | 1]) % mod;
}

void pushdown(int x) {
    if (lazymul[x] != 1) {
        sum[x << 1] *= lazymul[x];sum[x << 1] %= mod;
        sum[x << 1 | 1] *= lazymul[x];sum[x << 1 | 1] %= mod;
        lazyadd[x << 1] *= lazymul[x];lazyadd[x << 1] %= mod;
        lazyadd[x << 1 | 1] *= lazymul[x];lazyadd[x << 1 | 1] %= mod;
        lazymul[x << 1] *= lazymul[x];lazymul[x << 1] %= mod;
        lazymul[x << 1 | 1] *= lazymul[x];lazymul[x << 1 | 1] %= mod;
        lazymul[x] = 1;
    }
    if (lazyadd[x]) {
        sum[x << 1] += lazyadd[x] * len(x << 1);sum[x << 1] %= mod;
        sum[x << 1 | 1] += lazyadd[x] * len(x << 1 | 1);sum[x << 1 | 1] %= mod;
        lazyadd[x << 1] += lazyadd[x];lazyadd[x << 1] %= mod;
        lazyadd[x << 1 | 1] += lazyadd[x];lazyadd[x << 1 | 1] %= mod;
        lazyadd[x] = 0;
    }
}

void build(int l, int r, int x) {
    L[x] = l, R[x] = r, lazymul[x] = 1;
    if (l == r) {
        sum[x] = a[l];
        return;
    }
    int mid = l + ((r - l) >> 1);
    build(l, mid, x << 1);
    build(mid + 1, r, x << 1 | 1);
    pushup(x);
}

void updateadd(int l, int r, int x, int d) {
    if (l <= L[x] && R[x] <= r) {
        sum[x] += d * len(x);sum[x] %= mod;
        lazyadd[x] += d;lazyadd[x] %= mod;
        return;
    }
    pushdown(x);
    int mid = L[x] + ((R[x] - L[x]) >> 1);
    if (l <= mid) updateadd(l, r, x << 1, d);
    if (r > mid) updateadd(l, r, x << 1 | 1, d);
    pushup(x);
}

void updatemul(int l, int r, int x, int d) {
    if (l <= L[x] && R[x] <= r) {
        sum[x] *= d;sum[x] %= mod;
        lazymul[x] *= d;lazymul[x] %= mod;
        lazyadd[x] *= d;lazyadd[x] %= mod;
        return;
    }
    pushdown(x);
    int mid = L[x] + ((R[x] - L[x]) >> 1);
    if (l <= mid) updatemul(l, r, x << 1, d);
    if (r > mid) updatemul(l, r, x << 1 | 1, d);
    pushup(x);
}

int query(int l, int r, int x) {
    if (l <= L[x] && R[x] <= r) {
        return sum[x];
    }
    pushdown(x);
    int ans = 0ll;
    int mid = L[x] + ((R[x] - L[x]) >> 1);
    if (l <= mid) ans += query(l, r, x << 1), ans %= mod;
    if (r > mid) ans += query(l, r, x << 1 | 1), ans %= mod;
    return ans;
}

signed main() {
    n = read(), q = read(), mod = read();
    for (int i = 1;i <= n;i++) a[i] = read();

    build(1, n, 1);

    while (q--) {
        int op = read(), x = read(), y = read(), k;
        if (op == 1) {
            k = read();
            updatemul(x, y, 1, k);
        }
        else if (op == 2) {
            k = read();
            updateadd(x, y, 1, k);
        }
        else {
            write(query(x, y, 1)), puts("");
        }
    }

    return 0;
}

例27

AT_icpc2015autumn_h Donut Decoration

D 先生，是一个了不起的甜甜圈制造商。今天，他的厨房准备在日出之前制作甜甜圈。

D 先生瞬间完成了 N 个油炸圈饼。但是，这些油炸圈饼得先经过各种装饰任务才可以成为甜甜圈销售：填充奶油，浸入巧克力，打顶可爱，丰富多彩的东西等等。

有 K 个任务编号为 1 到 K，并且每一个甜甜圈都必须K个任务以 1,2,⋯,K 的顺序仅完成一次，才能成为销售物品。

D先生立即将 N 个甜甜圈排成一列,他似乎打算一次完成每个装饰任务。

但是，他在做什么呢？昨天晚上熬夜的D先生在每个任务只装饰了连续的一部分甜甜圈。这显然是一个错误！不仅如此，他还可能是做了几次同一任务，任务的顺序也是混乱的。

没有经过正确流程装饰的甜甜圈不能作为销售物品提供，所以他应该把它们丢掉。

幸运的是，有数据记录了他所做的一系列任务。数据包含以下信息：对于每个任务，装饰的甜甜圈的连续区间 [l,r] 和任务的ID x 。

请编写一个程序，列举可在展示柜中显示的甜甜圈的数量，作为销售给定记录数据的答案。

对于 100\% 的数据，1 \leq N, K, T \leq 200000，x_i \leq K, 1 \leq l_i \leq r_i \leq N

考虑最终只有 1 到 K 按照顺序排列才是一个合法的串。

不妨把他当做一个字符串，给他 Hash。

我们发现区间末尾加一个，Hash 值会乘上基加上 bias。

也就是线段树很经典的操作了。

复杂度一个 \log。

::::success[code]

#include<bits/stdc++.h>

#define int long long

namespace IO {
    inline int read() {
        int ret = 0, f = 1;char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -f;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            ret = (ret << 1) + (ret << 3) + (ch ^ 48);
            ch = getchar();
        }
        return ret * f;
    }
    void write(int x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}

using namespace std;
using namespace IO;

const int maxn = 2e5 + 5;
const int mod = 19260817;

int a[maxn];
int L[maxn << 2], R[maxn << 2], lazyadd[maxn << 2], lazymul[maxn << 2], sum[maxn << 2];

int n, k, T;

int len(int x) {
    return R[x] - L[x] + 1;
}

void pushup(int x) {
    sum[x] = (sum[x << 1] + sum[x << 1 | 1]) % mod;
}

void pushdown(int x) {
    if (lazymul[x] != 1) {
        sum[x << 1] *= lazymul[x];sum[x << 1] %= mod;
        sum[x << 1 | 1] *= lazymul[x];sum[x << 1 | 1] %= mod;
        lazyadd[x << 1] *= lazymul[x];lazyadd[x << 1] %= mod;
        lazyadd[x << 1 | 1] *= lazymul[x];lazyadd[x << 1 | 1] %= mod;
        lazymul[x << 1] *= lazymul[x];lazymul[x << 1] %= mod;
        lazymul[x << 1 | 1] *= lazymul[x];lazymul[x << 1 | 1] %= mod;
        lazymul[x] = 1;
    }
    if (lazyadd[x]) {
        sum[x << 1] += lazyadd[x] * len(x << 1);sum[x << 1] %= mod;
        sum[x << 1 | 1] += lazyadd[x] * len(x << 1 | 1);sum[x << 1 | 1] %= mod;
        lazyadd[x << 1] += lazyadd[x];lazyadd[x << 1] %= mod;
        lazyadd[x << 1 | 1] += lazyadd[x];lazyadd[x << 1 | 1] %= mod;
        lazyadd[x] = 0;
    }
}

void build(int l, int r, int x) {
    L[x] = l, R[x] = r, lazymul[x] = 1;
    if (l == r) {
        sum[x] = a[l];
        return;
    }
    int mid = l + ((r - l) >> 1);
    build(l, mid, x << 1);
    build(mid + 1, r, x << 1 | 1);
    pushup(x);
}

void updateadd(int l, int r, int x, int d) {
    if (l <= L[x] && R[x] <= r) {
        sum[x] += d * len(x);sum[x] %= mod;
        lazyadd[x] += d;lazyadd[x] %= mod;
        return;
    }
    pushdown(x);
    int mid = L[x] + ((R[x] - L[x]) >> 1);
    if (l <= mid) updateadd(l, r, x << 1, d);
    if (r > mid) updateadd(l, r, x << 1 | 1, d);
    pushup(x);
}

void updatemul(int l, int r, int x, int d) {
    if (l <= L[x] && R[x] <= r) {
        sum[x] *= d;sum[x] %= mod;
        lazymul[x] *= d;lazymul[x] %= mod;
        lazyadd[x] *= d;lazyadd[x] %= mod;
        return;
    }
    pushdown(x);
    int mid = L[x] + ((R[x] - L[x]) >> 1);
    if (l <= mid) updatemul(l, r, x << 1, d);
    if (r > mid) updatemul(l, r, x << 1 | 1, d);
    pushup(x);
}

int query(int l, int r, int x) {
    if (l <= L[x] && R[x] <= r) {
        return sum[x];
    }
    pushdown(x);
    int ans = 0ll;
    int mid = L[x] + ((R[x] - L[x]) >> 1);
    if (l <= mid) ans += query(l, r, x << 1), ans %= mod;
    if (r > mid) ans += query(l, r, x << 1 | 1), ans %= mod;
    return ans;
}

signed main() {
    n = read(), k = read();
//    for (int i = 1;i <= n;i++) a[i] = read();
    T = read();
    build(1, n, 1);

    while (T--) {
        int x = read(), y = read(), p = read();
        updateadd(x, y, 1, p);
        updatemul(x, y, 1, k + 1);
    }

    int answer = 0ll;
    for (int i = 1;i <= k;i++) answer = (answer + i) * (k + 1), answer %= mod;
//    cout << answer << '\n';

    int Ans = 0;
    for (int i = 1;i <= n;i++) Ans += query(i, i, 1) == answer;

    write(Ans);puts("");
    return 0;
}

::::

线段树3

咕咕咕。

陈亮舟线段树

陈亮舟线段树就应该陈亮舟讲。

从《楼房重建》出发浅谈一类使用线段树维护前缀最大值的算法

例28

P4198 楼房重建

::::success[code]

#include<bits/stdc++.h>

#define int long long

namespace IO {
    inline int read() {
        int ret = 0, f = 1;char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -f;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            ret = (ret << 1) + (ret << 3) + (ch ^ 48);
            ch = getchar();
        }
        return ret * f;
    }
    void write(int x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    } 
} 

using namespace std;
using namespace IO;
using db = long double;

const int maxn = 1e5 + 5;

int n, m;

namespace segtree {
    int L[maxn << 2], R[maxn << 2], rscnt[maxn << 2];
    db Max[maxn << 2];

    int calc(int x, db pre) {
        if (L[x] == R[x]) return Max[x] > pre;
        if (Max[x << 1] > pre) return calc(x << 1, pre) + rscnt[x];
        return calc(x << 1 | 1, pre);
    }

    void pushup(int x) {
        Max[x] = max(Max[x << 1], Max[x << 1 | 1]);
        rscnt[x] = calc(x << 1 | 1, Max[x << 1]);
    }

    void build(int l, int r, int x) {
        L[x] = l, R[x] = r;rscnt[x] = 1;
        if (l == r) return;

        int mid = l + r >> 1;

        build(l, mid, x << 1);
        build(mid + 1, r, x << 1 | 1);
    }

    void update(int pos, db d, int x) {
        if (L[x] == R[x]) {
            Max[x] = d;
            rscnt[x] = 1;
            return;
        }

        int mid = L[x] + R[x] >> 1;

        if (pos <= mid) update(pos, d, x << 1);
        else update(pos, d, x << 1 | 1);

        pushup(x);
    }
}

using namespace segtree;

signed main() {
    n = read(), m = read();
    build(1, n, 1);

    while (m--) {
        int x = read(), y = read();
        update(x, y * 1.0 / x, 1);
        write(calc(1, 0));putchar(10);
    }

    return 0;
}

::::

例29

CF671E Organizing a Race

树套树

前面的例 25 也可用树套树解决。

同时树套树似乎可以被分块套分块替代（？

例30

P3332 [ZJOI2013] K大数查询

权值线段树套区间线段树，做完了。

::::success[code]

#include<bits/stdc++.h>

#define int long long

namespace IO {
    inline int read() {
        int ret = 0, f = 1;char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -f;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            ret = (ret << 1) + (ret << 3) + (ch ^ 48);
            ch = getchar();
        }
        return ret * f;
    }
    void write(int x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}

using namespace std;
using namespace IO;

const int maxm = 5e7 + 5;
const int maxn = 5e4 + 5;

struct Node {
    int op, l, r, c;
}q[maxn];

int n, m;
int tot, uni[maxn];
int L[maxn << 2], R[maxn << 2], cnt, lazy[maxm];
int rt[maxn << 2], ls[maxm], rs[maxm], sum[maxm];

void pushup(int x) {
    sum[x] = sum[ls[x]] + sum[rs[x]];
}

void pushdown(int x, int l, int r) {
    if (!lazy[x]) return;
    if (!ls[x]) ls[x] = ++cnt;
    if (!rs[x]) rs[x] = ++cnt;
    lazy[ls[x]] += lazy[x];
    lazy[rs[x]] += lazy[x];
    int mid = l + r >> 1;
    sum[ls[x]] += lazy[x] * (mid - l + 1);
    sum[rs[x]] += lazy[x] * (r - mid);
    lazy[x] = 0;
}

void inupdate(int &root, int l, int r, int L, int R, int x) {
    if (!root) root = ++cnt;
    if (L <= l && R >= r) {
        sum[root] += (r - l + 1) * x;
        lazy[root] += x;
        return;
    }
    pushdown(root, l, r);
    int mid = l + r >> 1;
    if (L <= mid) inupdate(ls[root], l, mid, L, R, x);
    if (R > mid) inupdate(rs[root], mid + 1, r, L, R, x);
    pushup(root);
}

int inquery(int root, int l, int r, int L, int R) {
    if (!root) return 0;
    if (L <= l && R >= r) return sum[root];
    int mid = l + r >> 1, ans = 0;
    pushdown(root, l, r);
    if (L <= mid) ans += inquery(ls[root], l, mid, L, R); 
    if (R > mid) ans += inquery(rs[root], mid + 1, r, L, R);
    return ans;
}

void build(int l, int r, int x) {
    L[x] = l, R[x] = r;//rt[x] = ++cnt;
    if (l == r) return;
    int mid = l + r >> 1;
    build(l, mid, x << 1);
    build(mid + 1, r, x << 1 | 1);
}

void update(int l, int r, int d, int x) {
    inupdate(rt[x], 1, n, l, r, 1);
    if (L[x] == R[x]) return;
    int mid = L[x] + R[x] >> 1;
    if (d <= mid) update(l, r, d, x << 1);
    else update(l, r, d, x << 1 | 1);
}

int query(int l, int r, int d, int x) {
    if (L[x] == R[x]) return L[x];
    int rsum = inquery(rt[x << 1 | 1], 1, n, l, r);
    if (rsum < d) return query(l, r, d - rsum, x << 1);
    else return query(l, r, d, x << 1 | 1);
}

signed main() {
//  freopen("1.txt", "r", stdin);
//  freopen("out.out", "w", stdout);

    n = read(), m = read();
    for (int i = 1;i <= m;i++) {
        q[i].op = read(), q[i].l = read(), q[i].r = read(), q[i].c = read();
        if (q[i].op == 1) uni[++tot] = q[i].c;
    }

    sort(uni + 1, uni + 1 + tot);
    tot = unique(uni + 1, uni + 1 + tot) - uni - 1;

    for (int i = 1;i <= m;i++) if (q[i].op == 1) q[i].c = lower_bound(uni + 1, uni + 1 + tot, q[i].c) - uni;

//  for (int i = 1;i <= m;i++) if (q[i].op == 1) cerr << q[i].c << '\n';cerr << "nailong\n";

    build(1, tot, 1);

    for (int i = 1;i <= m;i++) {
        if (q[i].op == 1) update(q[i].l, q[i].r, q[i].c, 1);
        else write(uni[query(q[i].l, q[i].r, q[i].c, 1)]), putchar(10);
    }

    return 0;
}

::::

其他题不放了。

分块

分块是一个十分暴力的数据结构，也是我喜欢分块的原因。

当要维护的信息不满足区间可加性时，分块就可以十分霸道地草过去。

注意到上面例 28 可以轻松用分块草过。

::::success[code]

#include<bits/stdc++.h>

namespace IO {
    inline int read() {
        int ret = 0, f = 1;char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -f;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            ret = (ret << 1) + (ret << 3) + (ch ^ 48);
            ch = getchar();
        }
        return ret * f;
    }
    void write(int x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}

using namespace IO;
using namespace std;
using db = double;

const int maxn = 1e5 + 5;
const int maxp = 400;

int n, m, cnt;
int L[maxp], R[maxp], f[maxn], tot[maxp];
//vector<int> s[maxp];
db a[maxn], s[maxp][maxp];

void update(int k) {
    int l = L[k], r = R[k];
    db now = 0;
    tot[k] = 0;
    for (int i = l;i <= r;i++) if (a[i] > now) s[k][++tot[k]] = a[i], now = a[i];
}

void init() {
    cnt = sqrt(n);
    for (int i = 1;i <= cnt;i++) {
        L[i] = (i - 1) * cnt + 1;
        R[i] = i * cnt;
        for (int j = L[i];j <= R[i];j++) f[j] = i;
    }
    if (R[cnt] != n) {
        cnt++;
        L[cnt] = R[cnt - 1] + 1;
        R[cnt] = n;
        for (int i = L[cnt];i <= R[cnt];i++) f[i] = cnt;
    }
}

int solve() {
    db nowh = 0, ans = 0;
    for (int i = 1;i <= cnt;i++) {
//      vector<int>::iterator pos = upper_bound(s[i].begin(), s[i].end(), nowh);
        if (s[i][tot[i]] <= nowh) continue;
        int pos = upper_bound(s[i] + 1, s[i] + 1 + tot[i], nowh) - s[i];
        ans += tot[i] - pos + 1;
        nowh = s[i][tot[i]];
    }
    return ans;
}

int main() {
    n = read(), m = read();
    init();

    for (int i = 1;i <= m;i++) {
        int x = read(), y = read();
        a[x] = y * 1.0 / x;
//      cout << a[x];
        update(f[x]);
        write(solve());putchar(10);
    }

    return 0;
}

::::

分块是一种思想，顾名思义就是把序列分成很多块，通过维护整块的信息来减少查询的复杂度。

举个例子：假设我们要用分块做线段树 1。

假设块长为 B，那么把序列分成 \lceil \frac{n}{B} \rceil 块，然后维护整块的区间和。

修改的时候记录查询区间 [l, r] 两端点所在的块 lk，rk，暴力修改这两块，然后中间维护一个整块加的 tag。这样修改的复杂度就是 \mathcal{O}(B + \frac{n}{B})。

查询的时候同理，把两个端点所在块暴力查，中间的直接整块查，复杂度是 \mathcal{O}(B + \frac{n}{B}) 的。

此时运用小学学过的基本不等式就可以知道当且仅当 b = \sqrt{n} 时复杂度取到最小值 \mathcal{O}(n \sqrt n)。

::::success[code]

你说得对，但是分块不用脑子。

#include<bits/stdc++.h>

#define int long long

namespace IO {
    inline int read() {
        int ret = 0, f = 1;char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -f;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            ret = (ret << 1) + (ret << 3) + (ch ^ 48);
            ch = getchar();
        }
        return ret * f;
    }
    void write(int x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}

using namespace std;
using namespace IO;

const int maxn = 1e5 + 5;

int a[maxn], tag[maxn], sum[maxn], f[maxn], L[maxn], R[maxn];
int n, m, len;

int query(int l, int r) {
    int fr = f[l], to = f[r], ans = 0;
    if (fr == to) {
        for (int i = l;i <= r;i++) ans += a[i] + tag[i];
        return ans;
    }
    for (int i = fr + 1;i < to;i++) ans += sum[i];
    for (int i = l;i <= R[fr];i++) ans += a[i] + tag[fr];
    for (int i = L[to];i <= r;i++) ans += a[i] + tag[to];
    return ans;
}

void update(int l, int r, int k) {
    int fr = f[l], to = f[r];
    if (fr == to) {
        for (int i = l;i <= r;i++) a[i] += k, sum[fr] += k;     
        return;
    }
    for (int i = fr + 1;i < to;i++) tag[i] += k, sum[i] += k * (R[i] - L[i] + 1);
    for (int i = l;i <= R[fr];i++) a[i] += k, sum[fr] += k;
    for (int i = L[to];i <= r;i++) a[i] += k, sum[to] += k;
    return;
}

void init() {
    len = sqrt(n);
    for (int i = 1;i <= len;i++) {
        L[i] = (i - 1) * len + 1;
        R[i] = i * len;
        for (int j = L[i];j <= R[i];j++) {
            f[j] = i;
            sum[i] += a[j];
        }
    }
    if (R[len] != n) {
        len++;
        L[len] = R[len - 1] + 1;
        R[len] = n;
        for (int i = L[len];i <= R[len];i++) {
            f[i] = len;
            sum[len] += a[i];
        }
    }
}

signed main() {
    n = read(), m = read();
    for (int i = 1;i <= n;i++) a[i] = read();

    init();

    while (m--) {
        int op = read(), x = read(), y = read(), k;
        if (op == 1) {
            k = read();
            update(x, y, k);
        }
        else write(query(x, y)), puts("");
    }

    return 0;
}

::::

例31~39

LOJ 九题。网上题单讲解一大堆。很多讲的很好的，这里不赘述了。

关于块长

我记得 2013 年有一篇集训队论文是关于块长的，当时不知道哪里点进去的，现在也找不到了。

例40

P2801 教主的魔法

发现线段树好像做不了。于是尝试分块维护。

发现查询操作的答案不太好维护，所以新开一个数组维护每一块中排好序的数组，然后维护一个加 tag。因为如果整块加 k 的话并不会影响块内的相对顺序，所以每次修改至多会让两个块重排。

发现查询整块的时候可以直接二分大于等于 k - lazy 的位置。于是你就切掉了这道题。

::::success[code]

#include<bits/stdc++.h>

#define int long long

namespace IO {
    inline int read() {
        int ret = 0, f = 1;char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -f;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            ret = (ret << 1) + (ret << 3) + (ch ^ 48);
            ch = getchar();
        }
        return ret * f;
    }
    void write(int x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}

using namespace IO;
using namespace std;

const int maxn = 1e6 + 5;
#define INF 2147483647

int n, m;
int a[maxn], b[maxn], L[maxn], R[maxn], lazy[maxn], num[maxn];

void init() {
    int x = sqrt(n);
    for (int i = 1;i <= x;i++) {
        L[i] = (i - 1) * x + 1;
        R[i] = i * x;
        for (int j = L[i];j <= R[i];j++) num[j] = i;
        sort(b + L[i], b + R[i] + 1);
    }
    if (R[x] != n) {
        x++;
        L[x] = R[x - 1] + 1;
        R[x] = n;
        for (int i = L[x];i <= R[x];i++) num[i] = x;
        sort(b + L[x], b + R[x] + 1);
    }
    return;
}

void update(int l, int r, int x) {
    int lk = num[l], rk = num[r];

    if (lk == rk) {
        for (int i = l;i <= r;i++) a[i] += x;
        for (int i = L[lk];i <= R[lk];i++) b[i] = a[i];
        sort(b + L[lk], b + R[rk] + 1);
        return;
    }

    for (int i = l;i <= R[lk];i++) a[i] += x;
    for (int i = L[lk];i <= R[lk];i++) b[i] = a[i];

    for (int i = lk + 1;i < rk;i++) lazy[i] += x;

    for (int i = L[rk];i <= r;i++) a[i] += x;
    for (int i = L[rk];i <= R[rk];i++) b[i] = a[i];

    sort(b + L[lk], b + R[lk] + 1);
    sort(b + L[rk], b + R[rk] + 1);

    return;
}

int query(int l, int r, int k) {
    int lk = num[l], rk = num[r], cnt = 0;

    if (lk == rk) {
        for (int i = l;i <= r;i++) cnt += (a[i] + lazy[lk]) >= k;
        return cnt;
    }

    for (int i = lk + 1;i < rk;i++) {
        int le = L[i], ri = R[i], mid;
        while (le <= ri) {
            mid = le + ri >> 1; 
            if (b[mid] + lazy[i] < k) le = mid + 1;
            else ri = mid - 1;
        }
        cnt += R[i] - le + 1;
    }

    for (int i = l;i <= R[lk];i++) cnt += (a[i] + lazy[lk]) >= k;

    for (int i = L[rk];i <= r;i++) cnt += (a[i] + lazy[rk]) >= k;

    return cnt;     
}

signed main() {
    n = read(), m = read();
    for (int i = 1;i <= n;i++) a[i] = read(), b[i] = a[i];

    init();

    while (m--) {
        char op;cin >> op;
        int l = read(), r = read(), k = read();

        if (op == 'A') write(query(l, r, k)), puts("");
        else update(l, r, k);
    }

    return 0;
}

::::

例41

P5356 [Ynoi Easy Round 2017] 由乃打扑克

一道不用卡常的 Ynoi。太棒了。

如果你做了例 40，那么你就会发现这道题就是把查询大于等于 C 改成查第 k 大。那么可以想到二分答案。然后转化成例 40。

然后会发现如果把二分上下界设为 INF 的话会 T。那么把区间最大值和最小值求出来设为二分上下界即可。

你说得对，但是《未来日记》动画化就是依托，看得胃疼。

::::success[code]

#include<bits/stdc++.h>

#define int long long

namespace IO {
    inline int read() {
        int ret = 0, f = 1;char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -f;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            ret = (ret << 1) + (ret << 3) + (ch ^ 48);
            ch = getchar();
        }
        return ret * f;
    }
    void write(int x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}

using namespace IO;
using namespace std;

const int maxn = 1e5 + 5;
#define INF 2147483647

int n, m;
int a[maxn], b[maxn], L[maxn], R[maxn], lazy[maxn], num[maxn];

void init() {
    int x = sqrt(n);
    for (int i = 1;i <= x;i++) {
        L[i] = (i - 1) * x + 1;
        R[i] = i * x;
        for (int j = L[i];j <= R[i];j++) num[j] = i;
        sort(b + L[i], b + R[i] + 1);
    }
    if (R[x] != n) {
        x++;
        L[x] = R[x - 1] + 1;
        R[x] = n;
        for (int i = L[x];i <= R[x];i++) num[i] = x;
        sort(b + L[x], b + R[x] + 1);
    }
    return;
}

void update(int l, int r, int x) {
    int lk = num[l], rk = num[r];

    if (lk == rk) {
        for (int i = l;i <= r;i++) a[i] += x;
        for (int i = L[lk];i <= R[lk];i++) b[i] = a[i];
        sort(b + L[lk], b + R[rk] + 1);
        return;
    }

    for (int i = l;i <= R[lk];i++) a[i] += x;
    for (int i = L[lk];i <= R[lk];i++) b[i] = a[i];

    for (int i = lk + 1;i < rk;i++) lazy[i] += x;

    for (int i = L[rk];i <= r;i++) a[i] += x;
    for (int i = L[rk];i <= R[rk];i++) b[i] = a[i];

    sort(b + L[lk], b + R[lk] + 1);
    sort(b + L[rk], b + R[rk] + 1);

    return;
}

int check(int l, int r, int x) {
    int lk = num[l], rk = num[r];
    int cnt = 0;

    if (lk == rk) {
        for (int i = l;i <= r;i++) if (a[i] + lazy[lk] <= x) cnt++;
        return cnt;
    }

    for (int i = l;i <= R[lk];i++) if (a[i] + lazy[lk] <= x) cnt++;

    for (int i = lk + 1;i < rk;i++) {
        if (b[L[i]] + lazy[i] > x) continue;
        if (b[R[i]] + lazy[i] <= x) {
            cnt += R[i] - L[i] + 1;
            continue;
        }

        int left = L[i], right = R[i], mid; 
        while (left < right) {
            mid = (left + right >> 1) + 1;
            if (b[mid] + lazy[i] <= x) left = mid;  
            else right = mid - 1;
        }
        if (b[left] + lazy[i] <= x) cnt += left - L[i] + 1;
    }

    for (int i = L[rk];i <= r;i++) if (a[i] + lazy[rk] <= x) cnt++;

    return cnt;
}

int getmin(int l, int r) {
    int ans = INF, lk = num[l], rk = num[r];

    if (lk == rk) {
        for (int i = l;i <= r;i++) ans = min(ans, a[i] + lazy[lk]);
        return ans;
    }

    for (int i = l;i <= R[lk];i++) ans = min(ans, a[i] + lazy[lk]);

    for (int i = lk + 1;i < rk;i++) ans = min(ans, b[L[i]] + lazy[i]);

    for (int i = L[rk];i <= r;i++) ans = min(ans, a[i] + lazy[rk]);

    return ans;
}

int getmax(int l, int r) {
    int ans = -INF, lk = num[l], rk = num[r];

    if (lk == rk) {
        for (int i = l;i <= r;i++) ans = max(ans, a[i] + lazy[lk]);
        return ans;
    }

    for (int i = l;i <= R[lk];i++) ans = max(ans, a[i] + lazy[lk]);

    for (int i = lk + 1;i < rk;i++) ans = max(ans, b[R[i]] + lazy[i]);

    for (int i = L[rk];i <= r;i++) ans = max(ans, a[i] + lazy[rk]);

    return ans;
}

int query(int l, int r, int k) {
    if (k < 1 || k > r - l + 1) return -1;

    int lef = getmin(l, r), rig = getmax(l, r), ans = -1, mid;

    while (lef <= rig) {
        mid = lef + rig >> 1;
        if (check(l, r, mid) < k) lef = mid + 1;    
        else rig = mid - 1, ans = mid;
    }

    return ans;     
}

signed main() {
    n = read(), m = read();
    for (int i = 1;i <= n;i++) a[i] = read(), b[i] = a[i];

    init();

    while (m--) {
        int op = read(), l = read(), r = read(), k = read();

        if (op == 1) write(query(l, r, k)), puts("");
        else update(l, r, k);
    }

    return 0;
}

::::

例42

P4168 [Violet] 蒲公英

区间编号最小的众数，强制在线。

考虑一个查询的答案可能是什么。要不就是中间整块的众数，要不就是其他数字加上散块里面的数变成查询区间的众数。

于是维护一个前缀数组 t[i][j]，表示前 i 块内数字 j 出现的次数。

用一个临时数组把整块的数出现的次数存下来，散块直接暴力加进去，然后直接查就好了。注意不要使用任何 memcpy 和 memset，否则会 T 飞。

::::success[code]

放一个别人的 code。

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e4+5,maxk=505;

int n,m,a[maxn],mp[maxn],b[maxn],tot,cnt;
int f[maxn],l[maxk],r[maxk];
int p[maxk][maxk],num[maxk][maxn],fk[maxn];

void init(){
    cnt=sqrt(n);
    for(int i=1;i<=cnt;i++){
        l[i]=r[i-1]+1,r[i]=i*cnt;
        for(int j=l[i];j<=r[i];j++)f[j]=i;
    }
    if(cnt*cnt<n){
        cnt++;l[cnt]=r[cnt-1]+1;r[cnt]=n;
        for(int j=l[cnt];j<=r[cnt];j++)f[j]=cnt;
    }
    for(int i=1;i<=cnt;i++){
        memset(fk,0,sizeof(fk));
        int maxx=0,maxi=0;
        for(int j=i;j<=cnt;j++){
            for(int k=l[j];k<=r[j];k++){
                if(++fk[a[k]]>maxx)maxx=fk[a[k]],maxi=a[k];
                if(fk[a[k]]==maxx&&maxi>a[k])maxi=a[k];
            }
            p[i][j]=maxi;
        }
    }
    for(int i=1;i<=cnt;i++){
        for(int j=l[i];j<=r[i];j++)num[i][a[j]]++;
        for(int j=1;j<=n;j++)num[i][j]+=num[i-1][j];
    }
}

signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];
    sort(b+1,b+n+1);
    tot=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+tot+1,a[i])-b;

    init();
    int ans=0;
    memset(fk,0,sizeof(fk));

    while(m--){
        int l0,r0;
        scanf("%d%d",&l0,&r0);
        l0=(l0+ans-1)%n+1;r0=(r0+ans-1)%n+1;
        if(l0>r0)swap(l0,r0);
        int maxx=0;ans=0;

        int fl=f[l0],fr=f[r0];
        if(fl==fr){
            for(int i=l0;i<=r0;i++){
                int t=++fk[a[i]];
                if(t>maxx)maxx=t,ans=a[i];
                if(t==maxx&&ans>a[i])ans=a[i];

            }
            for(int i=l0;i<=r0;i++)fk[a[i]]--;
        }
        else{
            ans=p[fl+1][fr-1];
            maxx=num[fr-1][ans]-num[fl][ans];
            for(int i=l0;i<=r[fl];i++){
                int t=(++fk[a[i]])+num[fr-1][a[i]]-num[fl][a[i]];
                if(t>maxx)maxx=t,ans=a[i];
                if(t==maxx&&ans>a[i])ans=a[i];
            }
            for(int i=l[fr];i<=r0;i++){
                int t=(++fk[a[i]])+num[fr-1][a[i]]-num[fl][a[i]];
                if(t>maxx)maxx=t,ans=a[i];
                if(t==maxx&&ans>a[i])ans=a[i];
            }
            for(int i=l0;i<=r[fl];i++)fk[a[i]]--;
            for(int i=l[fr];i<=r0;i++)fk[a[i]]--;
        }
//      for(int i=1;i<=n;i++)if(fk[i])cout<<"#$%&";
        ans=b[ans];
        cout<<ans<<'\n';
    }

    return 0;
}

欸这个代码怎么用我的名字当数组名啊。

::::

例43

P3203 [HNOI2010] 弹飞绵羊

经典题，值得思考。

::::success[sol] 维护某个点弹出本块在哪里，要几次。修改直接修，查询整块跳。

操作复杂度 \mathcal{O}(\sqrt n)。

#include<bits/stdc++.h>

#define INF 2147483647

namespace IO {
    inline int read() {
        int ret = 0, f = 1;char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -f;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            ret = (ret << 1) + (ret << 3) + (ch ^ 48);
            ch = getchar();
        }
        return ret * f;
    }
    void write(int x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
} 

using namespace IO;
using namespace std;

const int maxn = 2e5 + 500;
const int qmaxn = 500 + 5;

int n, m;
int a[maxn], L[qmaxn], R[qmaxn], num[maxn], nxtk[maxn], step[maxn];

void init() {
    int x = sqrt(n);
    for (int i = 1;i <= x;i++) {
        L[i] = (i - 1) * x + 1;
        R[i] = x * i;
        for (int j = R[i];j >= L[i];j--) {
            num[j] = i;
            step[j] = step[j + a[j]] + 1;
            nxtk[j] = (j + a[j] > R[i]) ? j + a[j] : nxtk[j + a[j]];
        }
    } 

    if (R[x] != n) {
        x++;    
        L[x] = R[x - 1] + 1;
        R[x] = n;
        for (int i = R[x];i >= L[x];i--) {
            num[i] = x;
            step[i] = step[i + a[i]] + 1;
            nxtk[i] = (i + a[i] > R[x]) ? i + a[i] : nxtk[i + a[i]];
        }
    }

    return;
}

void update(int x, int k) {
    int l = L[num[x]], r = R[num[x]];
    a[x] = k;

    for (int i = r;i >= l;i--) {
        if (i + a[i] > r) {
            nxtk[i] = i + a[i];
            step[i] = 1;
        }
        else {
            nxtk[i] = nxtk[i + a[i]];
            step[i] = step[i + a[i]] + 1;
        }
    }

    return;
}

int query(int x) {
    int ans = 0;
    while (x <= n) {
        ans += step[x];
        x = nxtk[x];
    }
    return ans;
}

int main() {

//  freopen("P3203_1.in", "r", stdin);
//  freopen("P3203_1.txt", "w", stdout);

    n = read();
    for (int i = 1;i <= n;i++) a[i] = read();

    init();

    m = read();
    while (m--) {
        int op = read(), j = read(), k;
        if (op == 1) write(query(j + 1)), puts("");//!!!!!11111
        else k = read(), update(j + 1, k);
    }

    return 0;
}

::::

例44

P7446 [Ynoi2007] rfplca

发现每个节点的祖先们都只会是编号小于等于自己的点，所以我们找 LCA 向上跳的时候，在数组中都是向左跳。

于是变成了弹飞绵羊。类似的，预处理跳出本块到哪里。然后类似倍增 LCA 查询就好了。

然而并没有结束，注意到 Ynoi，必定卡常。

注意到如果对整块修改次数大于块长时块内每个数必定一次跳出本块。此时打上标记，不用暴力修改，跳出块的位置直接等于 fa 就好了。

::::warning[my code] 没有卡常，一直 T 48pts。

#include<bits/stdc++.h>

#define int long long
//#define INF 2147483647
#define HDF_LOVES_YDMY 1
#define getchar getchar_unlocked

namespace IO {
    inline int read() {
        int ret = 0, f = 1;char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -f;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            ret = (ret << 1) + (ret << 3) + (ch ^ 48);
            ch = getchar();
        }
        return ret * f;
    }

//  const int SIZE = 1 << 14;
//  char getc() {
//      static char buf[SIZE], *begin = buf, *end = buf;
//      if (begin == end) {
//          begin = buf;
//          end = buf + fread(buf, 1, SIZE, stdin);
//      }
//      return *begin++;
//  }
//  
//  int read() {
//      int ret = 0, f = 1;char ch = getc();
//      while (!isdigit(ch)) f |= ch == '-', ch = getc();
//      while (isdigit(ch)) ret = (ret << 1) + (ret << 3) + (ch ^ 48), ch = getc();
//      return ret * f;
//  }

    void write(int x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
} 

using namespace IO;
using namespace std;

const int maxn = 4e5 + 500;
//const int qmaxn = 500 + 5;

int n, m;
int a[maxn], L[maxn], R[maxn], num[maxn], f[maxn], lazy[maxn], lastans;

void init() {
    int x = sqrt(n);

    for (int i = 1;i <= x;i++) {
        L[i] = (i - 1) * x + 1;
        R[i] = i * x;
        for (int j = L[i];j <= R[i];j++) {
            num[j] = i;
            f[j] = (a[j] < L[i]) ? a[j] : f[a[j]];
        }
    }

    if (R[x] != n) {
        x++;
        L[x] = R[x - 1] + 1;
        R[x] = n;
        for (int i = L[x];i <= R[x];i++) {
            num[i] = x;
            f[i] = (a[i] < L[x]) ? a[i] : f[a[i]];
        }
    }

    return;
}

void renew(int nowk) {
//  if (!lazy[nowk]) return;

    for (int i = L[nowk];i <= R[nowk];i++) {
        a[i] = max(a[i] - lazy[nowk], 1ll);
        (a[i] < L[nowk]) ? f[i] = a[i] : f[i] = f[a[i]];
//      int fa = max(a[i] - lazy[num[i]], 1ll);
//      (fa < L[nowk]) ? f[i] = fa : f[i] = f[fa];
    }

    lazy[nowk] = 0;

    return;
}

void update(int l, int r, int x) {
    int lk = num[l], rk = num[r];

    if (lk == rk) {
        for (int i = l;i <= r;i++) a[i] -= x;
//      renewf(l, r);   
        return;
    } 

    for (int i = l;i <= R[lk];i++) a[i] -= x;

    for (int i = lk + 1;i < rk;i++) lazy[i] += x;

    for (int i = L[rk];i <= r;i++) a[i] -= x;

//  renewf(l, r);

    return; 
}

int query(int x, int y) {
    int xk, yk;

    while (HDF_LOVES_YDMY) { 

        xk = num[x], yk = num[y];

        if (x == 1 || y == 1) return 1;
        if (x == y) return x;
        if (max(a[y] - lazy[yk], 1ll) == x) return x;
        if (max(a[x] - lazy[xk], 1ll) == y) return y;

//      renewf(min(x, y) - sqrt(n) - 1, max(x, y));

        if (xk != yk) (xk < yk) ? (renew(yk), y = f[y]) : (renew(xk), x = f[x]);
        else {
            renew(xk);
            if (f[x] == f[y]) {
                while (HDF_LOVES_YDMY) {
                    if (x == 1 || y == 1) return 1; 
                    if (x == y) return x;
    //                  int ax = max(a[x] - lazy[xk], 1ll), ay = max(a[y] - lazy[yk], 1ll);
                    if (a[x] == a[y]) return a[x];
                    else if (x < y) y = a[y];
                    else x = a[x];
                }
            }
            else x = f[x], y = f[y];
        }
    } 
}

signed main() {
    n = read(), m = read();
    a[1] = 1;L[0] = 1, R[0] = 1;num[1] = 0;
    for (int i = 2;i <= n;i++) a[i] = read();

    init();

    while (m--) {
        int op = read(), j = read(), k = read(), l;
        if (op == 1) l = read(), update(j ^ lastans, k ^ lastans, l ^ lastans);
        else lastans = query(j ^ lastans, k ^ lastans), /*printf("%lld", lastans)*/write(lastans), puts("");
    }

    return 0;
}

::::

::::success[code] 放一个 @bbbzzx 大神的 code。

#include<bits/stdc++.h>
#define int long long
#define db double
#define inf 1e18
#define gc getchar
#define pc putchar
#define lowbit(x) (x)&-(x)
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=gc();
    while(!isdigit(ch)){
        if(ch=='-') f=-f;
        ch=gc();
    }
    while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=gc();
    return x*f;
}
inline void write(int x){
    if(x<0) pc('-'),x=-x;
    if(x>9) write(x/10);
    pc(x%10+'0');
}
const int N=4e5+500;
const int M=750;
int n,m,a[N];
int block,num,st[M],ed[M];
int pos[N],lazy[M];
int fa[N],maxx[M];
void pushdown(int x){
    for(int i=st[x];i<=ed[x];i++) a[i]=max(a[i]-lazy[x],1ll);
    lazy[x]=0; 
}
void update(int x){
    maxx[x]=0;
    for(int i=st[x];i<=ed[x];i++){
        maxx[x]=max(maxx[x],a[i]);
        if(a[i]<st[x]) fa[i]=a[i];
        else fa[i]=fa[a[i]];
    }
}
void init(){
    block=sqrt(max(n-1,1ll));
    num=(n-2)/block+2;
    st[1]=ed[1]=1;
    for(int i=2;i<=num;i++){
        st[i]=(i-2)*block+2;
        ed[i]=min((i-1)*block+1,n);
    }
    pos[1]=1;
    for(int i=2;i<=n;i++) pos[i]=(i-2)/block+2;
    for(int i=2;i<=num;i++) update(i);
}
void modify(int l, int r, int x){
    int p=pos[l],q=pos[r];
    if(p==q){
        for(int i=l;i<=r;i++) a[i]=max(a[i]-x,1ll);
        update(p);
    }else{
        for(int i=l;i<=ed[p];i++) a[i]=max(a[i]-x,1ll);
        update(p);
        for(int i=st[q];i<=r;i++) a[i]=max(a[i]-x,1ll);
        update(q);
        for(int i=p+1;i<q;i++){
            lazy[i]+=x;
            maxx[i]=max(maxx[i]-lazy[i],1ll);
            if(maxx[i]>=st[i]){
                pushdown(i);
                update(i);
            }
        }
    }
}
inline int query(int u, int v){
    while(u!=1&&v!=1){
        int p=pos[u],q=pos[v],nxtu,nxtv;
        if(maxx[p]<st[p]) nxtu=max(a[u]-lazy[p],1ll);
        else{
            if(lazy[p]){
                pushdown(p);
                update(p);
            }
            nxtu=fa[u];
        }
        if(maxx[q]<st[q]) nxtv=max(a[v]-lazy[q],1ll);
        else{
            if(lazy[q]){
                pushdown(q);
                update(q);
            }
            nxtv=fa[v];
        }
        if(p>q) u=nxtu;
        else if(p<q) v=nxtv;
        else{
            if(nxtu==nxtv) break;
            else{
                if(pos[nxtu]>pos[nxtv]) u=nxtu;
                else v=nxtv;
            }
        }
    }
    if(u==1||v==1) return 1ll;
    pushdown(pos[u]);
    while(u!=v){
        if(u<v) swap(u,v);
        u=a[u];
    }
    return u;
}
signed main(){
    n=read(),m=read();
    a[1]=1;
    for(int i=2;i<=n;i++) a[i]=read();
    init();
    int ans=0;
    while(m--){
        int op=read();
        if(op==1){
            int l=read(),r=read(),x=read();
            l^=ans,r^=ans,x^=ans;
            modify(l,r,x);
        }else{
            int u=read(),v=read();
            u^=ans,v^=ans;
            ans=query(u,v);
            write(ans);
            puts("");
        }
    }
    return 0;
}

::::

值域分块

就是把分块当桶用，类比区间线段树和权值线段树。

真没什么好讲，放个别人的博客。值域分块入门

其实很多东西都可以分块嗯做，所以经常会看见题解区有人说“大家好我非常喜欢暴力数据结构所以我就用分块过了这道题”。

熟练使用分块是很好的。可惜我不会。

莫队

学了分块之后必不可少的就是莫队了。

个人认为白书里面讲的最好。废话莫队讲的莫队当然是最好的啦。

好文 侵删。

珂朵莉树（odt）

在分块之后终于学到了比分块更加美丽暴力的数据结构。一是因为它比分块更加暴力，二是珂朵莉本来就很美丽。

跟 OI-wiki 学的。

简介

珂朵莉树（odt），又名颜色段均摊。它维护的每一个区间里都是相同的数据。例如序列 1 2 2 3 4 1 在 odt 中就使用 5 个区间维护。

由于 odt 需要频繁的插入和删除区间，所以通常选择 set 维护。set 里是一些结构体维护的区间，又因为区间的数据需要修改，所以区间的数值 v 前面要加上关键字 mutable。

下面是定义 odt 的示例。

struct Node {
    int l, r;
    mutable int v;

    Node(int x, int y, int z) {
        l = x, r = y, v = z;
    }

    bool operator < (const Node & x) const {
        return l < x.l;
    } 
};

set<Node> odt;

初始化的时候因题目而异，有时插入一个 1 到 n 的区间（值是题目给定的）。有时把每个数当作一个长度为 1 的区间插入进去。

然后是 odt 的核心操作 split 和 assign。

split 操作

split 做的事就是找到 x 所在的区间 [l,r]，并且把这个区间分裂成 [l,x - 1] 和 [x,r]，然后返回分裂完的右区间的迭代器。

首先查找 x 所在的区间，直接用 lower_bound 暴力找就好了（对就是这么暴力）。由于用区间的 l 作为第一关键字，找到的区间要么左端点是 x，此时就不用分裂了，直接 return；要么是包含 x 的区间的下一个区间，此时上一个区间就是要找的区间，迭代器自减。

找到区间之后直接把它 erase 掉，再插入 [l,x - 1] 和 [x,r]。

于是 split 操作结束。

auto split(int x) {
    auto it = odt.lower_bound({x, 0, 0});//按第一关键字排序，后面两个随便填
    if (it != odt.end() && it -> l == x) return it;//如果当前区间的左端点就是这个区间
    it--;//否则要找的就是上一个区间
    int l = it -> l, r = it -> r, v = it -> v;//要先把当前区间的信息记录下来，erase 掉后就用不了了。   
    odt.erase(it);
    odt.insert({l, x - 1, v});
    return odt.insert({x, r, v}).first;
}

assign 操作

此操作完成的事很简单，就是把区间 [l,r] 推平，并赋值成 v。

这个操作直接利用 split 完成就很简单，具体见代码注释。

void assign(int l, int r, int v) {
    auto itr = split(r + 1), itl = split(l);
//注意先split(r + 1)，再split(l)，因为如果先把左边的区间 erase 掉再找右边的区间会出问题
//再注意理解为什么是 r + 1 而不是 r
//需要操作的区间是到 r 的，所以 split 时为了把 r 点包含进去应该 split 到 r + 1。
    odt.erase(itl, itr);
    odt.insert({l, r, v});
}

其他操作

其他操作就是题目中给定的各种操作。先把要操作的区间 split 出来，再进行各种修改和查询操作就好了。

void myfunction(int l, int r, int x) {
    auto itr = split(r + 1), itl = split(l);
    for (;itl != itr;itl++) {
        //各种操作各种操作各种操作
    }
}

odt 的应用

CF896C Willem, Chtholly and Seniorious

珂朵莉起源题对吧。

对于操作 1 和 2 是很好用珂朵莉树维护的。考虑操作 3 和 4 怎么完成（虽然似乎不用怎么考虑）。

对于操作 3，我们直接将每个值和这个值的个数加到 vector 里面，然后直接 sort 一遍，接着遍历一遍找到 k 大值。

对于操作 4 （k 方和）就是很经典的求和操作了。对于每一个值分别求它的幂，然后加起来就好了。

于是这道题迎刃而解。

::::success[code]

#include<bits/stdc++.h>

#define int long long

namespace IO {
    inline int read() {
        int ret = 0, f = 1;char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -f;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            ret = (ret << 1) + (ret << 3) + (ch ^ 48);
            ch = getchar();
        }
        return ret * f;
    }
    void write(int x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}

using namespace IO;
using namespace std;

constexpr int maxn = 1e5 + 5;
typedef pair<int, int> PII;

int n, m, seed, Vmax;

struct Node {
    int l, r;
    mutable int v;

    Node(int x, int y, int z) {
        l = x, r = y, v = z;
    }

    bool operator < (const Node & x) const {
        return l < x.l;
    } 
};

set<Node> odt;

auto split(int x) {
    auto it = odt.lower_bound({x, 0, 0});
    if (it != odt.end() && it -> l == x) return it;
    it--;
    int l = it -> l, r = it -> r, v = it -> v;
    if (r < x) return odt.end();    
    odt.erase(it);
    odt.insert({l, x - 1, v});
    return odt.insert({x, r, v}).first;
}

void assign(int l, int r, int v) {
    auto itr = split(r + 1), itl = split(l);
    odt.erase(itl, itr);
    odt.insert({l, r, v});
}

void add(int l, int r, int x) {
    auto itr = split(r + 1), itl = split(l);
    for (;itl != itr;itl++) itl -> v += x;
}

int len(auto it) {
    return it -> r - it -> l + 1;
}

int qpow(int a, int p, int mod) {
    int ans = 1;a %= mod;
    while (p) {
        if (p & 1) ans *= a, ans %= mod;
        a *= a, a %= mod;
        p >>= 1;
    }
    return ans;
}

int query(int l, int r, int p, int mod) {
//  cout << l << ' ' << r << ' ' << p << ' ' << mod;
    auto itr = split(r + 1), itl = split(l);
    int cnt = 0;
    for (;itl != itr;itl++) cnt = (cnt + (qpow(itl -> v, p, mod) % mod) * len(itl)) % mod;
    return cnt;
}

int kth(int l, int r, int k) {
    vector<PII> a;
    auto itr = split(r + 1), itl = split(l);
    for (auto iter = itl;iter != itr;iter++) a.push_back(PII(iter -> v, (iter -> r) - (iter -> l) + 1));
    sort(a.begin(),a.end());
    for (auto iter = a.begin();iter != a.end();iter++) {
        k -= iter -> second;
        if (k <= 0) return iter -> first;
    }
    return -1;
}

int rnd() {
    int ret = seed;
    seed = (seed * 7 + 13) % (long long)(1e9 + 7);
    return ret;
}

signed main() {
    n = read(), m = read(), seed = read(), Vmax = read();
    for (int i = 1;i <= n;i++) odt.insert(Node(i, i, (rnd() % Vmax) + 1));

    while (m--) {
        int op = (rnd() % 4) + 1, l = (rnd() % n) + 1, r = (rnd() % n) + 1, x, y;
        if (l > r) swap(l, r);
        if (op == 3) x = (rnd() % (r - l + 1)) + 1;
        else x = (rnd() % Vmax) + 1;
        if (op == 4) y = (rnd() % Vmax) + 1;

        switch (op) {
            case 1 : {add(l, r, x);break;}
            case 2 : {assign(l, r, x);break;}
            case 3 : {write(kth(l, r, x)), putchar(10);break;}
            case 4 : {write(query(l, r, x, y)), putchar(10);break;}
            default : break;
        }

//      for (auto i : odt) cout << i.l << ' ' << i.r << ' ' << i.v << '\n';
    }

    return 0;
}

::::

注意这个快速幂里面底数先要模模数，否则会 WA #3。

P3071 [USACO13JAN] Seating G

什么？最左的连续空位？还有区间推平？ 于是自然想到珂朵莉树解决。

初始化时先插入一个 1 到 n，值为 0 的区间，表示初始全为空座位。

找最左的连续 a 个空位，直接暴力循环一遍就好了，别忘了把相邻的空区间的长度累加起来，否则就会 WA 20pts。

客人离开就是区间推平，直接 assign 即可。

::::success[code]

#include<bits/stdc++.h>

namespace IO {
    inline int read() {
        int ret = 0, f = 1;char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -f;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            ret = (ret << 1) + (ret << 3) + (ch ^ 48);
            ch = getchar();
        }
        return ret * f;
    }
    void write(int x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}

using namespace IO;
using namespace std;

constexpr int maxn = 5e5 + 5;

int n, m;

struct Node {
    int l, r;
    mutable int v;

    Node(int L, int R, int V) {l = L, r = R, v = V;}

    bool operator < (const Node & x) const {
        return l < x.l;
    }
};

set<Node> odt;

auto split(int x) {
    auto it = odt.lower_bound(Node(x, 0, 0));
    if (it != odt.end() && it -> l == x) return it;
    it--;
    int l = it -> l, r = it -> r, val = it -> v;
    if (r < x) return odt.end();
    odt.erase(it);
    odt.insert(Node(l, x - 1, val));
    return odt.insert(Node(x, r, val)).first; 
}

void Assign(int l, int r, int val) {
    auto itr = split(r + 1), itl = split(l);
    odt.erase(itl, itr);
    odt.insert(Node(l, r, val));
}

int len(auto x) {
    return x.r - x.l + 1;
}

int update(int x) {
//  auto rit = split(y + 1), lit = split(x);
//  for (auto i : odt) {
//      if (i.v == 1) continue;
//      if (len(i) >= x) {
//          Assign(i.l, i.l + x, 1);
//          return 0;
//      }
//  }

    int tot = 0, cnt = 0, frm = -1;
    for (auto i : odt) {
        if (i.v == 0) {
            cnt += len(i);
            if (frm == -1) frm = i.l;
        }
        else cnt = 0, frm = -1;
        tot = max(tot, cnt);
        if (tot >= x) {
            Assign(frm, frm + x - 1, 1);
            return 0;
        }
    }
    return 1;
}

int main() {
    n = read(), m = read();

    odt.insert(Node(1, n, 0));

    int ans = 0;
    while (m--) {
        char ch;cin >> ch;
        int x = read(), y;
        if (ch == 'A') ans += update(x);
        else y = read(), Assign(x, y, 0); 
//      for (auto i : odt) {
//          cout << i.l << ' ' << i.r << ' ' << i.v << '\n';
//      }
    }

    write(ans), putchar(10);
    return 0;
}

::::

P4344 [SHOI2015] 脑洞治疗仪

众所周知的，这道题被卡了对吧。所以这是 100 pts 做法（unaccepted）。

操作 0 就是推平，操作 1 用 vector 记下来再填进去（注意 split 和 erase 之间的顺序），操作 2 就类似上一题的做法统计最长的空区间。

::::success[code]

#include<bits/stdc++.h>

namespace IO {
    inline int read() {
        int ret = 0, f = 1;char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -f;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            ret = (ret << 1) + (ret << 3) + (ch ^ 48);
            ch = getchar();
        }
        return ret * f;
    }
    void write(int x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}

using namespace IO;
using namespace std;

constexpr int maxn = 2e5 + 5;

int n, m;

struct Node {
    int l, r;
    mutable int v;

    Node(int L, int R, int V) {
        l = L, r = R, v = V;
    }

    bool operator < (const Node & x) const {
        return l < x.l;
    }
};

set<Node> odt;

auto split(int x) {
    auto it = odt.lower_bound(Node(x, 0, 0));
    if (it != odt.end() && it -> l == x) return it;
    it--;
    int l = it -> l, r = it -> r, val = it -> v;
    if (r < x) return odt.end();
    odt.erase(it);
    odt.insert(Node(l, x - 1, val));
    return odt.insert(Node(x, r, val)).first; 
}

void Assign(int l, int r, int val) {
    auto itr = split(r + 1), itl = split(l);
    odt.erase(itl, itr);
    odt.insert(Node(l, r, val));
}

int len(auto x) {
    return x -> r - x -> l + 1;
}

void update(int l1, int r1, int l2, int r2) {
    auto rit = split(r1 + 1), lit = split(l1), L = lit;
//  int cnt = 0;
//  for (;lit != rit;lit++) if (lit -> v == 1) cnt += len(lit), lit -> v = 0;

    int cnt = 0;
    for (;lit != rit;lit++) if (lit -> v == 1) cnt += len(lit);
    Assign(l1, r1, 0);
//  for (auto i : odt) cout << i.l << ' ' << i.r << ' ' << i.v << '\n';
//  putchar(10);
    rit = split(r2 + 1), lit = split(l2);
    for (;lit != rit;lit++) {
        if (lit -> v == 1) continue;
        if (cnt >= len(lit)) cnt -= len(lit), lit -> v = 1;
        else {
            if (cnt != 0) Assign(lit -> l, lit -> l + cnt - 1, 1);
            break;
        }
    }
}

int perform(int l, int r) {
    auto rit = split(r + 1), lit = split(l);
    int ans = 0, cnt = 0;
    for (;lit != rit;lit++) {
//      cout << lit -> l << ' ' << lit -> r << ' ' << lit -> v << '\n';
        if (lit -> v == 0) cnt += len(lit);
        else ans = max(ans, cnt), cnt = 0;
    }
    ans = max(ans, cnt);
    return ans;
}

int main() {
    n = read(), m = read();

    odt.insert(Node(1, n + 1, 1));

    while (m--) {
        int op = read(), x = read(), y = read();
        if (op == 0) Assign(x, y, 0);
        if (op == 1) {
            int u = read(), v = read();
            update(x, y, u, v);
        }
        if (op == 2) write(perform(x, y)), putchar(10);
    }

    return 0;
}

::::

P7134 小 H 的序列

https://www.luogu.com.cn/problem/P7134。

这个查询操作看起来十分像珂朵莉树的起源题对吧，所以自然想到珂朵莉树解决。

操作一似乎不能直接推平，考虑把每个区间转存到数组里面，再把操作区间删掉，然后把相邻且值相同的区间合并之后再加到珂朵莉树中。

询问操作就是很典的珂树了，把每个树里的的区间一起计算 v ^ {p}，再乘上区间长度，累加到答案。

::::success[code]

#include<bits/stdc++.h>

#define int unsigned long long

namespace IO {
    inline int read() {
        int ret = 0, f = 1;char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -f;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            ret = (ret << 1) + (ret << 3) + (ch ^ 48);
            ch = getchar();
        }
        return ret * f;
    }
    void write(int x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}

using namespace IO;
using namespace std;

constexpr int maxn = 1e5 + 5;

int n, m;

struct Node {
    int l, r;
    mutable int v;

//  Node(int x, int y, int z) {
//      l = x, r = y, v = z;
//  }

    bool operator < (const Node & x) const {
        return l < x.l;
    } 
};

set<Node> odt;

auto split(int x) {
    auto it = odt.lower_bound({x, 0, 0});
    if (it != odt.end() && it -> l == x) return it;
    it--;
    int l = it -> l, r = it -> r, v = it -> v;
    if (r < x) return odt.end();    
    odt.erase(it);
    odt.insert({l, x - 1, v});
    return odt.insert({x, r, v}).first;
}

void assign(int l, int r, int v) {
    auto itr = split(r + 1), itl = split(l);
    odt.erase(itl, itr);
    odt.insert({l, r, v});
}

int MOD[maxn], Val[maxn];
int qpow(int a, int p, int mod) {
    int ans = 1LL, A = a;

    if (MOD[A] == mod) return Val[A];

    while (p) {
        if (p & 1) ans *= a, ans %= mod;
        a *= a, a %= mod;
        p >>= 1;
    }

    Val[A] = ans, MOD[A] = mod;

//  cout << ans << '\n'; 
    return ans % mod;
}

void update(int l, int r, int x, int y, int d) {
//  cout << l << ' ' << r << ' ' << x << ' ' << y << ' ' << d << '\n';
    auto itr = split(r + 1), itl = split(l);Node its[maxn];
    int tot = 1, nowx = 0;
    for (auto i = itl;i != itr;i++) {
        int v = i -> v;
        its[++tot] = *i;
        if (v <= y && v >= x) its[tot].v = d;
    }

    odt.erase(itl, itr);

    for (int i = 1;i <= tot;i++) {
        if (i == 1 || its[i].v != its[i - 1].v) {
            if (nowx) odt.insert({nowx, its[i - 1].r, its[i - 1].v});
            nowx = its[i].l;
        }
    }
    odt.insert({nowx, r, its[tot].v});
}

int len(auto it) {
    return it -> r - it -> l + 1;
}

int query(int l, int r, int p, int mod) {
//  cout << l << ' ' << r << ' ' << p << ' ' << mod << '\n';
    auto itr = split(r + 1), itl = split(l);
//  cout << itl -> l << ' ' << itr -> r;
    int cnt = 0;
    for (;itl != itr;itl++) {
//      cout << itl -> l << ' ' << itl -> r << ' ' << itl -> v << ' ' << len(itl) << '\n';
//      (((cnt += qpow(itl -> v, p, mod)) %= mod) *= len(itl)) %= mod;
        cnt = (cnt + (qpow(itl -> v, p, mod) % mod) * len(itl)) % mod;
//      cout << qpow(itl -> v, p, mod) << "nailong " << cnt << '\n';
    }
//  cout << cnt << '\n';
    return cnt;
}

signed main() {
    n = read(), m = read();

    for (int i = 1;i <= n;i++) odt.insert({i, i, read()});

    int Ans = 0;

    while (m--) {
        int op = read(), l = read(), r = read(), u = read(), v = read(), t;
        if (op == 0) t = read(), update(l, r, u, v, t);
        else Ans ^= query(l, r, u, v);

//      for (auto i : odt) cout << i.l << ' ' << i.r << ' ' << i.v << '\n';
    }

    write(Ans), putchar(10);

    return 0;
}

::::