HDU 3973 线段树+字符串hash

题目大意：

不断修改字符串中的字母，然后询问区间字符串是否处于已给定的字符串集合中

这里将原来的字符串集合保存到hash表中，当然用map，set都没有问题

修改查询都用线段树实现，自己的query函数写的有问题，按照网上的改了就没问题

写一下自己的理解，因为左右子树合并的时候，需要计算右子树生成的字符串的长度后，加上base的长度次方

而我们计算右子树中含有的字母数量，靠t-m ，而这个t 必然要处于 l , r 中，向下递归的时候注意修改s，t的区间，不然计算的长度会偏长

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <map>
  4 #include <set>
  5 #include <iostream>
  6 #define maxn 100010
  7 #define ls o<<1
  8 #define rs o<<1|1
  9 #define define_m int m=(l+r)>>1
 10 #define base 33
 11 #define MOD 1000007
 12 using namespace std;
 13 typedef unsigned long long ULL;
 14 
 15 ULL val[maxn<<2] , fac[maxn];
 16 int size[maxn<<2] , head[MOD+5] , k;
 17 char str[2000100];
 18 
 19 struct HashNode{
 20     ULL val;
 21     int next;
 22 }_hash[MOD];
 23 
 24 void insert(ULL key)
 25 {
 26     int pos = key%MOD;
 27     _hash[k].val = key , _hash[k].next = head[pos];
 28     head[pos] = k++;
 29 }
 30 
 31 bool search(ULL key)
 32 {
 33     int pos = key%MOD;
 34     for(int i=head[pos] ; ~i ; i=_hash[i].next)
 35         if(key == _hash[i].val) return true;
 36     return false;
 37 }
 38 
 39 void init()
 40 {
 41     fac[0]=1;
 42     for(int i=1;i<maxn;i++)
 43         fac[i]=fac[i-1]*base;
 44     memset(head , -1 , sizeof(head));
 45     k=0;
 46 }
 47 
 48 void push_up(int o)
 49 {
 50     val[o] = val[ls]*fac[size[rs]]+val[rs];
 51 }
 52 
 53 void build(int o , int l , int r)
 54 {
 55     size[o] = r-l+1;
 56     if(l==r){
 57         val[o] = (ULL)str[l];
 58         return ;
 59     }
 60     define_m;
 61     build(ls , l , m);
 62     build(rs , m+1 , r);
 63     push_up(o);
 64 }
 65 
 66 void update(int o , int l , int r , int pos)
 67 {
 68     if(l==r && l==pos){
 69         val[o] = (ULL)str[l];
 70         return ;
 71     }
 72     define_m;
 73     if(m>=pos) update(ls , l , m , pos);
 74     else update(rs , m+1 , r , pos);
 75     push_up(o);
 76 }
 77 
 78 ULL query(int o , int l , int r , int s , int t)
 79 {
 80     if(l>=s&&r<=t){
 81         return val[o];
 82     }
 83     define_m;
 84     if(m>=t) return query(ls , l , m , s , t);
 85     else if(m<s) return query(rs , m+1 , r , s , t);
 86     else return query(ls , l , m , s , m)*fac[t-m]+query(rs , m+1 , r , m+1 , t);//注意后面一个函数中左边界由s改为m+1
 87 }
 88 
 89 int main()
 90 {
 91     #ifndef ONLINE_JUDGE
 92         freopen("a.in" , "r" , stdin);
 93     #endif // ONLINE_JUDGE
 94     int T,q,n,cas=0;
 95     char qu[10];
 96     init();
 97     scanf("%d",&T);
 98 
 99     while(T--)
100     {
101         printf("Case #%d:\n",++cas);
102         scanf("%d",&n);
103         for(int i=1;i<=n;i++){
104             scanf("%s",str);
105             ULL cur = 0;
106             for(int j=0 ; j<strlen(str) ; j++)
107                 cur = cur*base+(ULL)str[j];
108             insert(cur);
109         }
110         scanf("%s",str);
111         int len=strlen(str);
112         build(1,0,len-1);
113         scanf("%d",&q);
114         int pos,s,t;
115         for(int i=1;i<=q;i++){
116             scanf("%s",qu);
117             if(qu[0]=='C'){
118                 scanf("%d%s",&pos,qu);
119                 str[pos]=qu[0];
120                 update(1,0,len-1,pos);
121             }
122             else{
123                 scanf("%d %d",&s,&t);
124                 if(search(query(1,0,len-1,s,t))) printf("Yes\n");
125                 else printf("No\n");
126             }
127         }
128     }
129     return 0;
130 }

HDU 3973 线段树+字符串hash

推荐阅读