复杂数据结构（2）

1. DLX之精确覆盖问题

2. DLX之重复覆盖问题

3. 左偏树

4. 后缀数组

• 字符串下标从 1 开始。共 n 个后缀，复杂度 $O(n\log n)$，将后缀按照字典序排序。
• $sa[i]$：排名第 $i$ 位的后缀是第几个后缀
• $rk[i]$：第 $i$ 个后缀的排名是多少
• $height[i]$：$sa[i]$ 和 $sa[i-1]$ 的最长公共前缀，即 $lca(i,i-1)$
• $lca(i,j)$ 后缀排名第 i 和第 j 的字符串的最长公共前缀。有如下性质：
  • $lca(i,j)=lca(j,i)$.
  • $lca(i,i)=len(i)$.
  • lca(i,j)=min{lca(i,k),lca(k,j)}lca(i, j) = min\\{lca(i, k), lca(k, j)\\}lca(i,j)=min{lca(i,k),lca(k,j)}.
• 定义 $h(i)=h(i-1)-1.$

2715. 后缀数组

• 题意：给定一个长度为 $n$ 的字符串，只包含大小写英文字母和数字。将字符串中的 $n$ 个字符的位置编号按顺序设为 $1\sim n$。并将该字符串的 $n$ 个非空后缀用其起始字符在字符串中的位置编号表示。现在要对这 $n$ 个非空后缀进行字典序排序，并给定两个数组 $SA$ 和 $Height$。排序完成后，用 $SA[i]$ 来记录排名为 $i$ 的非空后缀的编号，用 $Height[i]$ 来记录排名为 $i$ 的非空后缀与排名为 $i-1$ 的非空后缀的最长公共前缀的长度（$1\le i\le n$）。特别的，规定 $Height[1]=0$。请你求出这两个数组。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 1000010;int N, M;
char s[maxn];
//x是第一关键字，y是第二关键字，c是出现的次数
int sa[maxn], x[maxn], y[maxn], c[maxn], rk[maxn], height[maxn];void get_sa() {//x[i]是第i个元素的第一关键字for (int i = 1; i <= N; i++) c[x[i]] = s[i]]++;for (int i = 2; i <= M; i++) c[i] += c[i - 1];for (int i = N; i >= 1; i--) sa[c[x[i]]--] = i;for (int k = 1; k <= N; k <<= 1) {int num = 0;//y[i]表示第二关键字排名为i的数，第一关键字的位置//第n-k+1到第n位是没有第二关键字的 所以排名在最前面for (int i = N - k + 1; i <= N; i++) y[++num] = i;//排名为i的数 在数组中是否在第k位以后//如果满足(sa[i]>k) 那么它可以作为别人的第二关键字，就把它的第一关键字的位置添加进y就行了for (int i = 1; i <= N; i++) {if (sa[i] > k) {y[++num] = sa[i] - k;}}for (int i = 1; i <= M; i++) c[i] = 0;for (int i = 1; i <= N; i++) c[x[i]]++;for (int i = 2; i <= M; i++) c[i] += c[i - 1];for (int i = N; i; i--) sa[c[x[y[i]]]--] = y[i], y[i] = 0;swap(x, y);x[sa[1]] = 1, num = 1;for (int i = 2; i <= N; i++) {x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++num;}if (num == N) break;M = num;}
}void get_height() {for (int i = 1; i <= N; i++) rk[sa[i]] = i;for (int i = 1, k = 0; i <= N; i++) {if (rk[i] == 1) continue;if (k) k--;int j = sa[rk[i] - 1];while (i + k <= N && j + k <= N && s[i + k] == s[j + k]) k++;height[rk[i]] = k;}
}int main() {scanf("%s", s + 1);N = strlen(s + 1), M = 122;get_sa();get_height();for (int i = 1; i <= N; i++) printf("%d ", sa[i]);puts("");for (int i = 1; i <= N; i++) printf("%d ", height[i]);puts("");return 0;
}

《挑战程序设计竞赛》板子

• 代码很短，复杂度是 O(nlog⁡2n)O(n\\log^2n)O(nlog2n)

char str[maxn];
//rk[i] 表示下标为i开头后缀的排名
//sa[i] 表示第i小的后缀首字母对应原字符串下标。
int rk[maxn], sa[maxn], tmp[maxn];
int N, k;
bool cmp(int i, int j)
{if(rk[i] != rk[j]) return rk[i] < rk[j];else{int ri = i + k <= N ? rk[i + k] : -1;int rj = j + k <= N ? rk[j + k] : -1;return ri < rj;}
}
//if s is a string, please use: get_sa(char s[], int sa[])
void get_sa(int S[], int sa[])
{for(int i = 0; i <= N; i++){sa[i] = i;rk[i] = i < N ? S[i] : -1;}for(k = 1; k <= N; k <<= 1){sort(sa, sa + N + 1, cmp);tmp[sa[0]] = 0;for(int i = 1; i <= N; i++){tmp[sa[i]] = tmp[sa[i - 1]] + (cmp(sa[i - 1], sa[i]) ? 1 : 0);}for(int i = 0; i <= N; i++){rk[i] = tmp[i];}}
}

