ACdream群赛(5) D Palindrome

Problem D: Palindrome

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 319  Solved: 35
[Submit][Status][Web Board]

Description

Now we have a long long string, and we will have two kinds of operation on it.

C i y: change the ith letter to y;

Q i j: check whether the substring from ith letter to jth letter is a palindrome.

Input

There are multiple test cases.

The first line contains a string whose length is not large than 1,000,000.

The next line contains a integer N indicating the number of operations.

The next N lines each lines contains a operation.

All letters in the input are lower-case.

Output

For each query operation, output "yes" if the corresponding substring is a palindrome, otherwise output "no".

Sample Input

aaaaa 4 Q 1 5 C 2 b Q 1 5 Q 1 3

Sample Output

yes no yes

分析：在线段树上进行修改和查询操作，单点更新，成段询问。每段记录该段的正反两个哈希值，比较是否相等。程序缺点：未解决小概率的碰撞问题

#include<cstdio>
#include<cstring>
#define maxn (1<<20)
typedef long long u64;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define mod  12582917
 
typedef struct S {
    u64 left, right;
} TREE;
TREE tree[maxn << 1];
u64 exp[maxn];
char str[maxn];
char op[3];
 
void print_exp() {
    exp[0] = 1;
    for (int i = 1; i < maxn; ++i) {
        exp[i] = (exp[i - 1]*26) % mod;
    }
}
 
void build(int l, int r, int rt) {
    if (l == r) {
        tree[rt].left = tree[rt].right = str[l] - 'a';
        //      printf("l=%lld r=%lld\n",tree[rt].left,tree[rt].right);
        return;
    }
    int m = (l + r) >> 1;
    build(lson);
    build(rson);
    tree[rt].left = (exp[r - m] * tree[rt << 1].left + tree[rt << 1 | 1].left) % mod;
    tree[rt].right = (exp[m - l + 1] * tree[rt << 1 | 1].right + tree[rt << 1].right) % mod;
 
}
 
void update(int l, int r, int rt, int p, char ch) {
    if (l == r) {
        tree[rt].left = tree[rt].right = ch - 'a';
        // str[l] = ch;
        return;
    }
    int m = (l + r) >> 1;
    if (p <= m) {
        update(lson, p, ch);
    } else {
        update(rson, p, ch);
    }
    tree[rt].left = (exp[r - m] * tree[rt << 1].left + tree[rt << 1 | 1].left) % mod;
    tree[rt].right = (exp[m - l + 1] * tree[rt << 1 | 1].right + tree[rt << 1].right) % mod;
    //  printf("%d %d : l=%lld r=%lld\n",l,r,tree[rt].left,tree[rt].right);
}
 
TREE query(int l, int r, int rt, int a, int b) {
    if (l == a && r == b) {
        return tree[rt];
    }
    int m = (l + r) >> 1;
    if (b <= m) {
        return query(lson, a, b);
    } else if (a > m) {
        return query(rson, a, b);
    } else {
        TREE ans1, ans2, ans;
        ans1 = query(lson, a, m);
        ans2 = query(rson, m + 1, b);
        ans.left = (exp[b - m] * ans1.left + ans2.left) % mod;
        ans.right = (exp[m - a + 1] * ans2.right + ans1.right) % mod;
        return ans;
    }
}
 
int main() {
    int Q, len, i;
    int a, b;
    char ch[3];
    TREE ans;
    print_exp();
    while (scanf("%s", str + 1) != EOF) {
        len = strlen(str + 1);
        build(1, len, 1);
        scanf("%d", &Q);
        while (Q--) {
            scanf("%s", op);
            if (op[0] == 'C') {
                scanf("%d%s", &a, ch);
                update(1, len, 1, a, ch[0]);
            } else {
                scanf("%d%d", &a, &b);
                ans = query(1, len, 1, a, b);
                //    printf("l=%lld r=%lld\n",ans.left,ans.right);
                if (ans.left == ans.right) {
                    printf("yes\n");
                } else {
                    printf("no\n");
                }
            }
        }
    }
    return 0;
}


static int hash_mod[] = {
    17,             /* 0 */
    37,             /* 1 */
    79,             /* 2 */
    163,            /* 3 */
    331,            /* 4 */
    673,            /* 5 */
    1361,           /* 6 */
    2729,           /* 7 */
    5471,           /* 8 */
    10949,          /* 9 */
    21911,          /* 10 */
    43853,          /* 11 */
    87719,          /* 12 */
    175447,         /* 13 */
    350899,         /* 14 */
    701819,         /* 15 */
    1403641,        /* 16 */
    2807303,        /* 17 */
    5614657,        /* 18 */
    11229331,       /* 19 */
    22458671,       /* 20 */
    44917381,       /* 21 */
    89834777,       /* 22 */
    179669557,      /* 23 */
    359339171,      /* 24 */
    718678369,      /* 25 */
    1437356741,     /* 26 */
    2147483647      /* 27 (largest signed int prime) */
};