Nowcoder线段树应用专题 | Rabbit House = カフェラテ、カフェモカ、カプチーノ~ = QwQ

# 线段树的一些技巧

# 单点修改的写法

有单点修改操作时，使用 map 记录数组某个位置的点在线段树中的位置可以更快更好写地修改。

	void build(int l, int r, int rt)
	{
	if (l == r)
	{
	//...
	map[l] = rt;
	return;
	}
	//...
	}
	void update(int rt, int v)
	{
	rt = map[rt];
	tree[rt] += v;
	while (rt >>= 1)
	update(rt);
	}

# 一些封装思想

传统面向过程的线段树在维护复杂信息时可能有很多不便，把一些 lazytag 相关操作封装起来比如：

	pushdown(rt)
	init_lazy(rt) // 初始化 / 还原 lazy
	cal_lazy(rt) // 计算 lazy 对当前节点的影响
	union_lazy(rt, son) // 传递标记

之后所有线段树题直接套板子，只需要重新设计 lazytag 就好了

在 E 题疯狂 WA 之后被教做人了。。改了波码风怎么就 A 了（躺）

# 动态 DP

~~Dynamic Dynamic Progarmming~~

本质上是线段树维护转移矩阵。

由 DAG 引入，假设现在有这个图（行表示起点列表示终点）：

$原矩阵： \begin{bmatrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix} \quad\quad 用这个表示走两步的方案数： \begin{bmatrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix} ^ 2 = \begin{bmatrix} 0 & 1 & 1 & 2 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix}$

对其中矩阵乘法进行扩展：

矩阵中对乘法的 operator 这里： tmp[i][j] = a[i][k] * a[k][j] 改成 tmp[i][j] = min(a[i][k] + a[k][j], tmp[i][j]) 就变成了 Floyd。

然后把这个矩阵放到线段树中维护，就可以做 DAG 上的带修 Flyod。

# 题目

# K 矩阵表示

# 题意

上场 E 题传送门

在此基础上增加单点修改，即某次操作可能会修改某个中间楼梯的方向。

# 思路

显然可以树状数组维护前缀和，但不如线段树更优美。

因为树状数组需要矩阵求逆，但线段树只需要考虑区间合并（仅矩阵乘法）。

# 代码

	#include <cstdio>
	#include <iostream>
	#define rep(i,s,t) for(int i=s;i<=t;i++)
	#define root 1,n,1
	#define mid (l+r)>>1
	#define lson l,m,rt<<1
	#define rson m+1,r,rt<<1\|1
	using namespace std;
	using ll = long long;
	const int MAXN = 1e5 + 233;
	const ll MOD = 1e9 + 7;
	int n, M;
	struct Matrix
	{
	ll a[2][2];
	Matrix()
	{
	a[0][0] = a[1][1] = 1;
	a[1][0] = a[0][1] = 0;
	}
	Matrix(ll a00, ll a01, ll a10, ll a11)
	{
	a[0][0] = a00;
	a[0][1] = a01;
	a[1][0] = a10;
	a[1][1] = a11;
	}
	Matrix operator * (const Matrix &B)
	{
	Matrix C(0, 0, 0, 0);
	rep (i, 0, 1)
	rep (j, 0, 1)
	rep (k, 0, 1)
	C.a[i][j] = (C.a[i][j] + a[i][k] * B.a[k][j]) % MOD;
	return C;
	}
	} mtx[MAXN];
	struct Tnode
	{
	Matrix sum;
	};
	struct Tree
	{
	Tnode t[MAXN << 2];
	int mp[MAXN]; // 树节点，与数组的映射
	void update(int rt)
	{
	t[rt].sum = t[rt << 1].sum * t[rt << 1 \| 1].sum;
	}
	void build(int l, int r, int rt)
	{
	if (l == r)
	{
	t[rt].sum = mtx[l];
	mp[l] = rt;
	return;
	}
	int m = mid;
	build(lson);
	build(rson);
	update(rt);
	}
	void modify(int p, Matrix v)
	{
	int rt = mp[p];
	t[rt].sum = v;
	while (rt >>= 1)
	update(rt);
	}
	Matrix query(int l, int r, int rt, int nl, int nr)
	{
	if (nl <= l && r <= nr)
	{
	return t[rt].sum;
	}
	int m = mid;
	if (nl <= m)
	if (m < nr)
	return query(lson, nl, nr) * query(rson, nl, nr);
	else
	return query(lson, nl, nr);
	else
	return query(rson, nl, nr);
	}
	} ST;
	int main()
	{
	//freopen("in.txt", "r", stdin);
	scanf("%d%d ", &n, &M);
	char ch;
	rep (i, 2, n) // 写法有关，这里记录的是到达这层的楼梯
	{
	scanf("%c", &ch);
	if (ch == '/')
	mtx[i] = Matrix(1, 1, 0, 1);
	else
	mtx[i] = Matrix(1, 0, 1, 1);
	}
	ST.build(root);
	int opt, l, r, s, t;
	Matrix x;
	while (M--)
	{
	scanf("%d", &opt);
	if (!opt)
	{
	scanf("%d %c", &l, &ch);
	if (ch == '/')
	x = Matrix(1, 1, 0, 1);
	else
	x = Matrix(1, 0, 1, 1);
	ST.modify(l + 1, x);
	}
	else
	{
	scanf("%d%d%d%d", &l, &r, &s, &t);
	printf("%lld\n", ST.query(root, l + 1, r).a[s][t]);
	}
	}
	return 0;
	}

