HDU3973 线段树 + 字符哈希

　　题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3973 , 线段树 + 字符哈希，好题。

　　又学了一种新的哈希方法，hhhh~

解法：

　　想法是用P进制的数来表示一个字符串，由于可能数太大，所以就将转换成是十进制后的数模long long的最大值，这样虽然也有可能冲突，但是概率会非常小。这里的P可以随意取一个素数(我取的是31)。

　　先用上面提到的哈希方法将W集合中的字符串都转成十进制数存在数组中，然后进行排序；每一次询问时候，将询问区间的子串转成十进制后二分查找是否在W集合中即可。

　　思路虽然简单，但是实现起来还是比较麻烦，尤其是有很多细节需要注意。

#include <iostream>

#include <cstdio>

#include <cmath>

#include <queue>

#include <vector>

#include <string>

#include <string.h>

#include <algorithm>

using namespace std;

#define LL __int64

#define lson l , m , rt << 1

#define rson m + 1 , r , rt << 1 | 1

const int maxn =  + ;

const int p = ;

char str[];

LL Hash[maxn << ] , P[maxn];

LL W[ + ];

void init()

{

    P[] = ;

    for(int i =  ; i <= maxn ; i++)

        P[i] = P[i - ] * p;

}

LL calhash(char str[])

{

    LL sum = ;

    for(int i =  ; str[i] != '\0' ; i++) {

        sum = sum * p + str[i] - 'a' + ;

    }

    return sum;

}

int binary_search(int l , int r , LL a[] , LL x)

{

    int m = (l + r) >> ;

    while(l <= r) {

        if(a[m] == x)

            return m;

        if(a[m] > x)

            r = m - ;

        if(a[m] < x)

            l = m + ;

        m = (l + r) >> ;

    }

    return -;

}

void PushUp(int l , int r , int rt)

{

    int m = (l + r) >> ;

    Hash[rt] = Hash[rt << ] * P[r - m] + Hash[rt <<  | ];

}

void build(int l , int r , int rt)

{

    if(l == r) {

        Hash[rt] = str[r] - 'a' + ;

        return;

    }

    int m = (l + r) >> ;

    build(lson);

    build(rson);

    PushUp(l , r , rt);

}

void update(int x , int l , int r , int rt)

{

    if(l == r) {

        Hash[rt] = str[x] - 'a' + ;

        return;

    }

    int m = (l + r) >> ;

    if(x > m)

        update(x , rson);

    else

        update(x , lson);

    PushUp(l , r , rt);

}

LL query(int L , int R , int l , int r , int rt)

{

    if(L <= l && R >= r) {

        return Hash[rt];

    }

    int m = (l + r) >> ;

    if(m < L)

        return query(L , R , rson);

    else if(m >= R)

        return query(L , R , lson);

    else

        return query(L , m , lson) * P[R - m] + query(m +  , R , rson);

}

int main()

{

    int n , m , T;

    char ch[] , s[];

    init();

    cin >> T;

    for(int k =  ; k <= T ; k++)

    {

        scanf("%d" , &n);

        for(int i =  ; i <= n ; i++) {

            scanf("%s" , str);

            W[i] = calhash(str);

        }

        sort(W +  , W + n + );

        scanf("%s" , str);

        int len = strlen(str);

        build( , len -  , );

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

        scanf("%d" , &m);

        while(m--) {

            scanf("%s" , ch);

            if(ch[] == 'Q') {

                int L , R;

                scanf("%d %d" , &L , &R);

                LL tmp = query(L , R ,  , len -  , );

                if(binary_search( , n , W , tmp) != -)

                    puts("Yes");

                else

                    puts("No");

            } else {

                int x;

                scanf("%d" , &x);

                scanf("%s" , s);

                str[x] = s[];

                update(x ,  , len -  , );

            }

        }

    }

    return ;

}

巴特西

HDU3973 线段树 + 字符哈希

最新文章

热门文章