5. 后缀自动机

• 首先要区分一个概念：子序列在原序列中可以不连续，子串在原串中必须连续
• SAM是个状态机。一个起点，若干终点。原串的所有子串和从SAM起点开始的所有路径一一对应，不重不漏。所以终点就是包含后缀的点。
• 每个点包含若干子串，每个子串都一一对应一条从起点到该点的路径。且这些子串一定是里面最长子串的连续后缀。
• SAM问题中经常考虑两种边：
  • 普通边，类似于Trie。表示在某个状态所表示的所有子串的后面添加一个字符。
  • Link、Father。表示将某个状态所表示的最短子串的首字母删除。这类边构成一棵树。
• SAM的构造思路
  • endpos(s)：子串s所有出现的位置（尾字母下标）集合。SAM中的每个状态都一一对应一个endpos的等价类（例如 “abcab”, endpos(“ab”) = {2, 5}）。
  • endpos的性质：
    • 令 s1,s2 为 S 的两个子串 ，不妨设 |s1|≤|s2| （我们用 |s| 表示 s 的长度 ，此处等价于 s1 不长于 s2 ）。则 s1 是 s2 的后缀当且仅当 $endpos(s1)\supseteq endpos(s2)$ ，s1 不是 s2 的后缀当且仅当 $endpos(s1)\cap endpos(s2)=\varnothing$
    • 两个不同子串的endpos，要么有包含关系，要么没有交集。
    • 两个子串的endpos相同，那么短串为长串的后缀。
    • 对于一个状态 st ，以及任意的 longest(st) 的后缀 s ，如果 s 的长度满足：$|shortest(st)|\le |s|\le |longsest(st)|$ ，那么 $s\in substrings(st)$ 。

2766. 后缀自动机

• 给定一个长度为 $n$ 的只包含小写字母的字符串 $S$。对于所有 $S$ 的出现次数不为 $1$ 的子串，设其 $value$ 值为该子串出现的次数 $\times$ 该子串的长度。请计算，$value$ 的最大值是多少。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;//节点数量开成两倍
const int maxn = 2000010;
int tot = 1, last = 1;
struct Node {int len, fa;int ch[26];
}node[maxn];
char str[maxn];
typedef long long ll;ll f[maxn], ans;void extend(int c) {//求蓝边int p = last, np = last = ++tot;f[tot] = 1;node[np].len = node[p].len + 1;for (; p && !node[p].ch[c]; p = node[p].fa) node[p].ch[c] = np;if (!p) node[np].fa = 1;else {int q = node[p].ch[c];if (node[q].len == node[p].len + 1) node[np].fa = q;else {int nq = ++tot;node[nq] = node[q], node[nq].len = node[p].len + 1;node[q].fa = node[np].fa = nq;for (; p && node[p].ch[c] == q; p = node[p].fa) node[p].ch[c] = nq;}}
}
int h[maxn], e[maxn], ne[maxn], idx;void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}void dfs(int u) {//求绿边for (int i = h[u]; i != -1; i = ne[i]) {dfs(e[i]);f[u] += f[e[i]];}if (f[u] > 1) ans = max(ans, f[u] * node[u].len);
}int main() {scanf("%s", str);for (int i = 0; str[i]; i++) extend(str[i] - 'a');memset(h, -1, sizeof h);for(int i = 2; i <= tot; i++) add(node[i].fa, i);dfs(1);printf("%lld\\n", ans);return 0;
}

6. 点分治（树分治）

252. 树 - AcWing题库

给定一个有 $N$ 个点（编号 $0,1,...,N-1$）的树，每条边都有一个权值（不超过 $1000$）。树上两个节点 $x$ 与 $y$ 之间的路径长度就是路径上各条边的权值之和。求长度不超过 $K$ 的路径有多少条。

三种情况：路径两端点在不同的子树中；路径的一个端点是重心；路径的两个端点都在重心之中。复杂度 O(nlog⁡2n)O(n \\log^2 n)O(nlog2n)

