Acwing算法基础课：数据结构

单链表

有两种实现方式：

• 结构体实现
• 数组模拟

两者在功能上实际上是等价的，但后者比前者代码更简洁。前者使用真正的指针来引用节点，后者使用数组索引来引用节点。后者实际上相当于用数组索引“模拟”了一个地址空间。将数组定义为全局变量，因此也无需在运行时频繁申请空间。

应用：

• 存储图、树的邻接表

const int N = 100010;

int head, e[N], ne[N], idx;

void init(){
    head = -1;
    idx = 0;
}

void add_to_head(int x) {
    e[idx] = x;
    ne[idx] = head;
    head = idx++;
}

void insert(int k, int x) {
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx ++ ;
}

void remove(int k) {
    if (ne[k] != -1)
        ne[k] = ne[ne[k]];
}

void remove_head() {
    if (head != -1)
        head = ne[head];
}

双向链表

使用0、1号节点作为“伪节点”，作为链表的左右边界。由此，无需使用特殊的头插、头删函数。

const int N = 100010;

int e[N], l[N], r[N], idx;

void init(){
    l[0] = -1;
    r[0] = 1;
    l[1] = 0;
    r[1] = -1;
    idx = 2;
}

void remove(int k) {
    if (k<2) return;
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

void insert_right(int k, int x) {
    if (k==1) return;
    e[idx] = x;
    l[idx] = k;
    r[idx] = r[k];
    l[r[k]] = idx;
    r[k] = idx ++;
}

void insert_left(int k, int x) {
    if (k==0) return;
    e[idx] = x;
    l[idx] = l[k];
    r[idx] = k;
    r[l[k]] = idx;
    l[k] = idx ++ ;
}

数组模拟栈、队列

栈

int stk[N], tt;

// push
stk[++tt] = x;
// pop
tt--;
// not empty
tt>0

tt实际上作为栈指针，始终指向栈顶。但只有在tt>0时栈指针才有效，tt==0时表示栈为空。

队列

int q[N], hh=0, tt=-1;
// enqueue
q[++tt] = x;
// dequeue
hh++;
// not empty
hh<=tt

hh 队头指针，tt 队尾指针。元素从队尾入队，从队头出队。hh 和 tt 始终指向队头、队尾元素，但仅当 hh<=tt 时指针才有效。

单调栈和单调队列

单调栈

单调栈指一类情况，可以用栈来优化，在元素入栈时加以控制，使得栈中元素始终保持单调性（严格递增、递减），因此得名单调栈。基于单调性这一性质，可以进行求最值、二分等操作。

应用实例：

• 求数列中每个元素左侧离它最近的且小于它的元素

上例中有一性质：对栈中的元素 $ a_i, a_j (i < j) $ 若 $ a_i \ge a_j $ 则 $a_i$​ 一定不会是答案，可以删掉。

基于这一性质，在元素入栈前出栈所有小于等于它的元素，由此形成单调栈，栈顶即为所求元素（离它最近且小于它）。

int stk[100010], tt;

int main(){
    int n;
    scanf("%d", &n);
    for (int i=1; i<=n; i++) {
        int x;
        scanf("%d", &x);
        while (tt>0 && stk[tt]>=x) tt--;
        if (tt>0) printf("%d ", stk[tt]);
        else printf("-1 ");
        stk[++tt] = x;
    }
}

单调队列

考虑滑动窗口求最值问题，以求最小值为例，每次有右侧新元素x入队时，有下列性质：

对原队列中的元素 $a_i$ 若 $ a_i \ge x $ 则 $ a_i $ 不可能再作为答案，因为 $ x $ 在 $ a_i $ 右侧，一定比 $ a_i $ 晚出队，又比 $ a_i $ 小，因此可以删除 $ a_i $

由此又形成了“单调队列”，即队列中元素严格单调递增。队列最左边即为最小值；与单调栈类似，基于单调性可以进行求最值、二分等操作。

可以发现，上文所述实际是一个单调栈，而非“队列”，因为只有在右侧的入队、出队（可看作入栈、出栈），而没有左侧的出队。出于“滑动窗口”的要求，队列左侧需要在离开滑动窗口时出队，于是可称之为“单调队列”。

为了实现判断队列左侧是否已经离开滑动窗口，在队列中实际存储的是数列的下标。由下标可以间接引用数列的值，同时可以判断队列左侧是否已滑出窗口。

可见，单调队列可视为一种单调栈的扩展，即左侧可出队的单调栈。

int a[1000005], q[1000005], hh, tt;  
// a[]为原数列；q[]为单调队列，存储原数列下标，间接引用

// 核心代码，以求滑动窗口最小值为例：
hh=0, tt=-1;
for (int i=0; i<n; i++) { // 枚举滑动窗口的右端点
    if (hh <= tt && i-k+1 > q[hh]) hh++; // 判断队列左侧是否滑出窗口，若是则出队
    while (hh <= tt && a[q[tt]]>=a[i]) tt--;
    q[++tt] = i;
    if (i >= k-1) printf("%d ", a[q[hh]]); // 至少在形成滑动窗口后才输出
}

KMP

i 指向待匹配字符串 s[] ，j 指向模板串 p[]；当匹配失败时：

• 朴素算法：i 退回原位置的下一个位置，j 退回 1，然后重新比较
• KMP：i 只往前走，不往后退；匹配失败时，模板串向前移动到合适位置（即 j 向后退），继续尝试匹配

朴素算法向KMP的改进，利用了匹配失败时，i 指针前一部分匹配成功的信息。匹配失败时，i 不动，只需模板串向前移。向前移动应满足下列两条件：

1. 模板串向前移动后，应保证指针前的部分仍能重合（即前缀、后缀相等）
2. 向前移动的距离应尽量小，以免错过靠前的串（即公共前后缀程度应最大）

可以想象，如果能保证上面两条件，向后移动模板串 与 朴素算法中 i 跳回下一个位置重新匹配，效果是一样的：因为若不能重合（不满足上述条件1），即使 i 跳回下一个位置重新匹配，也会在到达原 i指针前失败（因为不重合）。条件2 保证了不会错过靠前的匹配串。因此，朴素算法跳回与直接按照next[]移动模板串的效果等价，而直接移动模板串节省了多次不必要的比较。

由此，需要求出最长公共前后缀长度的数组 next[]。next[i] = j 表示：

在串 p[1, i] 中，最长公共前后缀长度为 j ，即

p[1, j] = p[i-j+1, i] 且 j 为满足该条件的最大取值。

int n, m;
char p[100005], s[1000005]; // p[] 模板串； s[] 待匹配字符串；都从 1 开始存储
int ne[100005]; // ne[] 即 next[] 数组

int main(){
    cin >> n >> p+1 >> m >> s+1;
    
    // generate ne[]
    for (int i=2, j=0; i<=n; i++) {
        while (j && p[i] != p[j+1]) j=ne[j];
        if (p[i] == p[j+1]) j++;
        ne[i] = j;
    }
    
    // kmp
    for (int i=1, j=0; i<=m; i++) {
        while (j && s[i] != p[j+1]) j=ne[j];
        if (s[i] == p[j+1]) j++;
        if (j == n) {
            printf("%d ", i-n);
            j = ne[j]; // 匹配成功后，j应跳到ne[j]保证正确性，避免越界访问p[m+1]
        }
    }
}

注意事项：

• 使用ne作为next[]的名字防止命名冲突
• 实际是 $s_i$ 和 $ p_{j+1}$ 做比较，即模板串向前错一位；j==0表示“退无可退”，应继续比较下一个 i 。

Trie

一种树状数据结构，用来存储字符串的集合，提供快速查询某字符串数量的功能。

其中，字符串除狭义的由字符组成的字符串外，还可以指广义的串，例如数字可以理解为由0、1组成的串。

int son[N][26], cnt[N], idx; // cnt[] 数组为节点标记，指明每个串的数量
char tmp[N];

void insert(char *s) {
    int t=0; // 维护一个指针
    for (int i=0; s[i]; i++) {
        int u=s[i]-'a';
        if (!son[t][u]) son[t][u] = ++idx;
        t = son[t][u];
    }
    cnt[t] ++;
}

int query(char *s) {
    int t=0; // 维护一个指针
    for (int i=0; s[i]; i++) {
        int u=s[i]-'a';
        if (!son[t][u]) return 0;
        t = son[t][u];
    }
    return cnt[t];
}

作为一种树状数据结构，并没有使用邻接表存储指向子节点的指针，而使用定长数组（代码中的son[N][26])。

