线段树

1. 复杂信息维护

1. 「Luogu6327」区间加区间sin和

• 题意：
  给定序列 \(a_1,a_2,...,a_n\)，支持两种操作：

1. 给 \(l \le x \le r\) 的所有 \(a_x\) 加上 \(k\)。
2. 查询 \(\sum\limits_{i=l}^{r}sin(a_i)\)。
   \(n,m\le 10^5\)

• 做法：
  维护 \(\sin\) 和还有 \(\cos\) 和就行。

理由是下面这俩柿子：

\[\begin{aligned}\sin(\alpha+\beta)=\sin\alpha\cos\beta+\cos\alpha\sin\beta\\\cos(\alpha+\beta)=\cos\alpha\cos\beta-\sin\alpha\sin\beta\end{aligned} \]

所以：

\[\begin{aligned}\sum\limits_{k=l}^{r}\sin(a_k+c)=\sum\limits_{k=l}^{r}(\sin a_k\cos c+\sin c\cos a_k)=\cos c(\sum\limits_{k=l}^{r}\sin a_k)+\sin c(\sum\limits_{k=l}^{r}\cos a_k)\\ \sum\limits_{k=l}^{r}\cos(a_k+c)=\sum\limits_{k=l}^{r}(\cos c\cos a_k-\sin c\sin a_k)=\cos c(\sum\limits_{k=l}^{r}\cos a_k)-\sin c(\sum\limits_{k=l}^{r}\sin a_k)\end{aligned}\]

---

2. 「CF1149C」Tree Generator™

• 题意：
  给你一颗树的括号序列，求其直径。
  然后 \(m\) 次询问，每次交换两个括号，求交换后的直径。
  保证交换后的序列合法。
  \(n,m\le 10^5\)
• 题解

---

3. 「CF1114F」Please, another Queries on Array?

• 题意：

1. 区间修改：\(a_i=a_i\times c,i\in[l,r]\)。
2. 区间询问：\(\varphi(\prod\limits_{i=l}^{r}a_i)\mod (10^9+7)\)。
   \(n\le 4\times 10^5,q\le 2\times 10^5\)

• 题解

2. 需要脑洞的题目

4. 「CF356A」Knight Tournament

• 做法：
  考虑一个骑士被击败当且仅当他在第一个包含他，并且他不是胜利者的区间里面，击败他的人就是那个区间的胜利者。于是题目转换为求：对于每个 \(i\) ，求 \(\min\limits_{1\le j\le m}^{x_j≠i,l_j\le i\le r_j}\{j\}\)。
  然后我们把这些 \(battles\) 倒序排列，不难发现：原来第一个包含 \(i\) 且 \(x_j≠i\) 的区间 \(j\) 的胜利者（即打败 \(i\) 的那个人），就是倒序把所有 \(l_j\) 到 \(r_j\) 除 \(x_j\) 位外覆盖成 \(x_j\) 之后第 \(i\) 位的数。
  为啥？因为是倒序排列，所以最后一个覆盖这一位的一定是原来第一个覆盖的。
  于是题目再转换为区间覆盖，使用线段树维护即可。

5. 「HEOI2016 or TJOI2016」排序

• 题意：
  将序列子段从小到大或从大到小排序,一共 \(m\) 次，最后查询位置 \(q\) 上的值。
  \(n,m\le 10^5\)
• 做法：
  考虑 \(01\) 序列的排序如何实现。
  我们发现 \(01\) 序列排序之后有一边是 \(0\)，一边是 \(1\)，所以给某个子段排序相当于两个区间覆盖操作，可以使用线段树维护。
  然后再考虑对于原数组 \(a_i\)，二分 \(q\) 位置上的最终值 \(p\)。将 \(a_i<p\) 的 \(i\) 标记为 \(0\) ，否则标记为 \(1\)。对于这个 \(01\) 序列排序，最后如果位置 \(q\) 上面的数是 \(1\)，就说明 \(p\) 一定比这个二分的值大。

---

6. 「Luogu4198」楼房重建

• 题意：
  二维空间单点更新某处的线段高度，每次修改后查询从 \(0\) 处看到的线段数。
  \(n,m\le 10^5\)
• 做法：
  转换成斜率，即为求必须取 \(a_1\) 的最长上升子序列长度。
  线段树维护区间最长上升子序列长度 \(len\) 以及最大斜率 \(mx\)。询问的时候带一个限制 \(m\) ，表示最长上升子序列的首项可以取到的最小值，如果左边区间的 \(mx\) 小于等于 \(m\) ，直接统计右边区间的结果；否则右边区间能取的长度为 tr[x].len - tr[ls].len ，加上左边区间 \(len\) 之中能取的部分即可。
  单点修改的话，每次 pushup 要 query 一遍右儿子，因为左儿子的 \(mx\) 可能已经被改变。

