[Medium] P5310 [Ynoi2011] 遥远的过去

xiezheyuan2025/1/20约 1403 字大约 7 分钟

平衡树写错 $2$ 个小时，输麻了……

简要题意

给定一个长度为 $n$ 的序列 $a$ 和一个长度为 $m$ 的序列 $b$ ，有 $q$ 次操作，每次操作给出 $x,y$ ，表示令 $b_x\gets y$ 。

你需要在每次操作执行完成后，输出 $a$ 中有多少个长度为 $m$ 的子串与 $b$ 相似。定义两个序列是相似的，当且仅当离散化后两序列相同。

$1\leq n,m,q\leq 10^5,0\leq a_i\leq 2^{31}-1$ 。

思路

自己想出的一道 Ynoi！虽然这道题比较水就是了。

对于非传统的子串匹配问题，考虑哈希，不过这里的相同是离散化后相同，因此我们需要设计一个和排名相关的哈希函数：

f(A)=\sum_{i=1}^{m}(m-\mathrm{rank}(A_i))\cdot B^i

其中 $\mathrm{rank}(x)$ 表示 $x$ 在 $A$ 中的排名，至于为什么取 $m$ 与其的差，原因仅仅是实现比直接用 $\mathrm{rank}(A_i)$ 自然一点而已，并没有实质上的区别。

于是我们有 $f(A)=f(B)$ ，则可以认为 $A,B$ 相似。

现在我们只需要预处理出 $A$ 中所有长度为 $m$ 的子串的哈希值，并动态维护当前 $B$ 的哈希值，就可以轻易解决本问题。

先来考虑第二个问题，如何动态维护 $B$ 的哈希值？由于我们只有单点修改，可以将单点修改看成将这个位置的贡献删除，然后替换这个位置，再加上这个位置的贡献。

思考这个位置的贡献是什么，首先是这个位置本身的哈希值项 $(m-\mathrm{rank}(A_i))\cdot B^i$ ，这是容易处理的，另外的来自于排名。我们发现，对于每一个 $A_j$ ，若满足 $A_j\leq A_i$ ，则 $A_i$ 会对 $A_j$ 产生一个 $B^j$ 的贡献（来自排名信息）。我们采用平衡树维护 $B^j$ 的和即可。

最后考虑第一个问题，如何预处理出出 $A$ 中所有长度为 $m$ 的子串的哈希值？

不妨暴力处理出 $[n-m+1,n]$ 区间的哈希值，然后考虑将这个区间向左移动，模仿之前的过程。

你发现这样的问题是当我们移动区间的时候，会出现 $m-1$ 个元素的 $B^j$ 发生变化，如果打标记就太麻烦了。我们可以将 $B^j$ 中的 $j$ 改为 $a$ 中真正的下标，这样求出来的哈希值只是整体多乘了一个 $B$ 的整数次幂，乘上逆元的对应次幂即可。

时间复杂度 $O((n+m+q)\log n)$ 可以通过本题。

代码

平衡树用的是 WBLT。

#include <bits/stdc++.h>
#define ls(x) (son[x][0])
#define rs(x) (son[x][1])
using namespace std;

constexpr double alpha = 0.2928932188134524;
using ui64 = unsigned long long;
const int N = 1e5 + 5;
constexpr ui64 BASE = 1145141, BASE_INV = 5871511968970297629ull;
int val[N << 1], siz[N << 1], son[N << 1][2], stk[N << 1], top, tot;
ui64 sumt[N << 1];

void delnode(int i){ stk[++top] = i; }
bool leaf(int i){ return !ls(i); }

void pushup(int i){
    if(leaf(i)) return;
    siz[i] = siz[ls(i)] + siz[rs(i)];
    val[i] = val[rs(i)];
    sumt[i] = sumt[ls(i)] + sumt[rs(i)];
}

int newnode(int v, ui64 s){
    int i = top ? stk[top--] : ++tot;
    val[i] = v, sumt[i] = s, siz[i] = 1;
    ls(i) = rs(i) = 0;
    return i;
}

