简介
线段树大概是 $Oier$ 中最常用的数据结构了（大概
如何解决一道线段树题
操作的种类
下面先贴两个线段树用的板子，主要的区别在于 $Update$
一种是按照标记优先级的顺序，另一种是按照值和标记的顺序
一般来讲，在有普通关系标记的时候，只能用后一种写法
其它情况下一般使用前一种写法
1 |
|
以 Luogu U140092 线段树练习 为例
1 |
|
为了方便叙述，我们将对应操作用对应的函数进行替换
区间合并：$maintain$
下放标记：$pushdown$
应用标记(标记对值的影响)、叠加标记(标记对标记的影响)：$Update$
注意到我们把区间修改中的对完整区间修改也视为应用、叠加标记，因为这个东西本质上与父节点下放标记一样，当然普通关系标记除外
一般对于普通关系标记，我们都是先更新值（应用标记），然后再更新标记（叠加标记）
所以 $pushdown$ 一般这么写
1 | inline void Update_v() {} |
区间修改：$update$
区间查询：$query$
标记的种类
覆盖标记：当区间打上这类标记时，会将该区间的所有数值和标记全部回归一个初始量，这个初始量与之前区间内的数值和标记无关
普通标记
关系标记：具有关系或者说会相互影响的标记，我们称之为关系标记
但是我们依照增加标记的顺序是否会影响到对应值的更新来将关系标记再次分为两类
顺序关系标记 和 普通关系标记
我们以 Luogu P3372 【模板】线段树 1 为例，再此题中我们只需要维护一个区间加的标记，那么这个标记就是普通标记
以 Luogu P3373 【模板】线段树 2 为例，此题中我们维护了两个标记，区间乘和区间加，因为对一个区间先加再乘和先乘再加的结果不同，所以这两个标记为顺序关系标记
以 Luogu U140092 线段树练习 为例，此题中我们要维护的值为区间 $a$ 乘 $b$ 的和，区间 $a$ 的和，区间 $b$ 的和，要维护的标记为区间加 $a$，区间加 $b$，注意到对于一个区间先加 $a$ 后加 $b$ 和先加 $b$ 后加 $a$ 的结果是一样的，所以这两个标记是普通关系标记
以 Luogu P2572 [SCOI2010]序列操作 为例，此题中我们维护了三个标记，其中的区间赋 $0$ 和区间赋 $1$ 标记就是覆盖标记
如何叠加标记和应用标记
首先叠加标记是在我们同时记录了多个标记时会发生的情况
普通标记不会对其它标记造成影响
对于覆盖标记而言，字如其名，将其他标记回归初始量即可，需要注意到不能同时存在两个覆盖标记
对于关系标记，如果是顺序关系标记，我们必须注意下放的顺序
因此，我们定义关系标记的优先级，高优先级的标记先下放，低优先级的标记后下放，另外需要注意的是覆盖标记的优先级为最高
因为关系标记之间有相关关系，所以不能完全将关系标记分开来看，所以我们需要定义优先级，这个东西的本质是更改标记的定义，使得在存在优先级的情况下他们之间不再有相关关系
如果是普通关系标记，因为没有下放顺序的要求，所以我们同时更新就行（暂时先这么写
下面我们先看一下处理顺序关系标记的具体操作
以 Luogu P3373 【模板】线段树 2 为例，此题中的关系标记为区间乘和区间加标记
对于关系标记，根据优先级的来确定如何更新答案的关键是确定答案的形式
我们令 $v$ 表示区间和，$mul$ 表示区间乘，$add$ 表示区间加，为了方便表示，我们加下划线来表示子节点的标记和值
我们对两种分优先级的情况分别讨论
先乘后加
首先我们从数学式子的角度去思考如何设计标记并更新答案
$\underline{}v$ 的形式一定是 $x \cdot \underline{}v + y$
显然 $x$ 是标记 $mul$，$y$ 是标记 $add$，或者从另一个角度思考，我们定义 $mul$ 为 $x$，$add$ 为 $y$
那么我们先来思考 $Update\underline{}add$，因为 $add$ 的优先级低或者说通过 $\underline{} v$ 的形式能够发现 $add$ 对 $mul$ 标记没有影响
能够得到 $Update\underline{}add$ 的实现如下
现在我们考虑 $Update\underline{}mul$ 的实现，我们直接对照上面 $\underline{}v$ 的形式来乘一个 $mul$，得到 $mul\cdot x\cdot \underline{}v+mul\cdot y$
根据这个东西我们能够得到 $mul$ 对子节点的标记的作用，根据 $\underline{}v$ 的形式能够得到 $mul$ 对子节点的值的修改
另外我们换一个角度去思考如何设计标记并更新答案，不过本质上还是从答案的形式出发
我们直接按照最常规的计算顺序来思考，不妨将答案的形式表示为 $(((v+add1)\cdot mul1+add2)\cdot mul2+add2)\cdots) \cdot muln$
自然能够想到定义两个标记一个记录 $v$ 要乘多少，另一个记录要加多少，不妨令这两个标记为 $mul$ 和 $add$
在 $update$ 的时候对于区间加 $add$ 能够得到
区间乘 $mul$ 能够得到
但是在 $pushdown$ 的时候似乎出现了问题，我们要同时区间加和区间乘，好像又出现顺序问题了 = =
但其实并没有顺序问题，因为父节点传过来的标记已经按照 $update$ 的顺序操作过了，并且父节点传过来的标记一定比自己身上的标记的顺序要靠后，所以父节点的标记就相当于是把 $(((v+add1)\cdot mul1+add2)\cdot mul2+add2)\cdots) \cdot muln$ 整个东西的后面一部分压缩成了两个变量，而自己身上的标记就是前半段压缩成了一个标记，那么更新顺序自然和上面讨论过的一样了
就我个人而言，后面这种思路更加好想，当然两个思路本质是一样的
先加后乘
那么 $\underline{}v$ 的形式一定是 $(\underline{}v+x)\cdot y$
$Update\underline{}mul$
$Update\underline{}add$ 稍复杂一点，我们加 $add$ 之后变成 $(\underline{}v+x)\cdot y+add=(\underline{}v+x+\frac{add}{y})\cdot y$
下面我们来看一下处理普通关系标记的操作
以 Luogu U140092 线段树练习 为例
对于普通关系标记，我们需要直接思考所有普通关系标记对于需要维护的值的作用效果
在此题中，首先我们肯定要维护 $\sum a\cdot b$，那么我们可以分别思考 $a$ 区间加 $adda$ 和 $b$ 区间加 $addb$ 对答案 $\sum a\cdot b$ 的影响
通过这个影响来确定要维护的标记，然后我们发现需要维护 $\sum a$ 和 $\sum b$，然后再考虑 $adda$ 和 $addb$ 的应用和叠加
下面我们再看一道比较复杂的处理顺序关系标记和普通关系标记的题目
Luogu P5009 [yLOI2018] 不老梦 标记啥的都写到题解里面了
下面我们来讨论一下如何系统的求解顺序关系标记的顺序，我们以 Luogu P3373 【模板】线段树 2 为例
首先，我们有乘法和加法标记，我们考虑答案的形式，不妨假设是先乘后加
那么先加后乘就是有影响的，那么我们就要思考乘法标记对加发标记的作用，换句话讲就是我们要先下放乘法标记
所以我们对于顺序关系标记，首先要思考答案的形式，根据这个东西来确定下放顺序
2021杭电多校2 G I love data structure 经典例子
Segment tree Beats
区间最值操作
简要题意：给定一个长度为 $n$ 的序列 $a_i$，现在有 $m$ 次操作，操作有三种，第一种操作给定 $l,r,v$，将区间 $[l,r]$ 中的所有数都变成 $min(a_i,v)$，第二种操作给定 $l,r$，求 $max(a_i),i\in[l,r]$，第三种操作给定 $l,r$，求 $[l,r]$ 的区间和
$n,m\le 10^6$
简要题解：我们考虑维护用线段树区间最大值 $mx$ 和区间严格次大值 $se$ 以及区间最大值的个数 $t$ 和区间和 $sum$，那么对于一次区间取 $min$ 操作，如果 $v>= mx$，那么可以直接忽略；如果 $se<v< mx$，那么我们可以直接更新 $mx,sum$，然后我们将这个东西当成标记，具体实现中，我们直接将 $mx$ 当做标记即可，经过简单分类讨论，能够发现这个标记可以正常下传
如果 $se \ge v$，那么我们直接暴力 $dfs$，直到满足 $se <v<mx$，这样看似是暴力，实际上我们可以证明它的复杂度为 $O(n\log n)$，这里我们不沿用吉老师在论文中使用的标记类方法，我们定义一个节点的势能为它所管辖的区间中不同数的个数，整颗线段树的势能定义为所有节点的势能的和，上界为 $O(n\log n)$，注意到每暴力 $dfs$ 到一个点，这个点的次大值和最大值会被合并，也就是说值域减少 $1$，即势能减少 $1$，总时间复杂度 $O((n+m)\log n)$
简要题意：给定一个长度为 $n$ 的序列和 $m$ 次操作，操作有区间加，区间对 $v$ 取 $min$，区间对 $v$ 取 $max$，求区间和，求区间最大值，求区间最小值
简要题解：我们维护最大值、最大值的数量、严格次大值，最小值、最小值的数量、严格次小值，对于区间加，我们采用对于每种值单独维护一个标记的做法，即最大值区间加标记、最小值区间加标记、其它值区间加标记，要不然需要大量分类讨论
pushdown的时候需要注意值域重复的情况，其它就不需要分类讨论了，时间复杂度 $O(n\log^2 n)$1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28inline void Update(int i, int l, int r, int add1, int add2, int add3) {
// mn 最小值 smn 次小值 cmn 最小值个数 add1 最小值加法标记
// mx 最大值 smx 次大值 cmx 最大值个数 add2 最大值加法标记
// add3 其他值加法标记
if (T[i].mn == T[i].mx) {
if (add1 == add3) add1 = add2;
else add2 = add1;
T[i].v += 1ll * add1 * T[i].cmn;
}
else T[i].v += 1ll * add1 * T[i].cmn + 1ll * add2 * T[i].cmx +
1ll * add3 * (r - l + 1 - T[i].cmn - T[i].cmx);
if (T[i].smn == T[i].mx) T[i].smn += add2;
else if (T[i].smn != INF) T[i].smn += add3;
if (T[i].smx == T[i].mn) T[i].smx += add1;
else if (T[i].smx != -INF) T[i].smx += add3;
T[i].mn += add1; T[i].mx += add2;
T[i].add1 += add1; T[i].add2 += add2; T[i].add3 += add3;
}
inline void pushdown(int i, int l, int r) {
int &add1 = T[i].add1, &add2 = T[i].add2, &add3 = T[i].add3;
int m = l + r >> 1, mn = min(T[lc].mn, T[rc].mn), mx = max(T[lc].mx, T[rc].mx);
Update(lc, l, m, T[lc].mn == mn ? add1 : add3,
T[lc].mx == mx ? add2 : add3, add3);
Update(rc, m + 1, r, T[rc].mn == mn ? add1 : add3,
T[rc].mx == mx ? add2 : add3, add3);
add1 = add2 = add3 = 0;
}简要题意：给定一个长度为 $n$ 的序列，现在有 $m$ 次操作，操作有两种：单点修改、查询 $a_x,\cdots,a_n$ 的不同的后缀最小值的个数
$n,m\le 10^6$
简要题解：注意到查询不是区间而是一个后缀，这启示我们离线后扫描线，我们用线段树维护以时间为下标，值为后缀最小值的线段树，注意到每次查询的答案即为这个时间后缀最小值变化的次数
我们考察最基本的
Segment tree Beats的做法，容易发现我们可以在维护的时候顺便维护每个位置的值的变化次数，时间复杂度 $O(n\log n)$简要题意：给定一个长度为 $n$ 的排列 $p$，现在有 $m$ 次询问，每次询问区间 $[l,r]$ 中有多少子区间是连续的，一个区间是连续的，当且仅当这个区间中的数排列后形成一个公差为 $1$ 的等差数列
$n,m\le 1.2\times 10^5$
简要题解：对于连续区间这个定义，我们已经很熟悉了，如果一个区间是连续区间，那么一定满足 $max-min-(r-l)=0$，且我们注意到对于任何区间都有 $max-min-(r-l)\ge 0$
然后对于询问的形式，容易想到离线后扫描线然后维护一个历史值，这里我们注意到我们要求的是 $0$ 的个数且 $0$ 一定是历史最小值，另外关于 $max-min-(r-l)$ 这个东西可以利用单调栈，那么我们现在就需要维护区间加，求区间历史最小值的个数，为了维护这些东西，我们需要在线段树上维护：区间最小值、区间最小值的个数、区间历史最小值、区间历史最小值的个数、区间加标记、区间历史最小值加标记、区间历史最小值加标记的个数，时间复杂度 $O(n\log n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20inline void Update(int i, ll add, ll tadd, ll ctadd) {
if (T[i].tmn > T[i].mn + tadd) {
T[i].tmn = T[i].mn + tadd;
T[i].ctmn = T[i].cmn * ctadd;
} else if (T[i].tmn == T[i].mn + tadd)
T[i].ctmn += T[i].cmn * ctadd;
T[i].mn += add;
if (T[i].tadd > T[i].add + tadd) {
T[i].tadd = T[i].add + tadd;
T[i].ctadd = ctadd;
} else if (T[i].tadd == T[i].add + tadd)
T[i].ctadd += ctadd;
T[i].add += add;
}
inline void pushdown(int i) {
ll &add = T[i].add, &tadd = T[i].tadd, &ctadd = T[i].ctadd;
Update(lc, add, tadd, ctadd); Update(rc, add, tadd, ctadd);
add = tadd = ctadd = 0;
}
区间历史最值
简要题意：给定一个长度为 $n$ 的序列，现在有 $m$ 次操作，操作分别是区间加，区间赋值，求区间最大值，求区间历史最大值
$n,m \le 10^5$
简要题解：注意到在进行一次区间赋值后，区间加也相当于区间赋值，另外对于历史最大值，我们只需要记录区间加标记的最大前缀和区间赋值的最大值即可
对于标记的维护，我们仍然沿用不同值标记分开维护的思路，所以我们需要维护：区间和、区间最大值、区间历史最大值、区间加标记、区间赋值标记、历史最大值区间加标记、历史最大值区间赋值标记，时间复杂度 $O(n\log n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14inline void Update(int i, int add, int tadd, int cov, int tcov) {
// mx 区间最大值 add 区间加标记 cov 区间赋值标记
// tmx 区间历史最大值 tadd 历史最大值区间加标记 tcov 历史最大值区间赋值标记
T[i].tmx = max({ T[i].tmx, T[i].mx + tadd, tcov });
T[i].mx = cov == -INF ? T[i].mx + add : cov;
if (T[i].cov == -INF) {
T[i].tadd = max(T[i].tadd, T[i].add + tadd), T[i].add += add;
T[i].tcov = tcov; T[i].cov = cov;
}
else {
T[i].tcov = max({ T[i].tcov, T[i].cov + tadd, tcov });
T[i].cov = cov == -INF ? T[i].cov + add : cov;
}
}简要题意：给定一个长度为 $n$ 的序列，现在有 $m$ 次操作，操作有五种：区间加、区间对 $v$ 取 $min$，求区间和，求区间最大值，求区间历史最大值
$n,m\le 5\times 10^5$
简要题解：对于标记的处理，我们依然采用不同值维护不同标记的做法
我们维护区间和、区间最大值、区间最大值的个数、区间次大值、区间历史最大值、最大值加法标记、非最大值加法标记、历史最大值加法标记、非历史最大值加法标记，时间复杂度 $O(n\log^2n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22inline void Update(int i, int l, int r, int madd, int tmadd, int add, int tadd) {
// mx 最大值 tmx 历史最大值 smx 次大值 cmx 最大值个数
// madd 最大值加法标记 tmadd 历史最大值加法标记 add 非最大值加法标记 tadd 非历史最大值加法标记
T[i].v += 1ll * madd * T[i].cmx + 1ll * add * (r - l + 1 - T[i].cmx);
T[i].tmx = max(T[i].tmx, T[i].mx + tmadd);
T[i].mx += madd;
if (T[i].smx != -INF) T[i].smx += add;
T[i].tmadd = max(T[i].tmadd, T[i].madd + tmadd);
T[i].tadd = max(T[i].tadd, T[i].add + tadd);
T[i].madd += madd;
T[i].add += add;
}
inline void pushdown(int i, int l, int r) {
int &madd = T[i].madd, &tmadd = T[i].tmadd, &add = T[i].add, &tadd = T[i].tadd;
int mx = max(T[lc].mx, T[rc].mx), m = l + r >> 1;
if (T[lc].mx == mx) Update(lc, l, m, madd, tmadd, add, tadd);
else Update(lc, l, m, add, tadd, add, tadd);
if (T[rc].mx == mx) Update(rc, m + 1, r, madd, tmadd, add, tadd);
else Update(rc, m + 1, r, add, tadd, add, tadd);
madd = tmadd = add = tadd = 0;
}简要题意：给定一个长度为 $n$ 的序列，现在有 $m$ 次询问，每次询问区间 $[l,r]$ 的最大子段和，但是需要注意这个最大子段和相同的数只算一次
$n,m\le 10^5$
简要题解：我们考虑离线之后扫描线，线段树上每个点维护这个点到当前右端点区间和和历史最大值，容易发现，我们只需要记录 $pre_i$，然后每次更新 $[pre_i+1,i]$ 即可
时间复杂度 $O(n\log n)$
区间历史和
简要题意：给定一个长度为 $n$ 的序列 $a_i$，现在有 $m$ 次询问，每次询问给定区间 $[l,r]$，求区间 $[l,r]$ 有多少对子区间 $[i,j]$， 满足 $[i,j]$ 内不同的 $a_i$ 有奇数个
$n,m \le 5\times 10^5$
简要题解：我们考虑扫描线扫右端点，然后用线段树维护左端点 $0/1$ 表示这个区间合法
那么我们的一次询问相当于求一段区间的历史和，同时右端点移动时，我们需要将一段区间的 $0$ 和 $1$ 翻转
我们考虑维护区间 $0$ 的个数 $v[0]$、区间 $1$ 的个数 $v[1]$、区间历史和 $tv$、区间翻转 $rev$，为了维护区间历史和，我们需要维护一个 $t[2]$，表示区间 $0$ 对区间历史和的贡献以及区间 $1$ 对区间历史和的贡献
我们令区间翻转标记优先级最高，同时区间历史和的形式表示为
1
2if (rev) T[i].tv += t[0] * T[i].v[1] + t[1] * T[i].v[0];
else T[i].tv += t[0] * T[i].v[0] + t[1] * T[i].v[1];那么我们容易得到 $rev$ 对 $t[2]$ 的影响如下
1
if (rev) swap(T[i].t[0], T[i].t[1]), T[i].rev ^= 1;
简要题意：给定一个长度为 $n$ 的序列 $a_i$，现在有 $m$ 次操作，操作有两种：给定区间 $[l,r]$ 和 $v$，将区间 $[l,r]$ 加上 $v$；给定区间 $[l,r]$，求区间 $[l,r]$ 的历史版本和
$n,m\le 10^5,a_i,v\le 1000$
简要题解：首先明确我们需要用线段树维护区间和 $v$、区间历史和 $tv$，但是我们这里不引入时间的概念，我们将历史和 $tv$ 看成是 $v$ 乘上另一个标记 $t$，而每段时间，我们手动更新 $t$
即我们用线段树维护区间和 $v$、区间历史和 $tv$、标记 $t$、区间加标记 $add$、区间历史和加标记 $tadd$
首先我们认为 $t$ 标记优先级高于加标记，然后我们明确答案的形式
1
T[i].tv += t * T[i].v + tadd * (r - l + 1);
考虑 $t$ 对加法标记的影响，容易得到
1
T[i].tadd += t * T[i].add + tadd;
剩下的转移较为简单，不再赘述
线段树能维护的神奇东西
区间加等差数列，区间求和
单点修改矩阵，区间查询矩阵乘积
$01$ 串区间排序
区间求 $\sum_{i=l}^ra_ik^{i-l+1}$，单点修改 $a_i$
简要题意：给定一个长度为 $n$ 的序列 $a_i$，现在有 $m$ 次询问，每次询问求区间 $[l,r]$ 中的所有数排序去重后得到的序列 $b_i$，这个区间的价值是 $\sum b_if_i$，其中 $f_i$ 表示斐波那契数列第 $i$ 项
$n,m\le 3\times 10^4$
简要题解：莫队之后用权值线段树维护，将斐波那契数写成矩阵形式可以看做 $k^i$
线段树的经典应用
线段树上二分
简要题意：在二维平面上维护一个点集 $S$，现在有 $m$ 次操作，操作有三种，第一种操作给定 $(x,y)$，表示在 $S$ 中加入点 $(x,y)$；第二种操作给定 $(x,y)$，表示在 $S$ 中删除点 $(x,y)$；第三种操作给定 $(x,y)$，求满足 $x’>x,y’>y$ 的最小的 $x’$，如果最小的 $x’$ 不唯一，则选择 $y’$ 最小的
简要题解：离散化之后按照 $x$ 建线段树，每次查询相当于在线段树区间 $[x+1,cnt]$ 上最小 $i$ 使得，$y_i>y$，且 $y_i$ 最小
对于一个 $x$，我们用一个 $set$ 把横坐标是 $x$ 的 $y$ 都扔进去，那么我们只需要找到对应 $i$ 即可
这个东西可以在线段树上二分，且时间复杂度为 $O(\log n)$
实际上我们会将每次查询的线段分成 $O(\log n)$ 个线段，对于每个线段的直接判断是 $O(1)$，只有一个线段会下到叶节点，时间复杂度 $O(n\log n)$
1
2
3
4
5
6
7int query(int i, int l, int r, int L, int R, int v) {
if (l > R || r < L || T[i] <= v) return 0;
if (l == r) return T[i] > v ? l : 0;
int m = l + r >> 1, t = query(lc, l, m, L, R, v);
if (!t) return query(rc, m + 1, r, L, R, v);
else return t;
}简要题意：给定一个长度为 $n$ 的非升序列 $a_i$，现在有 $m$ 次操作，操作有两种，第一种操作给定 $x,y$，对于所有 $i\in[1,x]$，修改 $a_i=\max(a_i,y)$；第二种操作给定 $x,y$，从左往右访问序列 $a_i$，如果 $a_i\le y$，则 $ans++,y = y-a_i$，求 $ans$
$n,m\le 2\times 10^5$
简要题解：注意到修改操作不影响 $a_i$ 序列非升的性质，所以对于修改操作，我们只需要在线段树上二分找到第一个小于 $y$ 的位置，然后相当于做区间覆盖
对于查询操作，注意到 $y$ 每次做一段连续减之后大小至少除以 $2$，所以最多有 $O(\log a_i)$ 段，那么我们每次直接在线段树上二分这个东西即可，但是我们每次二分并不是从 $1$ 开始，可以通过将 $y$ 加上 $\sum_{i=1}^{l-1}a_i$ 然后从 $1$，这样会好写很多，时间复杂度 $O(n\log n\log a_i)$
动态 $dp$
线段树分治处理询问好吧，我也不知道为什么以前会起这个鬼名字总之它大概的意思就是对于一类 $dp$ 或者贪心的问题，加上修改并且在修改之后询问答案
有的时候这个东西可以拿线段树维护
本质上就是维护可合并的信息
CF 1420C2 Pokémon Army (hard version)
Luogu P3569 [POI2014]KAR-Cards
bzoj 3022 [Balkan2012]The Best Teams
简要题意：给定一个字符串 $S$，该字符串只含有 $a,b,c$ 这三个字符，你现在可以修改任意次，每次可以将任意一个字母修改成 $a,b,c$ 这三个字符中的某一个，求最小修改多少次使得不存在 $abc$ 这样的子序列，同时现在有 $m$ 次询问，每次询问修改 $S$ 的一个字符，求最小修改次数
$|S|,m \le 10^5$
简要题解：注意到信息满足可合并性，我们考虑线段树，用线段树维护 $a,b,c,ab,bc,abc$ 分别表示区间内不含有这些子序列的最小操作次数
考虑合并，容易得到 $a,b,c$ 的合并是直接相加，但对于 $ab$ 的合并似乎找不到合适的方法，我们考虑分类讨论，如果要使得左右区间合并后不存在 $ab$，那么在保证左右区间内部不含有 $ab$ 的情况下，只有两种情况，一是左边不含 $a$，二是右边不含 $b$，然后我们能够注意到左边不含 $a$ 则一定满足左边不含 $ab$，所以左边不含 $a$ 的情况就是 $T[lc].a + T[rc].ab$，那么容易得到第二种情况就是 $T[lc].ab+T[rc].b$，其它的类似都可以用这种方法得到，单点修改用线段树操作即可，时间复杂度 $O(n\log n)$
求全部或部分点对 $(i,j)$ 的贡献，或者说动态维护 $(i,j)$ 的贡献
一般这种题目的做法是直接分治，但部分题目线段树也可以做且更加方便
比较一般的做法是枚举一个端点，用线段树维护另一个左端点
本质就是扫描线
Luogu P4137 Rmq Problem / mex 强制在线可以用主席树，大部分这类题目都可以这样处理
CF 1389F Bicolored Segments 枚举右端点，然后用线段树维护一个只有左端点变化的数组
简要题意：给定一个长度为 $n$ 的序列 $a$，有 $m$ 次询问，每次给定询问区间 $[l,r]$，求 $\sum_{l\le x\le y\le r} \frac{\frac{max~a_{x\cdots y}+min~a_{l\cdots r}}{2}}{\frac{n(n+1)}{2}}$
$n,m\le 3\times 10^5$
简要题解：将询问离线，按照线段树的最经典做法，右端点增大，用线段树维护左端点
然后参考单调栈加入和删点的过程，用线段树维护
2021杭电多校4 E Didn’t I Say to Make My Abilities Average in the Next Life?!
类楼房修建线段树
简要题意：给定一个长度为 $n$ 的序列 $a$ 和 $m$ 次操作，初始时 $a_i$ 都等于 $0$，每次操作首先修改 $a_x$ 为 $y$，然后查询整个序列的前缀最大值的个数
$n,m\le 10^5$
简要题解：我们考虑使用线段树来维护这个东西，定义 $calc(i,l,r,p)$ 表示对于线段树上的节点 $i$，其所代表的区间为 $[l,r]$，在遍历这个区间之前的最大值为 $a[p]$，遍历这个区间后答案会增加多少
我们考虑如何计算这个东西，如果 $[l,m]$ 中的最大值大于 $a[p]$，那么答案就是 $calc(lc,l,m,p)+calc(rc,m+1,r,p_{lc})$，否则答案就是 $calc(rc,m+1,r,p)$，我们对于线段树上每个节点存储最大值的位置 $p$ 和 $calc(rc,m+1,r,p_{lc})$
因为 $calc$ 的计算是 $O(\log n)$，所以单点修改和查询都是 $O(n\log^2 n)$ 的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
struct Seg {
int p;
pair<int, int> v;
} T[maxn * 4];
pair<int, int> calc(int i, int l, int r, int p) {
if (a[T[i].p] <= a[p]) return make_pair(0, p);
if (l == r) return make_pair(1, l);
int m = l + r >> 1;
if (a[T[lc].p] > a[p]) return make_pair(calc(lc, l, m, p).first + T[i].v.first, T[i].v.second);
else return calc(rc, m + 1, r, p);
}
inline void maintain(int i, int l, int r) {
T[i].p = a[T[lc].p] >= a[T[rc].p] ? T[lc].p : T[rc].p;
int m = l + r >> 1;
T[i].v = calc(rc, m + 1, r, T[lc].p);
}
void build(int i, int l, int r) {
if (l == r) return T[i].p = l, void();
int m = l + r >> 1;
build(lc, l, m); build(rc, m + 1, r);
maintain(i, l, r);
}
void update(int i, int l, int r, int k) {
if (l == r) return ; int m = l + r >> 1;
if (k <= m) update(lc, l, m, k);
else update(rc, m + 1, r, k);
maintain(i, l, r);
}
int last;
int query(int i, int l, int r, int L, int R) {
if (l > R || r < L) return 0;
if (L <= l && r <= R) {
pair<int, int> tmp = calc(i, l, r, last);
last = tmp.second; return tmp.first;
} int m = l + r >> 1;
return query(lc, l, m, L, R) + query(rc, m + 1, r, L, R);
}简要题意：给定两个序列 $a,b$ 和 $m$ 次操作，其中 $b$ 是 $01$ 序列，操作有三种，单点修改 $a$，$b$ 区间异或 $1$，查询给定区间 $[l,r]$ 的前缀最大值组成的序列的相邻两个的 $b$ 的异或和
$n,m\le 2\times 10^5$
简要题解：首先如果我们不考虑 $b$ 的修改，那么这题完全就是楼房重建
现在我们考虑 $b$ 的修改，首先我们把 $b$ 差分一下，用树状数组维护，这样我们区间修改的时候只需要改两个点即可
然后我们继续套用楼房重建的做法，在需要查询 $b$ 的时候，我们直接用树状数组查询，这样看起来是 $O(n\log ^3n)$ 的
但实际上对于每一次 $calc(i,l,r,p)$，我们只会在 $l=r$ 的最底层查询一次 $b$，所以时间复杂度还是 $O(n\log ^2n)$ 的
求矩形并的面积和周长
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
using namespace std;
int n, xl[maxn], xr[maxn], yl[maxn], yr[maxn];
int b[maxn * 2], cnt;
void init_hash() {
for (int i = 1; i <= n; ++i) b[i] = yl[i], b[i + n] = yr[i];
sort(b + 1, b + 2 * n + 1); cnt = unique(b + 1, b + 2 * n + 1) - b - 1;
for (int i = 1; i <= n; ++i) {
yl[i] = lower_bound(b + 1, b + cnt + 1, yl[i]) - b;
yr[i] = lower_bound(b + 1, b + cnt + 1, yr[i]) - b;
}
}
struct node {
int k, l, r, v;
friend bool operator < (const node &u, const node &v) { return u.k < v.k; }
} a[maxn * 2];
struct Seg {
int v, cnt;
} T[maxn * 8];
inline void maintain(int i, int l, int r) { T[i].v = T[i].cnt ? b[r + 1] - b[l] : T[lc].v + T[rc].v; }
void update(int i, int l, int r, int L, int R, int v) {
if (l > R || r < L) return ;
if (L <= l && r <= R) {
T[i].cnt += v;
T[i].v = T[i].cnt ? b[r + 1] - b[l] : (l == r ? 0 : T[lc].v + T[rc].v);
return ;
} int m = l + r >> 1;
update(lc, l, m, L, R, v); update(rc, m + 1, r, L, R, v);
maintain(i, l, r);
}
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> xl[i] >> yl[i] >> xr[i] >> yr[i]; init_hash();
for (int i = 1; i <= n; ++i) a[i] = { xl[i], yl[i], yr[i], 1 }, a[i + n] = { xr[i], yl[i], yr[i], -1 };
sort(a + 1, a + 2 * n + 1); ll ans = 0;
for (int i = 1; i < 2 * n; ++i) {
update(1, 1, cnt - 1, a[i].l, a[i].r - 1, a[i].v);
ans += 1ll * T[1].v * (a[i + 1].k - a[i].k);
} cout << ans << "\n";
return 0;
}求与给定区间有交的所有区间
简要题意：现在有一个长度为 $n$ 的序列和 $m$ 个操作，操作有两种：第一种操作给定区间 $[l,r]$，表示添加一条覆盖 $[l,r]$ 的线段；第二种操作给定区间 $[l,r]$，求与给定区间有交点的最后一次添加的区间，并将其删除
$n\le 10^6,m\le 2\times 10^5$
简要题解：我们考虑线段树，注意到在线段树上寻找与区间 $[l,r]$ 有交点的所有区间的复杂度是 $O(\log n)$ 的，那么我们现在只有两个要维护的东西
一个是子树内最大区间和该点的最大区间，那么我们可以在线段树上每个节点维护一个 $set$，但是注意到区间的权值即为其加入顺序，那么我们可以使用栈来维护，同时使用延迟删除的技巧，时间复杂度 $O(n\log n)$
The 2021 ICPC Asia Taipei Regional Programming Contest C Community Service