【2024-ZR-C Day 3】数据结构（2）
1. 倍增二分
一个奇怪的 trick，二分+倍增的复杂度是 \(O(n \log^2 n)\)，但注意到二分和倍增的结构相近，所以可以写在一起。
实际上倍增求 LCA 就是用这个 trick 实现的，代码如下。
for(int i = 19; i >= 1; i--)
if(to[x][i] 不满足条件)
x = to[x][i], ans += (1 << i);
x = to[x][0], ans++;
2. 序列分治
中心思想：每次解决跨过中点的所有区间，然后向两侧递归（解决两侧的区间）。
是一个树形结构，类似于只有查询、无修改的线段树。
3. CDQ 分治
3.1. 定义
普通的分治是：先解决根，再解决左右两边，即对分治树进行先序遍历。
而有些问题需要中序遍历或后序遍历才能解决，我们称这样的分治为 CDQ 分治。
（归并排序就是一个 CDQ 分治的例子。）
3.2. 二元最长偏序子序列
给定二元组序列 \(\{(x_n, y_n)\}\)，求出最长的子序列 \(\{(x'_k, y'_k)\}\)，使得子序列中 \(x'_{i-1} \le x'_i, \space y'_{i-1} \le y'_i\).
类似 LIS 问题的计算方式，先计算 \(f_{l \sim mid}\)，再计算左边对右边的贡献，最后计算 \(f_{mid + 1 \sim r}\).
4. 分块
4.1. 定义
分块指将序列分成若干个块的，在区间操作时将被完整包含的一块一起处理的思想，以平衡复杂度。
4.2. 应用
分块有常见的三种应用：
- 支持区间修改和查询，维护一个 tag。
例：区间加，区间求和。 - 本质并不是分块的回滚莫队（只支持区间询问）。
- 对操作序列分块。
依次处理每个块内的修改和查询，处理完每个块后进行一次重构。
由于在处理每个块时前面所有块的信息都已经处理好了，所以实际上对每个块只需要块内的信息，不需要再从头开始重复枚举。
5. 树状数组上二分
树状数组中，\(c_p\) 维护的是 \([p - \operatorname{lowbit(p)} + 1, \space p]\) 的信息。可以发现，与章节【1. 倍增二分】相类似地，二分的结构同样内置于树状数组。
例：找出 \(01\) 数组中的第 \(k\) 个 \(1\).
考虑树状数组上二分，从高位向低位依次确定 \(p\)，使得 \([1, p]\) 的和 \(< k\).
\(p + 1\) 即为第 \(k\) 个 \(1\) 的位置。
根据树状数组的性质，\(c_{p | 2 ^ i}\) 表示 \([p + 1, \space p | 2 ^ i]\) 的和。
则考虑在二分中动态维护 \(cur\) 表示 \([1, p]\) 的和，每次向前跳时加上 \(c_{p | 2 ^ i}\) 即可。
int find(int k)
{
int cur = 0, p = 0; // cur: 当前 [1, p] 的和
for(int i = 20; i >= 0; i--)
{
if((p | (1 << i)) <= n && cur + c[p | (1 << i)] <= k)
p |= (1 << i), cur += c[p];
}
return p + 1;
}
此算法的实现都是比较套路的，可以直接套板子。
6. 例题
6.1. P9361 [ICPC2022 Xi'an R] Contests
\(a\) 可以 \(k-\)间接战胜的人，一定是 \(m\) 段后缀，我们只关心每个榜单中排名最高的人。若 \(b\) 在某个后缀中，\(a\) 就可以 \((k+1)-\)战胜 \(b\).
考虑维护一些长度为 \(m\) 的数组 \(f_{i, j}\)，每个 \(f_{i, j}\) 表示第 \(i\) 个节点可以 \(2^j-\)战胜的人形成的 \(m\) 段后缀的开头。
转移：\(\displaystyle f_{i, j, k} = \min_{x \text{ 能被 } i \space 2^{j-1}-\text{间接战胜}} f_{x, j - 1, k}\).
考虑记录 \(suf_{i, j, k}\) 表示第 \(j\) 个榜单中，\(\displaystyle \min_{x \in [i, n]} f_{x, j - 1, k}\) 的值。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m, q, x, y, a[6][N], rk[6][N];
struct node
{
int val[6];
bool operator > (const node &nd) const
{
for(int i = 1; i <= m; i++)
if(val[i] <= nd.val[i]) return 0;
return 1;
}
} f[25][N], sufmin[6][N], nxt, s, t;
/*
a[i][j]: 第 i 场比赛第 j 名的人
rk[i][j]: 第 i 场比赛第 j 个人的排名
f[i][j]: j 向前跳 2^i 步走到的每个比赛里的最高排名
sufmin[i][j]: i ~ n 号人能走到的最高排名
*/
node makenode(int x)
{
node res;
for(int i = 1; i <= m; i++)
res.val[i] = rk[i][x];
return res;
}
node minnode(node x, node y)
{
node res;
// cout << '.';for(int j = 1; j <= m; j++) cout << y.val[j] << ' '; cout<<'\n';
for(int i = 1; i <= m; i++)
res.val[i] = min(x.val[i], y.val[i]);
return res;
}
int main()
{
ios :: sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= m; i++)
for(int j = 1; j <= n; j++)
cin >> a[i][j], rk[i][a[i][j]] = j;
for(int i = 1; i <= m; i++)
for(int j = n; j >= 1; j--)
{
sufmin[i][j] = makenode(a[i][j]);
if(j < n) sufmin[i][j] = minnode(sufmin[i][j], sufmin[i][j + 1]);
}
for(int i = 1; i <= n; i++)
{
f[0][i] = sufmin[1][rk[1][i]];
for(int j = 2; j <= m; j++)
f[0][i] = minnode(f[0][i], sufmin[j][rk[j][i]]);
}
for(int k = 1; k <= 20; k++)
for(int i = 1; i <= n; i++)
{
f[k][i] = f[k - 1][i];
for(int j = 1; j <= m; j++)
f[k][i] = minnode(f[k][i], f[k - 1][a[j][f[k - 1][i].val[j]]]);
}
cin >> q;
while(q--)
{
cin >> x >> y;
s = makenode(x), t = makenode(y);
// cout << "s: ";for(int j = 1; j <= m; j++) cout << s.val[j] << ' ';
// cout << '\n';
if(s > t)
{
int res = 2;
for(int i = 20; i >= 0; i--)
{
nxt = s;
for(int j = 1; j <= m; j++)
nxt = minnode(nxt, f[i][a[j][s.val[j]]]);
// for(int j = 1; j <= m; j++) cout << nxt.val[j] << ' ';
// cout << '\n';
if(nxt > t) s = nxt, res += (1 << i);
}
cout << (res > n ? -1 : res) << '\n';
}
else cout << "1\n";
}
return 0;
}