主席树模板2+字符串模板

主席树另一模板

在某个历史版本上修改某一个位置上的值

访问某个历史版本上的某一位置的值

每进行一次操作，生成一个新的版本。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 1000005
int read() {
    int x=0,f=1;char ch;
    do{ch=getchar();if(ch=='-') f=-1;} while(ch<'0'||ch>'9');
    do{x=x*10+ch-48;ch=getchar();} while(ch>='0'&&ch<='9');
    return x*f;
}

int rt[MAXN], idx;
int a[MAXN];
int n, m;
struct node {
    int l, r, val;
}tree[MAXN << 5];

int build(int l, int r) {
    int now = ++idx;
    if (l == r) {
        tree[now].val = a[l];
        return now;
    }
    int mid = l + r >> 1;
    tree[now].l = build(l, mid);
    tree[now].r = build(mid + 1, r);
    return now;
}

int update(int pre, int L, int R, int pos, int val) {
    int now = ++idx;
    tree[now] = tree[pre];
    if (L == R && L == pos) {
        tree[now].val = val;
        return now;
    }
    int mid = L + R >> 1;
    if (pos <= mid)  tree[now].l = update(tree[pre].l, L, mid, pos, val);
    else tree[now].r = update(tree[pre].r, mid + 1, R, pos, val);
    return now;
}

int query(int rt, int L, int R, int pos) {
    if (L == R) {
        return tree[rt].val;
    }
    int mid = L + R >> 1;
    if (pos <= mid) return query(tree[rt].l, L, mid, pos);
    else return query(tree[rt].r, mid + 1, R, pos);
}

int main() {
    n = read(), m = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    rt[0] = build(1, n);
    for (int i = 1; i <= m; i++) {
        int pre, opt, pos, val;
        pre = read(), opt = read(), pos = read();
        if (opt == 1) {
            val = read();
            rt[i] = update(rt[pre], 1, n, pos, val);
        }
        else {
            rt[i] = rt[pre];
            printf("%d\n", query(rt[pre], 1, n, pos));
        }
    }
    return 0;
}

扩展KMP

扩展 $KMP$ 可以在$O(N)$时间内求出给定字符串每个后缀与该字符串前缀的最大匹配长度。类似的，也可以在$O(N+M)$ 的时间内求出字符串 $A$ 每个后缀与字符串 $B$ 的最大匹配长度。

将 $B$ 定义为模式串，类似于 $KMP$ ，要先对 $B$ 进行一遍自匹配。再利用求出来的 $Z$ 函数进行 $A$ 串与 $B$ 串的匹配。

定义 $t$ 为模式串（被匹配的字符串），$s$ 为匹配串。

定义 $Z$ 函数：$z[i]$ 表示 $t$ 和 $t[i,m]$ （即以 $t[i]$ 开头的后缀）的最长公共前缀的长度。定义边界 $z[1] = 0$ 。

定义 $p$ 函数：$p[i]$ 表示 $s$ 和 $t[1, m]$ 的最长公共前缀长度。

有意思的是，如果某个位置 $p[i] = m$ ，表示模式串在位置 $i$ 出现，这就是标准的 $kmp$ 问题。所以国内一般称之为扩展 $kmp$ 算法，因为这是对 $kmp$ 算法的扩展。

下面若干样例展示了对于不同字符串的 $Z$ 函数

• $aaaaa = [0,4,3,2,1]$
• $aaabaab=[0,2,1,0,2,1,0]$
• $abacaba=[0,0,1,0,3,0,1]$

会从 $2$ 到 $n$ 顺次计算 $z[i]$ 的值。同样类似于 $kmp$ ，计算 $z[i]$ 的过程中，我们会利用已经计算好的 $z[1],...,z[i - 1]$ 。

先将 $z$ 函数的计算搁置一边，假设已经完成了 $z$ 函数的计算。开始进行 $S$ 串的匹配。

如下图，假设当前遍历到匹配串 $S$ 位置 $i$ ，即前 $i-1$ 个 $p[i]$ 值的位置已经计算得到。定义 $l,r$ ，$r$ 代表以 $l$ 为起始位置的字符匹配成功的最右端（最后一个未失配的位置）。根据匹配的定义，可以得出 $s[l,r]=t[1,r-l+1]$ 。

因为 $s[l,r]=t[1,r-l+1]$ ，又根据 $z$ 函数的定义，下图三个椭圆长度都相同，均为 $z[i - l + 1]$ 。同时 $s[l,r]=t[i-l+1,r-l+1]=t[1,r-i+1]$ ，所以 $p[i]=z[i-l+1]$ 。 但是此时有个最右端的限制，所以当前 $p[i]$ 应为 $min(r-l+1,z[i-l+1])$

根据定义，$r$ 是 $s[l,r]$ 和 $t[1,r-l+1]$ 最后一个相同的字符，所以 $s[r + 1]$ 必然不等于 $t[r-l+2]$ ，但是 $s[r+1]$ 是有可能等于 $t[i-l+2]$ 的，即 $s[i+p[i]]$ 有可能等于 $t[p[i] +1]$ 。若相等，就自增 $p[i]$ 直到指针越界或者失去匹配。就完成了 $p[i]$ 的求解。若匹配的最右端超过了 $r$ ，那么就要更新一下 $l$ 和 $r$ 为 $i$ 和 $i + p[i] - 1$

如何求解 $z$ 函数呢？根据定义可以发现，类似于 $kmp$ ，求解 $z[i]$ 的过程就是模式串 $t$ 自己和自己的匹配过程。

例题：询问 $q$ 次，回答有多少个位置满足 字符串 $S$ 从某一位置开始的后缀子串与 $B$ 的匹配长度恰好为 $x$ 。