void rotate(int i, bool d){
    swap(ls(i), rs(i));
    swap(ls(son[i][d ^ 1]), rs(son[i][d ^ 1]));
    swap(son[son[i][d ^ 1]][d ^ 1], son[i][d]);
    pushup(son[i][d ^ 1]), pushup(i);
}

void maintain(int i){
    if(leaf(i)) return;
    bool d = 1;
    if(siz[ls(i)] < alpha * siz[i]) d = 1;
    else if(siz[rs(i)] < alpha * siz[i]) d = 0;
    else return;
    if(siz[son[son[i][d]][d ^ 1]] * (1 - alpha) >= siz[son[i][d]] * (1 - 2 * alpha)){
        rotate(son[i][d], d ^ 1);
    }
    rotate(i, d);
}

void insert(int i, int v, ui64 s){
    if(leaf(i)){
        int p = newnode(val[i], sumt[i]), q = newnode(v, s);
        if(val[i] > v) swap(p, q);
        ls(i) = p, rs(i) = q;
        return pushup(i);
    }
    insert(v <= val[ls(i)] ? ls(i) : rs(i), v, s);
    pushup(i), maintain(i);
}

void del(int &i, int v){
    bool d = (v <= val[ls(i)]) ^ 1;
    if(leaf(son[i][d])) delnode(son[i][d]), delnode(i), i = son[i][d ^ 1];
    else del(son[i][d], v), pushup(i), maintain(i);
}

ui64 query(int i, int v){
    if(leaf(i)) return val[i] <= v ? sumt[i] : 0;
    if(v <= val[ls(i)]) return query(ls(i), v);
    else return query(rs(i), v) + sumt[ls(i)];
}

int rnk(int i, int v){
    if(leaf(i)) return 1;
    if(v <= val[ls(i)]) return rnk(ls(i), v);
    else return rnk(rs(i), v) + siz[ls(i)];
}

void clear(int i){
    delnode(i);
    if(!leaf(i)) clear(ls(i)), clear(rs(i));
}

int n, m, q, a[N], b[N], root;
ui64 pw[N], pw_inv[N], f[N];
map<ui64,int> mp;

void init(){
    root = newnode(INT_MAX, 0), pw[0] = pw_inv[0] = 1;
    for(int i=1;i<=n;i++) pw[i] = pw[i - 1] * BASE;
    for(int i=1;i<=n;i++) pw_inv[i] = pw_inv[i - 1] * BASE_INV;
    for(int i=n-m+1;i<=n;i++) insert(root, a[i], pw[i]);
    for(int i=n-m+1;i<=n;i++) f[n - m + 1] += pw[i] * (m - rnk(root, a[i]));
    mp[f[n - m + 1] * pw_inv[n - m]]++;
    for(int i=n-m;i;i--){
        f[i] = f[i + 1];
        f[i] -= pw[i + m] * (m - rnk(root, a[i + m]));
        del(root, a[i + m]);
        f[i] -= query(root, a[i + m]);
        f[i] += query(root, a[i]);
        insert(root, a[i], pw[i]);
        f[i] += pw[i] * (m - rnk(root, a[i]));
        mp[f[i] * pw_inv[i - 1]]++;
    }
    clear(root);
    root = newnode(INT_MAX, 0);
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> q;
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=m;i++) cin >> b[i];
    init();
    for(int i=1;i<=m;i++) insert(root, b[i], pw[i]);
    ui64 b_hash = 0;
    for(int i=1;i<=m;i++) b_hash += pw[i] * (m - rnk(root, b[i]));
    while(q--){
        int p, v; cin >> p >> v;
        b_hash -= pw[p] * (m - rnk(root, b[p]));
        del(root, b[p]);
        b_hash -= query(root, b[p]);
        b[p] = v;
        b_hash += query(root, v);
        insert(root, v, pw[p]);
        b_hash += pw[p] * (m - rnk(root, v));
        cout << mp[b_hash] << '\n';
    }
    return 0;
}

// Written by xiezheyuan