int query(int l, int r, double mx, int x) {
	if (l == r) return s[l] > mx;
	if (tr[ls].mx <= mx) return query(mid + 1, r, mx, rs);
	else return query(l, mid, mx, ls) + tr[x].len - tr[ls].len;
}
void update(int l, int r, int p, double v, int x) {
	if (l == r) { tr[x] = (segtree) { v, l, 1 }; return; }
	if (p <= mid) update(l, mid, p, v, ls);
	else update(mid + 1, r, p, v, rs);
	tr[x].mx = max(tr[ls].mx, tr[rs].mx);
	tr[x].len = tr[ls].len + query(mid + 1, r, tr[ls].mx, rs);
}

3. 线段树合并 & 线段树分裂

7. 「Luogu4556」雨天的尾巴

• 题意：给定一棵树，每次操作给 \(u\) 到 \(v\) 的链上每个点加上一种救济粮的 \(w\) ，求最后每个点存放最多的救济粮种类。
• 做法：
  线段树合并。
  首先树剖，然后修改的时候树上差分，对于差分序列，给每一个树上的点开一棵权值线段树，记录每种救济粮个数以及最多救济粮出现的下标。考虑离线统计答案，从叶子到节点合并线段树：对于一个点 \(u\) ，它的所有儿子 \(s_i\) 已经与 \(s_i\) 的子树信息完成了合并，再合并 \(u\) 和每个 \(s_i\) ，最后统计答案即可，注意动态开点。

void calc(int u) {
	for (int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].to;
		if (v == fa[u]) continue;
		calc(v);
		rt[u] = merge(1, 1e5, rt[u], rt[v]);
	}
	if (tr[rt[u]].mx) ans[u] = tr[rt[u]].id;
}

8. 「CF1009F」Dominant Indices

• 题意：以 \(1\) 为根, \(n\) 个点的树，设 \(d(u,x)\) 为 \(u\) 子树中离 \(u\) 距离为 \(x\) 的点的个数，对每个 \(u\)，求最小的 \(k\)，使得 \(d(u,k)\) 最大。
• 做法：以深度为下标建权值线段树，维护最大值和最大值的位置，从叶子向根合并即可。

9. 「Luogu5494」线段树分裂

• 做法：线段树分裂+线段树合并
  仿照 FHQ Treap 的思路，将以 \(x\) 为根的树分裂成以 \(x,y\) 为根的树（ \(y\) 是通过引用的新树 ），前 \(k\) 小在 \(x\) ，之后在 \(y\)。
  于是我们首先看 \(x\) 左子树 \(v\)，如果 \(v<k\)，左侧依然是 \(x\) 的，递归右侧即可，此时 \(k'=k-v\)。
  如果 \(v=k\)，显然左边给 \(x\)，右边给 \(y\)。
  如果 \(v>k\)，右边归 \(y\)，递归左侧不改变 \(k\)。
  我们发现函数里最多递归一次，所以时间复杂度是 \(\log \ n\) 的。
  由于是分裂第 \(k\) 小，所以 \(x\) 的新权值就是 \(k\)，\(y\) 的权值就是 \(x\) 的原权值减去新权值。
  我们发现如果 \(v\ge k\)，右边都会归 \(y\) ，所以直接 swap(tr[x].rs, tr[y].rs) ，表示右子树归 \(y\) ，\(x\) 的右子树就被清空了。
  那么如何分裂出 \([x,y]\) 呢？
  我们先把 \([1,n]\) 分裂成 \([1,x-1]\) 和 \([x,n]\)，再在 \([x,n]\) 分裂出 \([x,y]\) 和 \([y+1,n]\)，最后把 \([1,x-1]\) 和 \([y+1,n]\) 合并即可。

void split(int x, int &y, int k) {
	if (!x) return;
	y = make();
	int v = tr[tr[x].ls].vl;
	if (k > v) split(tr[x].rs, tr[y].rs, k - v);
	else swap(tr[x].rs, tr[y].rs);
	if (k < v) split(tr[x].ls, tr[y].ls, k);
	tr[y].vl = tr[x].vl - k;
	tr[x].vl = k;
}

signed main() {
	n = read(), m = read();
	for (int i = 1; i <= n; i++) rt[seq] = update(1, n, i, read(), rt[seq]);
	for (int i = 1, op, x, y, z; i <= m; i++) {
		op = read(), x = read(), y = read();
		if (op == 0) {
			z = read();
			int p = query(1, n, 1, z, rt[x]), q = query(1, n, y, z, rt[x]), t = 0;
			split(rt[x], rt[++seq], p - q), split(rt[seq], t, q);
			rt[x] = merge(rt[x], t, 1, n);
		} else if (op == 1) {
			rt[x] = merge(rt[x], rt[y], 1, n);
		} else if (op == 2) {
			z = read();
			rt[x] = update(1, n, z, y, rt[x]);
		} else if (op == 3) {
			z = read();
			write(query(1, n, y, z, rt[x])), puts("");
		} else if (op == 4) {
			if (tr[rt[x]].vl < y) write(-1), puts("");
			else write(kth(1, n, y, rt[x])), puts("");
		}
	}
    return 0;
}

平衡树

4. 平衡树板子

懒得说了

5. 优化 dp

10. 「CF573E」Bear and Bowling

• 题意：求 \(a\) 的子序列 \(b\) ，使得 \(\sum\limits_{i}ib_i\) 最大。
• 题解