I

题目链接：

I - Magic

学习链接：

FZU - 2280 I - Magic

题目大意：

给你nn个字符串，每个字符串有一个值ww，有qq次询问，一共两种操作：一是“1,x,y”“1,x,y”表示把第xx个串的ww变为yy；二是“2,x”2,x”，输出第xx个串能放几次魔法。放魔法的条件是这样：用串x放魔法，如果在1~n个串中，一个串的ww不超过xx的ww并且xx是这个串的后缀，则算放了一次魔法，然后每次询问输出能放几个魔法。

具体思路：对于每个字符串hash一下，判断后缀，通过字符串hash判断就可以了。然后每次查询的时候O(n)查询就可以了。

AC代码：

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<cmath>
 4 #include<string>
 5 #include<cstring>
 6 using namespace std;
 7 # define ll long long
 8 # define ull unsigned long long
 9 # define inf 0x3f3f3f3f
10 const int ull base=131;
11 const int maxn = 2e5+100;
12 char str[maxn];
13 ull Hash[1000+10][1000+10],ind[maxn];
14 int val[maxn],length[maxn];
15 void init()
16 {
17     ind[0]=1;
18     for(int i=1; i<10000; i++)
19     {
20         ind[i]=ind[i-1]*base;
21     }
22 }
23 void hs(int id,char *s)
24 {
25     int len=strlen(s+1);
26     Hash[id][0]=0;
27     for(int i=1; i<=len; i++)
28     {
29         Hash[id][i]=Hash[id][i-1]*base+(ull)s[i];
30     }
31 }
32 ull getsub(int id,int l,int r)
33 {
34     return Hash[id][r]-Hash[id][l-1]*ind[r-l+1];
35 }
36 int n;
37 int cal(int t)
38 {
39     int ans=0;
40     ull tmp=getsub(t,1,length[t]);
41     for(int i=1; i<=n; i++)
42     {
43         if(val[i]>val[t]||length[i]<length[t])
44             continue;
45         ull tmpans=getsub(i,length[i]-length[t]+1,length[i]);
46         if(tmpans==tmp)
47             ans++;
48     }
49     return ans;
50 }
51 int main()
52 {
53     init();
54     int T;
55     scanf("%d",&T);
56     while(T--)
57     {
58         scanf("%d",&n);
59         for(int i=1; i<=n; i++)
60         {
61             scanf("%s",str+1);
62             hs(i,str);
63             scanf("%d",&val[i]);
64             length[i]=strlen(str+1);
65         }
66         int m;
67         scanf("%d",&m);
68         int op,st,ed;
69         for(int i=1; i<=m; i++)
70         {
71             scanf("%d",&op);
72             if(op==1)
73             {
74                 scanf("%d %d",&st,&ed);
75                 val[st]=ed;
76             }
77             else
78             {
79                 scanf("%d",&st);
80                 int ans=cal(st);
81                 printf("%d
",ans);
82             }
83         }
84     }
85     return 0;
86 }