#include<bits/stdc++.h>
using namespace std;
const int N = 10010, M = N * 2;
int n, m;
int h[N], e[M], ne[M], w[M], idx;inline void add(int a, int b, int c)
{e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}bool st[N];
int p[N], q[N];int get_size(int u, int fa)
{if(st[u]) return 0;int res = 1;for(int i = h[u]; i != -1; i = ne[i]){int v = e[i];if(v == fa) continue;res += get_size(v, u);}return res;
}int get_wc(int u, int fa, int tot, int& wc)
{if(st[u]) return 0;int sz = 1, ms = 0;for(int i = h[u]; i != -1; i = ne[i]){int v = e[i];if(v == fa) continue;int t = get_wc(v, u, tot, wc);ms = max(ms, t);sz += t;}ms = max(ms, tot - sz);if(ms <= tot / 2) wc = u;return sz;
}void get_dist(int u, int fa, int dist, int& qt)
{//printf("###\\n");if(st[u]) return;q[qt++] = dist;for(int i = h[u]; i != -1; i = ne[i]){int v = e[i];if(v == fa) continue;get_dist(v, u, dist + w[i], qt);}
}int get(int a[], int k)
{sort(a, a + k);int res = 0;for(int i = 0, j = k - 1; i < k && i <= j; i++){while(i < j && a[i] + a[j] > m) j--;res += j - i;}return res;
}int calc(int u)
{
//    printf("***\\n");if(st[u]) return 0;get_wc(u, -1, get_size(u, -1), u);st[u] = true;    int res = 0, pt = 0;for(int i = h[u]; i != -1; i = ne[i]){int qt = 0, v = e[i];get_dist(v, -1, w[i], qt);res -= get(q, qt);for(int k = 0; k < qt; k++){if(q[k] <= m) res++;p[pt++] = q[k];}}res += get(p, pt);for(int i = h[u]; i != -1; i = ne[i]) res += calc(e[i]);return res;
}int main()
{while(cin >> n >> m, n){memset(h, -1, sizeof h);memset(st, 0, sizeof st);idx = 0;for(int i = 1; i < n; i++){int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c), add(b, a, c);}printf("%d\\n", calc(0));}return 0;
}

264. 权值 - AcWing题库

给定一棵 $N$ 个节点的树，每条边带有一个权值。求一条简单路径，路径上各条边的权值和等于 $K$，且路径包含的边的数量最少。

也是考虑这三种情况：路径两端点在不同的子树中；路径的一个端点是重心；路径的两个端点都在重心之中。

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 200010, M = N * 2, S = 1000010, INF = 0x3f3f3f3f;
typedef pair<int, int> P;
int h[N], e[M], ne[M], w[M], idx;
int n, m;
P p[N], q[N];
int f[S];
bool st[N];
int ans = INF;
inline void add(int a, int b, int c)
{e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
int get_size(int u, int fa)
{if(st[u]) return 0;int sz = 1;for(int i = h[u]; i != -1; i = ne[i]){int v = e[i];if(v == fa) continue;sz += get_size(v, u);}return sz;
}
int get_wc(int u, int fa, int tot, int& wc)
{if(st[u]) return 0;int sz = 1, ms = 0;for(int i = h[u]; i != -1; i = ne[i]){int v = e[i];if(v == fa) continue;int t = get_wc(v, u, tot, wc);sz += t;ms = max(ms, t);}ms = max(ms, tot - sz);if(ms <= tot / 2) wc = u;return sz;
}
void get_dist(int u, int fa, int dist, int cnt, int& qt)
{if(st[u] || dist > m) return;q[qt++] = {dist, cnt};for(int i = h[u]; i != -1; i = ne[i]){int v = e[i];if(v == fa) continue;get_dist(v, u, dist + w[i], cnt + 1, qt);}
}
void calc(int u)
{if(st[u]) return;get_wc(u, -1, get_size(u, -1), u);st[u] = true;int pt = 0;for(int i = h[u]; i != -1; i = ne[i]){int v = e[i], qt = 0;get_dist(v, u, w[i], 1, qt);for(int k = 0; k < qt; k++){auto& t = q[k];if(t.x == m) ans = min(ans, t.y);ans = min(ans, f[m - t.x] + t.y);p[pt++] = t;}for(int k = 0; k < qt; k++){auto& t = q[k];f[t.x] = min(f[t.x], t.y);}}for(int k = 0; k < pt; k++){auto& t = p[k];f[t.x] = INF;}for(int i = h[u]; i != -1; i = ne[i]) calc(e[i]);
}
int main()
{scanf("%d%d", &n, &m);memset(h, -1, sizeof h);memset(f, 0x3f, sizeof f);for(int i = 1; i < n; i++){int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c), add(b, a, c);}calc(0);if(ans == INF) ans = -1;printf("%d\\n", ans);return 0;
}

7. 点分树（动态树分治）

动态点分治用来解决 带点权/边权修改 的树上路径信息统计问题。

8. CDQ分治

9. 仙人掌