原题链接：AC’s String

题意：给出 $n$ 个单词，再给出一个字符串，有 $m$ 次操作，每次修改字符串中的某一个字母，或询问字符串的某一个区间是否是一个单词。$T$ 组测试数据。
$n \leq 10^4$
$lensum(单词) \leq 2 · 10^6$
$len(字符串) \leq 10^5$

破题调死我了，辣鸡HDOJ比赛结束还查重

线段树维护字符串哈希

首先数据范围要求我们必须在 $mlogn$ 的时间复杂度内解决问题，
这样我们必然不可能每次查询都去遍历字符串，所以要用线段树维护字符串哈希来解决这个问题。

我用的哈希方式是y总教的 P = 131, ULL自然溢出的方式。

线段树维护区间哈希值，pushup可以用左子节点的哈希值乘以右子节点的长度加上右子节点的哈希值
大概这样 root.hash = left.hash * right.len + right.hash

单点修改就很好办了，但是查询中有一个很容易错的地方。

当我们的查询区间横跨左右两个子节点的时候，
递归到左子节点查询的时候需要把查询区间的右端点改为 $mid$
return query(u << 1, l, $mid$ ) * p[r - mid] + query(u << 1 | 1, l, r);
因为左区间的哈希值要乘一个p[r - mid]，这个r必须恰好是查询的区间右端点

C++ 代码

#include<cstring>
#include<cstdio>
#include<set>

using namespace std;

const int N = 100010, P = 131;

typedef unsigned long long LL;

struct note
{
    int l,r;
    LL h;
}tr[N * 4];

char s[N];
LL p[N];
int n;

LL haxi(char s[])
{
    LL res = 0;
    for(int i = 0; s[i]; i ++)  res = res * P + s[i];
    return res;
}

void build(int u, int l, int r)
{
    tr[u] = {l, r};
    if(l == r)
    {
        tr[u].h = s[l];
        return;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);

    tr[u].h = tr[u << 1].h * p[r - mid] + tr[u << 1 | 1].h;
}

void modify(int u, int x, char c)
{
    if(tr[u].l == tr[u].r)
    {
        tr[u].h = c;
        return;
    }

    int mid = tr[u].l + tr[u].r >> 1;
    if(x <= mid)  modify(u << 1, x, c);
    else  modify(u << 1 | 1, x, c);

    tr[u].h = tr[u << 1].h * p[tr[u].r - mid] + tr[u << 1 | 1].h;
}

LL query(int u, int l, int r)
{
    if(tr[u].l >= l and tr[u].r <= r)  return tr[u].h;

    int mid = tr[u].l + tr[u].r >> 1;
    if(r <= mid)  return query(u << 1, l, r);
    else if(l > mid)  return query(u << 1 | 1, l, r);
    return query(u << 1, l, mid) * p[r - mid] + query(u << 1 | 1, l, r);
}

set<LL> S;
int main()
{
    p[0] = 1;
    for(int i = 1; i < N; i ++)  p[i] = p[i - 1] * P;

    int T;
    scanf("%d", &T);
    for(int t = 1; t <= T; t ++)
    {
        memset(tr, 0, sizeof tr);
        S.clear();

        printf("Case #%d:\n", t);

        int n;
        scanf("%d", &n);

        while(n --)
        {
            scanf("%s", s);
            S.insert(haxi(s));
        }

        scanf("%s", s);
        n = strlen(s);
        build(1, 0, n - 1);

        int m;
        scanf("%d", &m);
        while(m --)
        {
            char op[2];
            scanf("%s", op);

            if(op[0] == 'Q')
            {
                int l, r;
                scanf("%d%d", &l, &r);
                if(S.count(query(1, l, r)))  puts("Yes");
                else  puts("No");
            }
            else
            {
                int x;
                char c[2];
                scanf("%d%s", &x, c);
                modify(1, x, c[0]);
            }
        }
    }
    return 0;
}