这样做的好处在于，可以$O(1)$快速索引子节点；由于一般字母表范围较小，也不占用过大空间。

题目：最大异或对

相比于原始的Trie树的query()函数有变形：“尽可能”找使得异或值最大的串。

关于解题思路的经验

• 别一上来就想找个最快的算法（O(1)？），可能会直接走进死胡同，白白浪费时间；可以根据数据范围猜测算法复杂度，不要有不切实际的期望
• 实在没思路的时候，先写暴力，然后再尝试优化可能是一个思路

并查集

一种树状数据结构，一个树对应一个集合，提供快速的集合合并、判断两元素是否位于同一集合的功能（使用路径压缩优化后，皆为O(1)）。

可在此基础上同时维护元素数量，边权等信息。

int p[N], cnt[N];

int find(int x) {
    if (p[x] != x) return p[x] = find(p[x]);
    return x;
}

题目：食物链

此题目中，集合的意义不是动物的种类（A/B/C），一个集合代表相互关系已知的动物的集合。

此外，维护一个逻辑距离（在find()中路径压缩时顺带被维护）。此逻辑距离属于一个模3同余加法群，两节点逻辑距离之差0、1、2可分别代表同类、吃、被吃的关系。这个模3同余加法群对应于包含A、B、C的“环状”食物链。

堆

一种完全二叉树，提供以下功能（以小根堆为例）：

1. 插入一个元素
2. 选取最小元素
3. 删除最小元素
4. 删除任一元素
5. 修改任一元素