# J DDP

# 题意

在原题的基础上添加了：

像 K 题一样可以修改中间楼梯的结构（单点）。
每个楼梯都有权值，走过有一定花费，可以进行修改（单点）。
查询最短路，而不是方案数。

# 思路

类似最短路，矩阵里的每个数字改为表示权值（没有楼梯就置为 inf）。

在矩阵乘法中做一些修改，相乘改成类似 Floyd 的求 min 操作。

用线段树维护即可。

# 代码

	#include <cstdio>
	#include <iostream>
	#include <cstring>
	#define rep(i,s,t) for(int i=s;i<=t;i++)
	#define root 1,n,1
	#define mid (l+r)>>1
	#define lson l,m,rt<<1
	#define rson m+1,r,rt<<1\|1
	using namespace std;
	using ll = long long;
	const int MAXN = 1e5 + 233;
	const ll INF = 1e15 + 233;
	int n, M;
	struct Matrix
	{
	// 矩阵除了对乘法的 operator 以外与上题完全一致
	Matrix operator * (const Matrix &B)
	{
	Matrix C(INF, INF, INF, INF);
	rep (i, 0, 1)
	rep (j, 0, 1)
	rep (k, 0, 1)
	C.a[i][j] = min(C.a[i][j], a[i][k] + B.a[k][j]); // 改成类似 floyd 的做法
	return C;
	}
	} mtx[MAXN];
	struct Tnode
	{
	Matrix sum;
	};
	struct Tree
	{
	// 线段树部分与上题完全一致
	} ST;
	char str[MAXN];
	int main()
	{
	freopen("in.txt", "r", stdin);
	scanf("%d%d ", &n, &M);
	scanf("%s", str + 2);
	int v0, v1, v2;
	rep (i, 2, n)
	{
	scanf("%d%d%d", &v0, &v1, &v2);
	if (str[i] == '/')
	mtx[i] = Matrix(v0, v2, INF, v1); // 跟图论题一样的初始化 emm
	else
	mtx[i] = Matrix(v0, INF, v2, v1);
	}
	ST.build(root);
	int opt, l, r, s, t;
	char ch;
	Matrix x;
	while (M--)
	{
	scanf("%d", &opt);
	if (opt == 0)
	{
	scanf("%d %c", &l, &ch);
	char nowch = mtx[l + 1].a[1][0] == INF ? '/' : '\\';
	if (ch != nowch)
	{
	swap(mtx[l + 1].a[0][1], mtx[l + 1].a[1][0]);
	ST.modify(l + 1, mtx[l + 1]);
	}
	}
	else if (opt == 1)
	{
	scanf("%d", &l);
	scanf("%d%d%d", &mtx[l + 1].a[0][0], &mtx[l + 1].a[1][1],
	(mtx[l + 1].a[1][0] == INF) ? &mtx[l + 1].a[0][1] : &mtx[l + 1].a[1][0]);
	ST.modify(l + 1, mtx[l + 1]);
	}
	else
	{
	scanf("%d%d%d%d", &l, &r, &s, &t);
	Matrix ans = ST.query(root, l + 1, r);
	printf("%lld\n", ans.a[s][t] >= INF ? -1 : ans.a[s][t]);
	}
	}
	return 0;
	}

