数据结构总结
$CSP$要来了，写写总结，写得有点快。。。
按最近的复习计划来慢慢更新吧，大家喜欢的话可以收藏一下~
基本数据结构
栈
特性：$Stack$，先进先出的数据结构，一般采用数组模拟。
应用：普通栈的模拟（表达式计算、模拟）、单调栈（优化$DP$、模拟）、$dfs$模拟栈（虚树的构建）等。
队列
特性：$Queue$，先进后出的数据结构，一般采用数组模拟。
应用：普通队列的模拟（模拟、广搜）、单调队列（优化$DP$、模拟）等。
$Ps$：优先队列挺好用的~
链表与邻接表
特性：储存位置不连续，可在任意位置删除或插入元素的数据结构，但只能按顺序访问；一般采用数组模拟。对于邻接表，实质上也是链表，相当于就是把多个链表接到一个数组$head$上，从$head[i]$开始可以依次遍历挂在$head[i]$上的元素。
应用：普通链表的模拟（模拟）、树与图的存储方式等。
Hash
思想：把一个复杂信息通过$Hash$函数映射在我们能够控制的值域以内，从而简化信息的处理。
特性：在某些情况下，不同复杂信息的$Hash$值可能会相同。
补丁：使用$Hash$表。即在$head[hash()]$查询是否存在复杂信息，再更新。
$Ps$：
- $Hash$函数的构建是一个乱搞，模数$P$最好是质数，才能使模$P$群的规模尽量大。
- 食用$unsigned$ $long$ $long$或许得到更好的体验？
字符串相关
字符串Hash
特性：判断字符串是否相等，直接用它们的$Hash$值进行比较。
实现：
/* 预处理，保证BASE大于所有给字符分配的数值 */
for (int i = 1;i <= n; ++i) {
f[i] = f[i - 1] * BASE + (s[i] - 'a' + 1);
p[i] = p[i - 1] * BASE;
}
/* 判断操作 */
int l1 = read(), r1 = read(), l2 = read(), r2 = read();
int len1 = r1 - l1 + 1, len2 = r2 - l2 + 1;
if (f[r1] - f[l1 - 1] * p[len1] == f[r2] - f[l2 - 1] * p[len2]) puts("Yes");
else puts("No");
后缀数组
定义：对于一个字符串$S$，把它的所有后缀按字典序排列后，排名为$i$的后缀记为$SA[i]$，排名$i$与$i-1$的最长公共前缀的长度记为$Height[i]$。
实现：这里只讨论$O(nlong^2n)$的实现（$CSP$就算考到了也没人会去写$O(n)$的吧。。。）。
在之前求字符串$S$的$Hash$时我们已经知道了它所有前缀的$Hash$值，所以在$sort$中我们可以二分出第一个不相同的位置，然后进行比较。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define BASE 133
#define ll long long
#define ull unsigned long long
const int N = 300000 + 7;
using std :: sort;
inline int read() {
int res = 0; bool f = 0; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = 1; ch = getchar(); }
while (ch <= '9' && ch >= '0') { res = (res << 3) + (res << 1) + ch - '0'; ch = getchar(); }
return f ? (~ res + 1) : res;
}
char s[N];
int n, sa[N];
ull p[N], f[N];
inline int min(int a, int b) { return a < b ? a : b; }
inline bool check(int l1, int r1, int l2, int r2) {
ull t1 = f[r1] - f[l1] * p[r1 - l1];
ull t2 = f[r2] - f[l2] * p[r2 - l2];
return t1 == t2;
}
inline int get(int a, int b) {
int l = 0, r = min(n - a, n - b), mid;
while (l < r) {
mid = (l + r + 1) >> 1;
if (check(a, a + mid, b, b + mid)) l = mid;
else r = mid - 1;
}
return l;
}
inline bool cmp(int rk1, int rk2) {
int l = get(rk1, rk2);
return s[rk1 + l] < s[rk2 + l];
}
int main(){
scanf("%s", s);
n = strlen(s); p[0] = 1;
for (int i = 1;i <= n; ++i) {
f[i] = f[i - 1] * BASE + s[i - 1] - 'a' + 1;
p[i] = p[i - 1] * BASE;
sa[i] = i - 1;
}
sort(sa + 1, sa + 1 + n, cmp);
for (int i = 1;i <= n; ++i) printf("%d ", sa[i]);
puts("");
printf("0 ");
for (int i = 2;i <= n; ++i) printf("%d ", get(sa[i - 1], sa[i]));
return 0;
}
应用；有点多，但都很神奇。。。
KMP算法及最小表示法
KMP
讲解：点这里。。。曾经写过一篇比较详尽的讲解。。。懒癌晚期了。。。
实现：
inline void KMP() {
ans[1] = 1;
memset(f, 0, sizeof f);
for (int i = 2, j = 0;i <= m; ++i) {
while (j && p[j + 1] != p[i]) j = f[j];
if (p[j + 1] == p[i]) ++j;
f[i] = j, ans[i] = ans[j] + 1;
}
res = 1;
for (int i = 2, j = 0;i <= m; ++i) {
while (j && p[j + 1] != p[i]) j = f[j];
if (p[j + 1] == p[i]) ++j;
while ((j << 1) > i) j = f[j];
res = (res * (ll)(ans[j] + 1) % P) % P;
}
}
应用：字符串相关（各种神奇题目）。。。
好题推荐：NOI2014动物园。
最小表示法
思想：类似于$KMP$的继承思想，用三个指针$O(n)$遍历。
实现：
inline int get_min() {
int i = 1, j = 2, k;
while (i <= n && j <= n) {
for (k = 0;k < n && a[i + k] == a[j + k]; k ++);
if (k == n) break;
if (a[i + k] > a[j + k]) {
i = i + k + 1;
if (i == j) i ++;
}
else {
j = j + k + 1;
if (i == j) j ++;
}
}
return min(i, j);
}
应用：貌似有点窄啊。。。
Mannacher
讲解：洛咕题解。。。（我又懒了。。。
貌似同机房大佬发了一篇？
实现：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAX = 22000000 + 5;
inline int read(){
int f = 1, x = 0;char ch;
do { ch = getchar(); if (ch == '-') f = -1; } while (ch < '0'||ch>'9');
do {x = x*10+ch-'0'; ch = getchar(); } while (ch >= '0' && ch <= '9');
return f*x;
}
char ch[MAX];
int cnt;
inline void get() {
ch[cnt] = '$';
ch[++cnt] = '#';
char c = getchar();
while (c < 'a' || c > 'z') c = getchar();
while (c >= 'a' && c <= 'z') {
ch[++cnt] = c;
ch[++cnt] = '#';
c = getchar();
}
}
int p[MAX], maxr, mid, maxp;
int main(){
get();
for (int i = 1;i <= cnt; ++i) {
if (i < maxr) {
p[i] = min(p[(mid << 1) - i], maxr - i);
}
else p[i] = 1;
while (ch[i + p[i]] == ch[i - p[i]]) { p[i]++; }
if (p[i] + i > maxr) maxr = p[i] + i, mid = i;
if (p[i] > maxp) maxp = p[i];
}
printf("%d", maxp-1);
return 0;
}
应用：只要你出题人有脑洞。。。
Trie
特性：多字符串快速检索。就是一棵树，树上节点记录着字符，树上边对应是否存在指向某一节点的指针。
实现：
struct TRIE {
struct TREE { int son[26]; } tr[N << 2]; int p;
int f[N << 2];
inline void insert(char *a) {
int u = 1;
int len = strlen(a + 1);
for (int i = 1;i <= len; ++i) {
if (!tr[u].son[a[i] - 'a' + 1]) tr[u].son[a[i] - 'a' + 1] = ++p;
u = tr[u].son[a[i] - 'a' + 1];
}
f[u] ++;
}
inline int find(char *a) {
int u = 1, res = 0;
int len = strlen(a + 1);
for (int i = 1;i <= len; ++i) {
u = tr[u].son[a[i] - 'a' + 1];
res += f[u];
}
return res;
}
}t;
应用：只要你出题人有脑洞。。。
二叉堆
特性：支持插入、删除、查询最值的数据结构；一棵满足”堆性质”的二叉树。
应用：优化$DP$、模拟等。
用优先队列多好啊。。。
*笛卡尔树
见这个。。。或许能比较明白了？
*左偏树
特性：它实质上也是一个二叉堆，但是合并的时间复杂度比较优秀。至于什么斜堆、斐波拉契堆$CSP$之前就不学了$TAT$。。。
简析：每个节点维护几个信息：左右儿子、到右儿子的距离、值。然后每次$Merge$操作顺着右儿子一直递归合并下去，回溯上来后，若右儿子距离更大，就$Swap$左右儿子，记得更新距离。
详析：洛咕题解。（我又又懒了。。）
数据结构的进阶
并查集
特性：“名副其实”。维护不相交集合的信息，快速判断连通性，有两个基本操作，$find$，确定元素属于哪个集合，$merge$，合并子集。
理解：并查集实际上是维护了一个森林，同一棵树上的节点处于同一个集合。
小进阶：带权并查集、按秩合并、路径压缩。。。
应用：
- 在Kruskal最小生成树算法中，用于快速判断一条边的两个端点是否属于一个联通块。
- 在左偏树等可并堆中，用于快速判断两个元素是否已经属于同一个堆。
- 维护区间关系。
- …
树状数组
特性：运用了二进制思想，$lowbit(x)$表示十进制数$x$在二进制下最后一位$1$所在的位置的十进制数表示，能够快速维护所有满足前缀可加性的运算。其实也可以用类似于二分的思想让树状数组维护其他一些奇奇怪怪的东西。。。
应用：
-
快速维护所有满足前缀可加性的运算。
-
求逆序对。
线段树
上这个。
虽然后面的内容咕了很久，但前面的内容对于$CSP$足够了吧？
分块
咕咕咕中。。。
点分治
咕咕咕中。。。
平衡树
咕咕咕中。。。
离线分治
咕咕咕中。。。
可持久化
咕咕咕中。。。
nice
赞呢~