前三项STL的priority_queue可以提供，后两项手写堆可以实现。

对于上述所有的功能，都可以经过up()和down()的组合来实现（向上调整、向下调整）。

由于是完全二叉树，可使用一个一维数组来存储。0号下标不用，1号节点表示根节点。2n、2n+1、n/2分别代表左子节点、右子节点和父节点。

int h[N], idx;

void up(int x) {
    while (x/2 && h[x/2] > h[x]) {
        swap(x/2, x);
        x /= 2;
    }
}

void down(int x) {
    int t=x;
    if (2*x <= idx && h[2*x] < h[t]) t=2*x;
    if (2*x+1 <= idx && h[2*x+1] < h[t]) t=2*x+1;
    if (t!=x) {
        swap(h[t], h[x]);
        down(t);
    }
}

题目：模拟堆

由于经常需要获得“第k个插入的数”，需要维护一个映射：

插入序号 <–> 堆中序号

up()和down()中的swap()全部用下面的heap_swap()替换：

int h[N], ph[N], hp[N], cnt, idx; // cnt 代表目前堆中元素个数，idx 代表已插入元素个数
// ph[] 插入序号->堆中序号
// hp[] 堆中序号->插入序号
void heap_swap(int a, int b) {
    swap(ph[hp[a]], ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

// 插入 x
h[++cnt] = x;
ph[++idx] = cnt;
hp[cnt] = idx;
up(cnt);
// 删除最小元素
heap_swap(1, cnt);
cnt --;
down(1);
// 删除第k个插入的数
k = ph[k];
heap_swap(k, cnt);
cnt--;
down(k), up(k);
// 修改第k个插入的数为x
k = ph[k];
h[k] = x;
down(k), up(k);

哈希表

哈希函数：(x % N + N) % N

N取质数可以降低冲突概率，从而稍微改善常数

拉链法

const int N = 100003; // 哈希表大小最好为质数；对于拉链法来说，大小可以差不多与数据规模同样大小

int h[N], e[N], ne[N], idx; 

void insert(int x) {
    int u = (x % N + N) % N; // !! 注意负数情况
    e[++idx] = x;
    ne[idx] = h[u];
    h[u] = idx;
}

bool find(int x) {
    int u = (x % N + N) % N; // !! 注意负数情况
    for (int i=h[u]; i; i=ne[i]) 
        if (e[i] == x)
            return true;
    return false;
}

开放寻址法

const int N = 300007, null = 0x3f3f3f3f;
// 开放寻址法中，哈希表大小N应设为数据规模的至少2~3倍
// 定义数据定义域外的一值（例如此题中0x3f3f3f3f>1*10^9）来表示空位

int h[N];

int get(int x) {
    int u = (x % N + N) % N;
    while (h[u] != null && h[u] != x) {
        u++;
        if (u==N) u=0;
    }
    return u;
}

定义一函数get()：若哈希表中存在该元素，则返回该元素下标；若不存在该元素，则返回第一个空位下标。

// 初始化
memset(h, 0x3f, sizeof h);
// 插入
h[get(x)] = x;
// 查询
h[get(x)] != null ? "Yes" : "No"

两种方法的比较

拉链法：常数稍小，性能更稳定不容易恶化；但比开放寻址法编码稍复杂

开放寻址法：数据结构简单（只有一个数组），代码简单（？）；常数稍大

字符串哈希

将字符串理解为一串P=131进制的大数（高位在前，低位在后），在模$2^{64}$意义下计算哈希（unsigned long long），从概率上来说哈希冲突概率极小。若两字符串哈希值相等，则可以认为两字符串相等（极大概率）。

可实现$O(n)$预处理，$O(1)$快速判断子串是否相等。

const int N = 100005, P = 131; // 采用P=131进制

typedef unsigned long long ull;

// 前缀哈希h[]和权重p[]
ull h[N], p[N]; 
char s[N];

// 计算某一子串哈希
ull get(int l, int r) {
    return h[r] - h[l-1] * p[r-l+1];
}

int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    scanf("%s", s+1); // 此题目中字符串下标从1开始
    
    // 预处理前缀哈希h[]和权重p[]
    p[0] = 1;
    for (int i=1; i<=n; i++) {
        h[i] = h[i-1] * P + s[i];
        p[i] = p[i-1] * P;
    }
    
    while (m--) {
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        puts(get(l1, r1) == get(l2, r2) ? "Yes" : "No");
    }
}

STL使用

1. priority_queue默认为大根堆，定义为小根堆的方法：

   priority_queue<int, vector<int>, greater<int>>

2. set/map由红黑树实现，维护一有序序列，基本操作的复杂度是$O(\log n)$

   unordered_set/unordered_map由哈希表实现，基本操作复杂度为$O(1)$

   两者提供类似功能，但红黑树支持lower_bound()和upper_bound()方法：

   lower_bound(x) 返回大于等于x的最小的数的迭代器 upper_bound(x) 返回大于x的最小的数的迭代器

   类似于二分。如无上述需要，使用哈希表效率更佳。