# H 线段树的二分思想

# 题意

给出一堆箱子（ $3e5个$ ），每个箱子最多放 $m$ 大小（ $1e9$ ），有一些物品（ $3e5$ ）序列，每个物品有大小（ $1e9$ ），每个箱子不能超过 $k$ 个（ $1e6$ ）物品。

每次从左到右寻找能放下当前物品的箱子并放下，询问放在哪里。

# 思路

二分思想，线段树维护区间 max。

每次按照以下流程：

根节点能不能放下，放不下直接输出 "-1"。
看左右子树能不能放下，按题意优先左子树。
一直到叶子节点，进行单点加操作，再一路合并上去。

# 代码

	#include <cstdio>
	#include <iostream>
	#define rep(i,s,t) for(int i=s;i<=t;i++)
	#define mid (l+r)>>1
	#define root 1,n,1
	#define lson l,m,rt<<1
	#define rson m+1,r,rt<<1\|1
	using namespace std;
	const int MAXN = 3e5 + 233;
	int n, M, k, T, tr[MAXN << 2], cnt[MAXN]; //tr 记录区间最大值，cnt 记录每个箱子的物品个数
	void update(int rt)
	{
	tr[rt] = max(tr[rt << 1], tr[rt << 1 \| 1]);
	}
	void build(int l, int r, int rt)
	{
	if (l == r)
	{
	tr[rt] = M;
	return;
	}
	int m = mid;
	build(lson);
	build(rson);
	update(rt);
	}
	int modify(int l, int r, int rt, int ai)
	{
	if (l == r)
	{
	if (tr[rt] >= ai)
	{
	tr[rt] -= ai;
	if (++cnt[l] == k) // 放 k 个之后直接把剩余容量变成 - 1
	tr[rt] = -1;
	return l;
	}
	return -1;
	}
	int m = mid, ans;
	if (tr[rt << 1] >= ai) // 优先往左，然后往右
	ans = modify(lson, ai);
	else if (tr[rt << 1 \| 1] >= ai)
	ans = modify(rson, ai);
	else
	return -1;
	update(rt);
	return ans;
	}
	int main()
	{
	//freopen("in.txt", "r", stdin);
	scanf("%d", &T);
	while (T--)
	{
	scanf("%d%d%d", &n, &M, &k);
	rep (i, 1, n)
	cnt[i] = 0;
	build(root);
	int ai;
	rep (i, 1, n)
	{
	scanf("%d", &ai);
	printf("%d\n", modify(root, ai));
	}
	}
	return 0;
	}

# F 综合应用

# 题意

给出一个长 $3e5$ 的数组，元素大小 $1e9$ ， $3e5$ 次询问每次给出区间 $[l, r]$ ，问将区间内元素离散化之后有多少个元素与原来不同。

# 思路

权值线段树。

区间 MEX：区间最小的未出现正整数。

大于 MEX 的数都会发生改变。

用 $lastpost[x]$ 表示值为 $x$ 的数最后一次在数组中出现的下标，线段树维护区间 $lastpost$ 最小值。

离线对查询区间右端点排序，对每个询问区间都可以通过区间 $l$ 值查询出 MEX。

问题进一步简化：求区间中小于 MEX 的数有多少个。

用 $cnt[x]$ 表示值为 $x$ 的数字有多少个

# 代码