#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define MAXN 200005
char s[MAXN];
char t[MAXN];
int n, m, q;
int z[MAXN]; //模式串自我匹配
int p[MAXN]; //匹配串大小
int cnt[MAXN]; //匹配长度对应的cnt

void getZ(char t[], int m) {
    for (int l = 0, r = 0, i = 2; i <= m; i++) {
        if (i <= r) z[i] = min(z[i - l + 1], r - i + 1);
        while (z[i] < m && i + z[i] <= m && t[z[i] + 1] == t[i + z[i]]) z[i]++;
        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }
}

int main() {
    cin >> n >> m >> q;
    scanf("%s", s + 1);
    scanf("%s", t + 1);
    getZ(t, m); //模式串自我匹配求Z函数
    for (int l = 0, r = 0, i = 1; i <= n; i++) {
        if (i <= r) p[i] = min(z[i - l + 1], r - i + 1);
        while (p[i] < m && i + p[i] <= n && t[p[i] + 1] == s[i + p[i]]) p[i]++;
        if (i + p[i] - 1 > r) {
            l = i;
            r = i + p[i] - 1;
        }
        cnt[p[i]]++;
    }
    while (q--) {
        int len;
        cin >> len;
        printf("%d\n", cnt[len]);
    }
    return 0;
}

马拉车

只能够解决最长回文串问题

和扩展 $kmp$ 的 $z$ 函数很像，且比 $z$ 函数简单。

定义 $p[i]$ 表示以 $i$ 为中心的最长回文半径。

首先将字符串 $xyxzasdfxyx$ 变成 $?x?y?x....?x?$ 的形式，这样所有原串的子串在新串中都统一成了奇数的形式。

类似于 $z$ 函数，维护一个以 $mid$ 为中心，右边界 $mr$ 最靠右的回文串，此时这个回文串的左边界是 $2 \times mid - r$。

若当前的 $i$ 小于 $mr$ ，$p[i]$ 等于 $p[l]$ 即 $p[2 * mid - r]$ 。由于有一个最右边界的限制，所以此时的 $p[i] = min(p[2 * mid -r], mr - i)$ 。然后看看能不能继续向两边扩展。

若当前的 $i$ 大于等于 $mr$ ，说明之前的结论无法共用，只能朴素暴力向两边扩展。

更新完当前位置 $i$ 的 $p[i]$ ，别忘了检查一下 $mr$ 是否可以更新。

#include<bits/stdc++.h>
using namespace std;
#define MAXN 20000005

int n;
char a[MAXN], b[MAXN];
int p[MAXN];

void init() {
    int k = 0;
    b[k++] = '$', b[k++] = '#';
    for (int i = 0; i < n; i++) b[k++] = a[i], b[k++] = '#';
    b[k++] = '^';
    n = k;
}

void manacher() {
    int mr = 0, mid;
    for (int i = 1; i < n; i++) {
        if (i < mr) p[i] = min(p[mid * 2 - i], mr - i);
        else p[i] = 1;
        while (b[i - p[i]] == b[i + p[i]]) p[i]++;
        if (i + p[i] > mr) {
            mr = i + p[i];
            mid = i;
        }
    }
}

int main() {
    scanf("%s", a);
    n = strlen(a);
    init();
    manacher();
    int res = 0;
    for (int i = 0; i < n; i ++ ) res = max(res, p[i]);
    printf("%d\n", res - 1);
    return 0;
}

最小最大表示法

指一个环形字符串的最小字典序表示方案。

#include <bits/stdc++.h>
using namespace std;
char a[2000010], b[2000010];
int calc_min(char s[]) {
    int n = strlen(s + 1);
    for (int i = 1; i <= n; i++)
        s[n + i] = s[i]; //将一条链变成一个区间
    int i = 1, j = 2, k;
    while (i <= n && j <= n)  {
        //在合法区间里面
        for (k = 0; k <= n && s[i + k] == s[j + k]; k++) //找出最大的不满足两个数相等的位置
            ;
        if (k == n) //如果完全一模一样
            break;
        if (s[i + k] > s[j + k])  {
            //如果大的话,**key**
            i += k + 1; //那么前面的数,肯定都不是最小表示.
            if (i == j)
                i++;
        }
        else {
            j += k + 1; //同理
            if (i == j)
                j++;
        }
    }
    return min(i, j);
}
int main() {
    scanf("%s", a + 1);
    int n = strlen(a + 1), x = calc_min(a);
    scanf("%s", b + 1);
    int m = strlen(b + 1), y = calc_min(b);
    a[x + n] = b[y + m] = 0;
    if (n == m && !strcmp(a + x, b + y)) {
        puts("Yes");
        puts(a + x);
    }
    else
        puts("No");
    return 0;
}

最大表示法只要在 $key$ 语句中把大于改成小于就行。

整除分块

形如 $\sum_{i = 1}^n{\lfloor \frac{n}{i} \rfloor}$ 之类的式子，可以用 $O(\sqrt{n})$ 的整除分块来优化。

对于每一个 $\lfloor\frac{n}{i} \rfloor$ 可以通过打表发现，有许多 $\frac{n}{ {i} }$ 的值是一样的，且呈块状分布。且每个块的最后一个数是 $n / (n / i)$ 。

for (int l = 1, r; l <= n; l = r + 1) {
    r = n / (n / l);
    ans += (r - l + 1) * (n / l);
}

如计算 $min(\lfloor \frac{m-1}{i} \rfloor \times i + n - m)$

$i \leq n$

式子即为

for (int l = 1, r; l <= n; l = r + 1) {
    r = (m - 1) / ((m - 1) / l);
    ans = min(ans, n - m + ((m - 1) / l) * l);
}