字符串选讲

树状数组维护区间哈希值

重点, 区间长度 = \(lowbit(x)\)

#include<bits/stdc++.h>

using namespace std;

using int128 = __int128;

using LL = long long;

const int N = 1e6 + 6;

LL c[4][N], sum, bpow[N], b = 100591, mod = 1e18 + 31, u;
int n, q, op, l, r, x;
char cs;
string s;

int lowbit(int x){
  return x & -x;
}

void updata(int id, int x, LL k){
  for(u = x; x <= n; c[id][x] = ((c[id][x] + (int128)(k) * bpow[x - u] % mod) % mod + mod) % mod, x += lowbit(x)){
  }
}

LL getsum(int id, int x){
  for(sum = 0, u = 1; x; sum = ((sum + (int128)(c[id][x]) * u % mod) % mod + mod) % mod, u = (int128)(u) * bpow[lowbit(x)] % mod, x -= lowbit(x)){
  }
  return sum;
}

LL query(int id, int l, int r){
  return (getsum(id, r) - (int128)(getsum(id, l - 1)) * bpow[r - l + 1] % mod + mod) % mod;
}

int main(){
  cin >> n >> q >> s;
  s = ' ' + s;
  bpow[0] = 1;
  for(int i = 1; i <= n; ++i){
    bpow[i] = (int128)(bpow[i - 1]) * b % mod;
  }
  for(int i = 1; i <= n; ++i){
    updata(0, i, s[i] - 'a' + 1);
    updata(1, i, s[n - i + 1] - 'a' + 1);
  }
  while(q--){
    cin >> op;
    if(op == 1){
      cin >> x >> cs;
      updata(0, x, (-(s[x] - 'a' + 1) + mod) % mod);
      updata(1, n - x + 1, (-(s[x] - 'a' + 1) + mod) % mod);
      s[x] = cs;
      updata(0, x, (s[x] - 'a' + 1));
      updata(1, n - x + 1, (s[x] - 'a' + 1));
    }
    else{
      cin >> l >> r;
      cout << (query(0, l, r) == query(1, n - r + 1, n - l + 1) ? "Yes\n" : "No\n");
    }
  }
  return 0;
}

失配树

每个元素 KMP 的 nxt 就是这个元素的父亲节点, 这样, 每个节点的祖先都是它的前缀