排序尽量用 cmp 别 operator（operator 莫名 RE 改了好久 QAQ）

	#include <cstdio>
	#include <iostream>
	#include <algorithm>
	#define rep(i,s,t) for(int i=s;i<=t;i++)
	#define root 1,n,1
	#define mid (l+r)>>1
	#define lson l,m,rt<<1
	#define rson m+1,r,rt<<1\|1
	using namespace std;
	const int MAXN = 3e5 + 233;
	int n, M, a[MAXN], ans[MAXN], q2tot;
	struct query1 //q1 记录原题询问，对右端点排序
	{
	int id, l, r;
	} q1[MAXN];
	struct query2 //q2 记录需要查询出现次数的数字
	{
	int id, pos, num, type; //pos 位置，num 数字，左右端点 type 分别取 1/-1，配合 id 直接统计到 ans 里
	} q2[MAXN << 1];
	bool cmpq1(query1 x, query1 y)
	{
	return x.r < y.r;
	}
	bool cmpq2(query2 x, query2 y)
	{
	return x.pos < y.pos;
	}
	struct Seg
	{
	int t[MAXN << 2], mp[MAXN]; // 权值线段树，维护 lastpos 最小值，mp 用于快速 modify
	void update(int rt)
	{
	t[rt] = min(t[rt << 1], t[rt << 1 \| 1]);
	}
	void build(int l, int r, int rt)
	{
	if (l == r)
	{
	t[rt] = 0;
	mp[l] = rt;
	return;
	}
	int m = mid;
	build(lson);
	build(rson);
	update(rt);
	}
	void modify(int rt, int v)
	{
	rt = mp[rt];
	t[rt] = v;
	while (rt >>= 1)
	update(rt);
	}
	int query(int l, int r, int rt, int nl) // 查询 nl 以后的 mex
	{
	if (l == r)
	{
	return l;
	}
	int m = mid;
	if (t[rt << 1] < nl) // 左边有数字最后一次出现在 nl 之前，优先往左查
	return query(lson, nl);
	else
	return query(rson, nl);
	}
	} ST;
	struct Bit
	{
	int t[MAXN << 1]; // 统计数字出现次数的 BIT
	int lb(int x)
	{
	return x & (-x);
	}
	void modify(int p, int v)
	{
	for (; p <= n; p += lb(p))
	t[p] += v;
	}
	int query(int p)
	{
	int tmp = 0;
	for (; p; p -= lb(p))
	tmp += t[p];
	return tmp;
	}
	} BIT;
	int main()
	{
	//freopen("in.txt", "r", stdin);
	scanf("%d", &n);
	rep (i, 1, n)
	{
	scanf("%d", &a[i]);
	if (a[i] > n)
	a[i] = n + 1;
	}
	scanf("%d", &M);
	rep (i, 1, M)
	{
	scanf("%d%d", &q1[i].l, &q1[i].r);
	q1[i].id = i;
	// 一开始认为区间所有数字的值都会改变，后面去查有多少不变（有多少数字小于等于 mex）
	ans[i] = q1[i].r - q1[i].l + 1;
	}
	sort(q1 + 1, q1 + M + 1, cmpq1);
	int now = 1;
	ST.build(root);
	rep (i, 1, n)
	{
	ST.modify(a[i], i); // 更新当前数字最后出现位置
	while (now <= M && q1[now].r == i)
	{
	q2[++q2tot].id = q1[now].id;
	q2[q2tot].num = ST.query(root, q1[now].l); // 查询当前 mex
	// 前缀和，出现次数 = [1, r] - [1, l - 1]，ans 是要减去这个数，右端点记 - 1
	q2[q2tot].pos = q1[now].r;
	q2[q2tot].type = -1;
	if (q1[now].l != 1)
	{
	q2[++q2tot].id = q1[now].id;
	q2[q2tot].num = q2[q2tot - 1].num;
	q2[q2tot].pos = q1[now].l - 1;
	q2[q2tot].type = 1;
	}
	now++;
	}
	}
	// 按 pos 排序，边添加数字边查询，就能避免用可持久化数据结构了 emm
	sort(q2 + 1, q2 + q2tot + 1, cmpq2);
	now = 1;
	rep (i, 1, n)
	{
	BIT.modify(a[i], 1);
	while (now <= q2tot && q2[now].pos == i)
	{
	ans[q2[now].id] += BIT.query(q2[now].num) * q2[now].type;
	now++;
	}
	}
	rep (i, 1, M)
	printf("%d\n", ans[i]);
	return 0;
	}

acm 杂题数据结构

# 线段树的一些技巧

# 单点修改的写法

# 一些封装思想

# 动态 DP

# 题目

# K 矩阵表示

# 题意

# 思路

# 代码

# J DDP

# 题意

# 思路

# 代码

# H 线段树的二分思想

# 题意

# 思路

# 代码

# F 综合应用

# 题意

# 思路

# 代码

Nowcoder前缀和专题

[杂题] 线段树一些题目