数据结构

线段树常见套路

• 维护位数在 $10^5$ 级别的二进制数，支持在某一位 $+1/-1$。
  • 按位用线段树维护，每个结点记录最长全 $0/1$ 后缀，做 $+1/-1$ 时先确定长度后做区间翻转/区间覆盖。
  • 若需要支持两棵线段树比较操作，在每个结点维护区间的哈希值，在线段树上二分找到最高的不同位。
• 对区间中相邻元素满足某种条件的子序列计数。
  • 记线段树结点上记首尾为特定元素的子序列方案数。
• 计算区间某一递推式的值，在每个结点维护转移矩阵的乘积。

线段树合并/分裂/可持久化

• 详见 changle_cyx xyz32768 的学习笔记，这里只作简要论述。

线段树合并

• 当遍历到某个结点，若两棵线段树中这个结点有一棵的对应位置是空的，则没必要遍历下去。
• 因此每次合并的时间就是两棵线段树重合的结点数。
• 设所有线段树的总点数为 $M$， 每次合并重合部分后，相当于删去了其中一棵树的那部分结点 ，因此将所有线段树合并成一棵的总时间复杂度为 $\mathcal{O}(M)$。
• 可对被合并的线段树进行空间回收。

inline void Merge(int &x, int y, int l, int r)
{
    if (!x || !y) 
    {
        x = x + y;
        return ;
    }
    int mid = l + r >> 1;
    Merge(lc(x), lc(y), l, mid);
    Merge(rc(x), rc(y), mid + 1, r);
    sze[x] += sze[y];
   	deleteNode(y);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

线段树分裂

• 将前 $k$ 个存在的叶子结点分裂出去，形成两棵线段树。
• 在线段树上二分即可。

inline void Split(int x, int l, int r, int &a, int &b, int k)
{
	if (l == r)
	{
		a = x;
		b = 0;
		return ;
	}
	int mid = l + r >> 1;
	if (k <= cnt[lc[x]])
	{
		a = newNode();
		b = x;
		Split(lc[x], l, mid, lc[a], lc[b], k);
	}
	else
	{
		a = x;
		b = newNode();
		Split(rc[x], mid + 1, r, rc[a], rc[b], k - cnt[lc[x]]);
	}
	Update(a);
	Update(b);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

• 经典应用：
  • 对 $[l,r]$ 按照升序/降序排序。
  • 询问 $[l,r]$ 相关信息。
• 我们将排序后满足升序/降序的区间成为一个连续段，通过线段树合并/分裂将每一个连续段对应一棵权值线段树，此时元素在序列中的排列顺序与权值线段树中的排列顺序相同，便于在线段树上维护，同时我们用 set 或一般的线段树维护连续段的信息。
• 每次分裂只会产生 $\mathcal{O}(\log n)$ 个结点，总时间复杂度仍然正确。

树状数组套权值线段树

• 以单点修改、区间求第 $k$ 小为例。
  • 每次修改利用树状数组，在对应 $\mathcal{O}(\log n)$ 棵权值线段树上修改。
  • 每次询问依然是在权值线段树上二分，利用树状数组将 $\mathcal{O}(\log n)$ 棵权值线段树上询问的结果相加。

重链剖分

• 令 $size[x]$ 为以 $x$ 为根的子树的结点个数，令 $y$ 为 $x$ 所有子结点中 $size$ 值最大的子结点，则 $(x,y)$ 为重边，$y$ 称为 $x$ 的重儿子，$x$ 到其余子结点的边为轻边。
• 若 $(x,y)$ 为轻边，则 $size[y]\le \lfloor \frac{size[x]}{2}\rfloor$，从根到某结点的路径上的轻边个数为 $\mathcal{O}(\log n)$，因此重路径数目也为 $\mathcal{O}(\log n)$。
• 对于任意两点 $x,y$，可将 $x$ 到 $y$ 的路径划分为 $\mathcal{O}(\log n)$ 个重路径，对应序列上的 $\mathcal{O}(\log n)$ 个区间，同时不在这条路径上的所有点也可以对应序列上的 $\mathcal{O}(\log n)$ 个区间。

inline void dfs1(int x)
{
	sze[x] = 1;
	for (arc *e = adj[x]; e; e = e->nxt)
	{
		int y = e->to;
		if (y == fa[x])
			continue ;
		fa[y] = x;
		dep[y] = dep[x] + 1;
		dfs1(y);
		sze[x] += sze[y];
		if (sze[y] > sze[son[x]])
			son[x] = y;
	}
}

inline void dfs2(int x)
{
	if (son[x])
	{
		pos[son[x]] = ++V;
		top[son[x]] = top[x];
		idx[V] = son[x]; 
		dfs2(son[x]);
	}
	int y;
	for (arc *e = adj[x]; e; e = e->nxt)
		if (!top[y = e->to])
		{
			pos[y] = ++V;
			idx[V] = y;
			top[y] = y;
			dfs2(y);
		}
}

inline void Init()
{
    dfs1(1);
    pos[1] = idx[1] = top[1] = V = 1;
    dfs2(1);
}

inline int pathQuery(int u, int v)
{
	int res = 0;
	while (top[x] != top[y])
	{
		if (dep[top[x]] < dep[top[y]])
			std::swap(x, y);
		res += querySum(1, 1, n, pos[top[x]], pos[x]);
		x = fa[top[x]];
	}
	if (dep[x] > dep[y])
		std::swap(x, y);
	return res + querySum(1, 1, n, pos[x], pos[y]);
}
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
54
55
56
57
58

分块

• 实现时需注意 $[l,r]$ 在同一块内的情况以及分块的边界问题。

• 区间众数。

  • 将序列平均分成 $\sqrt{n}$ 块，预处理 $cnt[i][j]$ 表示元素 $i$ 在前 $j$ 块中出现的次数，$ans[i][j]$ 表示第 $i$ 块到第 $j$ 块的众数。

  • $cnt[i][j]$ 即先枚举 $j$ 后枚举 $i$ 统计，$ans[i][j]$ 即先枚举 $i$，将第 $i$ 块及其之后的数依次加入，用桶维护众数。

  • 询问时设完整块为第 $L$ 块到第 $R$ 块，则答案要么为 $ans[L][R]$，要么为非完整块中的数，暴力枚举即可。

  • 时间复杂度 $\mathcal{O}(n\sqrt{n})$。

• 插入删除元素，询问元素的最大值/最小值。

  • 离散化后按值域分成 $\sqrt{n}$ 块，记录每块中插入元素的数目。
  • 询问时先暴力找到最值所在块，再在块内暴力找到最值。
  • 即可做到 $\mathcal{O}(1)$ 修改，$\mathcal{O}(\sqrt{n})$ 回答询问，可与莫队结合。

• 待补充。

莫队

• 允许离线，无修改，询问区间。

  • 将序列平均分成 $\sqrt{n}$ 块，给每个位置按顺序标上所在块的编号，将询问 $[l,r]$ 按左端点所在块为第一关键字，右端点所在位置的编号为第二关键字排序，易分析出总时间复杂度为 $\mathcal{O}(n\sqrt{n})$。
  • 单次移动可与其它传统数据结构结合，设单次移动时间复杂度为 $\mathcal{O}(k)$，总时间复杂度 $\mathcal{O}(kn\sqrt{n})$。
  • 若单次移动时间复杂度为 $\mathcal{O}(1)$，单次询问结合分块实现，时间复杂度为 $\mathcal{O}(\sqrt{n})$，总时间复杂度依然为 $\mathcal{O}(n\sqrt{n})$。

• 允许离线，带修改，询问区间。

  • 将序列所有点分块，块的大小为 $n^{\frac{2}{3}}$，共有 $n^{\frac{1}{3}}$ 个块，将询问按左端点所在块为第一关键字，右端点所在块为第二关键字，询问的时间为第三关键字进行排序，易分析出总时间复杂度为 $\mathcal{O}(n^{\frac{5}{3}})$。

  • 时间指针的移动即修改操作正向和逆向的进行。

	for (int i = 1, l, r; i <= m; ++i)
	{
		char ch;
		while (ch = getchar(), ch != 'R' && ch != 'Q');
		if (ch == 'Q')
		{
			++qm;
			q[qm].scan(pm, qm);
		}
		else
		{
			read(l); read(r); 
			p[++pm] = modify(l, _a[l], r);
			_a[l] = r;
		}
	}
	std::sort(q + 1, q + qm + 1);
	
	int tl = 1, tr = 0, tt = 0;
	for (int i = 1; i <= qm; ++i)
	{
		int l = q[i].l, r = q[i].r;
		while (tt < q[i].t)
		{
			modify b = p[++tt];
			if (b.x >= tl && b.x <= tr)
			{
				if (!--cnt[b.pre])
					--ans;
				if (!cnt[b.suf]++)
					++ans;
			}
			a[b.x] = b.suf;
		}
		while (tt > q[i].t)
		{
			modify b = p[tt--];
			if (b.x >= tl && b.x <= tr)
			{
				if (!--cnt[b.suf])	
					--ans;
				if (!cnt[b.pre]++)
					++ans;
			}
			a[b.x] = b.pre;
		}
		while (tl < l)
			if (!--cnt[a[tl++]])
				--ans;
		while (tl > l)
			if (!cnt[a[--tl]]++)
				++ans;
		while (tr > r)
			if (!--cnt[a[tr--]])
				--ans;
		while (tr < r)
			if (!cnt[a[++tr]]++)
				++ans;
		fans[q[i].id] = ans; 	
	}
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
54
55
56
57
58
59
60

• 高维莫队的情况有时可用差分拆成几个询问降成低维。

树上莫队

• 允许离线，询问树上路径。
• 考虑将树上路径转化为序列上的区间。
• 欧拉序：$\text{DFS}$ 遍历整棵树，访问到 $x$ 时，加入序列，访问完 $x$ 的子树，再加入序列，记 $x$ 两次加入序列的编号分别为 $st[x],ed[x]$。
• 考虑树上路径 $x\to y$，不妨设 $st[x]<st[y]$。
  • 若 $\text{LCA}(x,y)=x$，则统计 $[st[x],st[y]]$ 只出现一次的点的贡献。
  • 若 $\text{LCA}(x,y)\ne x$，则统计 $[ed[x],st[y]]$ 只出现一次的点的贡献，另外需要补上 $\text{LCA}(x,y)$ 的贡献。
• 实现时可以另外记录 $used[x]=0/1$ 表示指针经过了点 $x$ 偶数次/奇数次，来判断是将该点的贡献插入还是删除。
• 时间复杂度分析、带修改的处理同一般莫队相同。

回滚莫队

• 允许离线，无修改，询问区间，单次移动插入远比删除容易。
• 设法调整指针移动顺序，避免删除操作。
• 将序列平均分成 $\sqrt{n}$ 块，左右端点所在块相同的询问暴力处理，将其余询问按左端点所在块分组，每组按照右端点从小到大排序。
• 因为每组内右端点单调，从所在块右端点开始移动即可，每组总移动次数为 $\mathcal{O}(n)$ 。
• 对于每次询问，将左端点从所在块右端点开始移动，每次移动次数为 $\mathcal{O}(\sqrt{n})$ 。
• 用栈记录移动左端点发生改变的变量的地址和原来的值，处理完每个询问后还原回去。
• 总时间复杂度 $\mathcal{O}(n\sqrt{n})$。

典例1 洛谷P6072

算法一

• 设 $in[x],out[x]$ 分别表示在以 $x$ 为根的子树内/外选一条路径的异或和最大值，答案即 max ⁡ 1 ≤ x ≤ n { i n [ x ] + o u t [ x ] } \max\limits_{1 \le x \le n}{\{in[x]+out[x]\} } 1≤x≤nmax​{in[x]+out[x]}。
• 设 $x$ 在 $\text{DFS}$序 中编号为 $dfn[x]$，子树大小为 $size[x]$，可将 $in[x],out[x]$ 的求解表示成下面两种询问：
  • 求在 $[dfn[x],dfn[x]+size[x]-1]$ 任取两个数异或的最大值。
  • 求在 $[1,dfn[x]-1]\cup [dfn[x]+size[x],n]$ 任取两个数异或的最大值。
• 可将序列复制一遍，使第二种询问也变为连续的区间。
• 套用回滚莫队模板即可，时间复杂度 $\mathcal{O}(n\sqrt{n}\log w)$。

算法二

• 先求出最大异或和路径的两个端点 $dx,dy$，令树根为 $dx$ 。
• 不在该路径上的点被划分成若干个互不相干的子树，若最终的答案包含路径 $(dx,dy)$，暴力求这些子树内路径的最大异或和即可。
• 若最终的答案不包含 $(dx,dy)$，只需要求这条路径上所有点的 $in[x],out[x]$ 即可，类似算法一中的转换，由于此时询问的区间均为包含关系，每个数插入 $\text{Trie}$ 的次数为 $\mathcal{O}(1)$，同样可以暴力求解。
• 时间复杂度 $\mathcal{O}(n\log w)$。

典例2 洛谷P5386

• 令 $B_{A_i}=i$，对于每个询问 $(l,r,x,y)$，令 $C_{B_i}=1(x\le i\le y)$，则问题转化对于数组 $C$ 的 $[l,r]$，设每段连续 1 的长度为 $le{n}_i$，求 $\sum \frac{le{n}_i(le{n}_i+1)}{2}$。
• 容易想到外层套一个莫队，内层用线段树维护答案，时间复杂度 $\mathcal{O}(n\sqrt{n}\log n)$，常数过大难以通过。
• 将内层改为分块，并用并查集维护连续的 1，因为不方便删除将外层改为回滚莫队，时间复杂度不变，但常数小了很多。
• 注意到每个位置的插入操作至多只有一次，并且我们在合并连续 1 的过程中只关心每段连续 1 的起点和终点，我们只需要在每段连续 1 的起点处记录终点、在终点处记录起点即可 $\mathcal{O}(1)$ 完成合并。
• 时间复杂度 $\mathcal{O}(n\sqrt{n})$。

二次离线莫队

• 设 $f(x,l,r)$ 表示已经插入了区间 $[l,r]$、现在插入单点 $x$ 对答案产生的贡献。
• 一般莫队共有四种指针的移动，设当前区间为 $[tl,tr]$，目标区间为 $[l,r]$，这里以 $tr<r$ 为例，其它三种移动同理。
• 每次移动即

$$[tl,x-1]\to [tl,x](tr<x\le r)$$

​ 记 $F(x,r)=f(x,1,r)$，对答案产生的贡献为
$$f(x,tl,x-1)=F(x,x-1)-F(x,tl-1)$$
​ 其中 $F(x,x-1)$ 很容易预处理，$F(x,tl-1)$ 则可以通过扫描线将询问区间 $[tr+1,r]$ 挂在 $tl-1$ 处暴力询问得到。

• 如上所述，二次离线莫队即是把莫队移动的操作预处理以降低总的时间复杂度。
• 常见于询问区间内符合某种性质的点对数，莫队的单次移动可看一次询问（查询符合条件的点数）和一次修改（加入该点），设单次询问的复杂度为 $\mathcal{O}(f(n))$，单次修改的复杂度为 $\mathcal{O}(g(n))$ ，则上述做法使总时间复杂度由 $\mathcal{O}(n\sqrt{n}(f(n)+g(n)))$ 降至 $\mathcal{O}(ng(n)+n\sqrt{n}f(n))$，且空间复杂度依然为 $\mathcal{O}(n)$。

	// 假定 F(x, x) = F(x, x - 1)，sum 数组为 F(x, x - 1) 的前缀和
	// 以下为扫描线预处理部分，注意 ans 数组存储的只是最终答案的差分形式
	for (int i = 1; i <= m; ++i)
	{
		int l = q[i].l, r = q[i].r;
		if (tr < r)
		{
			v[tl - 1].push_back(segQuery(tr + 1, r, -1, i));
			ans[i] += sum[r] - sum[tr];
			tr = r;
		}	
		if (tr > r)
		{
			v[tl - 1].push_back(segQuery(r + 1, tr, 1, i));
			ans[i] -= sum[tr] - sum[r];
			tr = r;
		}
		if (tl < l)
		{
			v[tr].push_back(segQuery(tl, l - 1, -1, i));
			ans[i] += sum[l - 1] - sum[tl - 1];
			tl = l;
		}
		if (tl > l)
		{
			v[tr].push_back(segQuery(l, tl - 1, 1, i));
			ans[i] -= sum[tl - 1] - sum[l - 1];
			tl = l;
		}
	}
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

树上启发式合并

• 即 $\text{dsu on tree}$，解决的问题类型如下：

  • 允许离线。
  • 询问关于以某点 $x$ 为根的子树内的信息。
  • 询问的信息在遍历子树时容易维护。

• 先将所有询问挂在对应的子树根结点 $x$ 上，考虑先遍历子结点 $y$ 的子树处理其询问，除了最后一个子树外，每遍历完一棵子树就要清除它的影响，而最后一棵子树的信息则可以继承给 $x$。

• 我们令最后一棵子树为以重儿子为根的子树，由重链剖分的性质，从根到某结点的路径上的轻边个数为 $\mathcal{O}(\log n)$，因此每个点被清除的次数为 $\mathcal{O}(\log n)$。

• 设计算单点贡献的时间复杂度为 $\mathcal{O}(k)$，总时间复杂度 $\mathcal{O}(kn\log n)$。

• 预处理同重链剖分，具体算法流程如下：

  1. 遍历所有轻儿子，处理完某一个轻儿子后就清除它的影响。
  2. 遍历重儿子。
  3. 加上子树根结点 $x$ 的贡献。
  4. 回答询问。

inline void addSubtree(int x)
{
	for (int i = pos[x], im = pos[x] + sze[x] - 1; i <= im; ++i)
		addCol(col[idx[i]]);
}

inline void decSubtree(int x)
{
	for (int i = pos[x], im = pos[x] + sze[x] - 1; i <= im; ++i)
		decCol(col[idx[i]]);
}

inline void dfsTraverse(int x)
{
	for (arc *e = adj[x]; e; e = e->nxt)
	{
		int y = e->to;
		if (y == fa[x] || y == son[x])
			continue ;
		dfsTraverse(y);
		decSubtree(y);
	}
	if (son[x])
		dfsTraverse(son[x]);
	addCol(col[x]);
	for (arc *e = adj[x]; e; e = e->nxt)
	{
		int y = e->to;
		if (y == fa[x] || y == son[x])
			continue ;
		addSubtree(y);
	}
	for (int i = 0, im = ask[x].size(); i < im; ++i)
	{
		pair<int, int> y = ask[x][i];
		ans[y.second] = sum[y.first];
	}
}
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

虚树

• 对于 $\text{DFS}$序 连续的三个点 $x,y,z$，我们有 $\text{LCA}(x,z)=\text{LCA}(x,y)$ 或 $\text{LCA(y,z)}$，因此只要将所有关键点按照 $\text{DFS}$序 排序，再将所有 $\text{LCA}(x_i,x_{i+1})$ 与所有 $x_i$ 作为虚树中的结点即可。
• 将虚树中的所有结点按照 $\text{DFS}$序 排序，按照 $\text{DFS}$序 的顺序模拟虚树的 $\text{DFS}$，用栈维护虚树中的根到当前结点的那一条路径，不难得到虚树结点之间的连边。
• 对于树上任意 $k$ 个点的 $\text{LCA}$，类比上述结论，可知即为 $k$ 个点中 $\text{DFS}$序 最小和最大的点的 $\text{LCA}$。

inline bool cmp(const int &x, const int &y)  
{
	return dfn[x] < dfn[y];
}

inline bool isSubtree(int x, int y)
{
	return dfn[y] >= dfn[x] && dfn[y] <= dfn[x] + sze[x] - 1;
}

inline void auxTree()
{
    top = 0; 
    std::sort(vir + 1, vir + m + 1, cmp);
    for (int i = 1; i <= m; ++i)
    	key[vir[i]] = true;
	for (int i = 1, im = m; i < im; ++i)
		vir[++m] = queryLCA(vir[i], vir[i + 1]);
	std::sort(vir + 1, vir + m + 1, cmp);
	m = std::unique(vir + 1, vir + m + 1) - vir - 1;
	for (int i = 1; i <= m; ++i)
	{
		while (top && !isSubtree(stk[top], vir[i]))
			--top;
		if (top)
			par[vir[i]] = stk[top];
		stk[++top] = vir[i];
	}
} 
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