URAL 1989 Subpalindromes(線分ツリー単点修正+文字列hash)

タイトル:

文字列が与えられ、長さは105であり、m個の操作m<=104がある.2つの操作があります.1.[l,r]区間のサブストリングに返信するかどうかを尋ねる.i番目の文字をcに変更します.

解析:

この問題は文字列ハッシュ+セグメントツリーで行い、セグメントツリーは区間のhash値をクエリーするために使用されます.2本の線分木を1本建てて、前から後ろへのhash値を維持し、もう1本は後ろから前へのhash値を維持します.では,文字列を返すか否かを判断するには,正逆区間のハッシュ値の和が等しいか否かを見ればよい.修正については、単点更新です.
my code

#include <cstdio>
#include <cstring>
#include <algorithm>
#define ls (o<<1)
#define rs (o<<1|1)
#define lson ls, L, M
#define rson rs, M+1, R
using namespace std;
typedef unsigned long long ll;
const int N = (int)1e5 + 10;
const int sigma_size = 33;

int n, m;
ll H[N];
char str[N], str2[N];

inline ll idx(char c) { return c - 'a' + 1; }
inline int get(int pos) { return n - pos + 1; }

void init() {
    H[0] = 1;
    for(int i = 1; i < N; i++) {
        H[i] = H[i-1] * sigma_size; 
    }
}

ll lsum[N<<2], rsum[N<<2];
void pushUp(int o, int L, int R) {
    int M = (L + R)/2;
    lsum[o] = H[R - M] * lsum[ls] + lsum[rs];
    rsum[o] = H[R - M] * rsum[ls] + rsum[rs];
}

void build(int o, int L, int R) {
    if(L == R) {
        lsum[o] = idx(str[L]);
        rsum[o] = idx(str2[L]);
        return ;
    }
    int M = (L + R) >> 1;
    build(lson);
    build(rson);
    pushUp(o, L, R);
}

void modify(int o, int L, int R, int pos, int op) {
    if(L == R) {
        if(op == -1) lsum[o] = idx(str[L]);
        else rsum[o] = idx(str2[L]);
        return ;
    }
    int M = (L + R) >> 1;
    if(pos <= M) modify(lson, pos, op);
    else modify(rson, pos, op);
    pushUp(o, L, R);
}

ll query(int o, int L, int R, int ql, int qr, int op) {
    if(ql <= L && R <= qr)
        return (op == -1) ? lsum[o] : rsum[o];
    int M = (L + R) >> 1;
    if(qr <= M) return query(lson, ql, qr, op);
    else if(ql > M) return query(rson, ql, qr, op);
    return query(lson, ql, M, op) * H[qr - M] + query(rson, M+1, qr, op);
}

int main() {
    char oper[20], c[5];
    int a, b;

    init();
    while(~scanf("%s", str+1)) {
        n = strlen(str+1);
        strcpy(str2+1, str+1);
        reverse(str2+1, str2+1+n);

        build(1, 1, n); 
        scanf("%d", &m);

        ll pre, suf;
        while(m--) {
            scanf("%s", oper);
            if(oper[0] == 'p') {
                scanf("%d%d", &a, &b);
                int mid = (a + b) >> 1;
                int flag = (a + b) & 1;
                pre = query(1, 1, n, a, mid, -1);
                suf = query(1, 1, n, get(b), get(mid+flag), 1);
                puts((pre == suf) ? "Yes" : "No");
            }else {
                scanf("%d%s", &a, c);
                str[a] = c[0];
                modify(1, 1, n, a, -1);

                str2[get(a)] = c[0];
                modify(1, 1, n, get(a), 1);
            }
        }
    }
    return 0;
}