[bzoj4943]蚯蚓排队

询问相当于要求长度为k的公共子串个数，很容易联想到hash，由于询问是对全局的，因此对全局开一个hash的桶
对于合并/删除操作，将中间新产生/需要删除的字符串暴力修改即可，单次复杂度最坏为$o(k^{2})$
这样看上去复杂度是$o(nk^{2})$的，但考虑最终的字符串总数$o(nk)$，删除操作最多删掉$o(ck^{2})$，而$\sum 合并复杂度-\sum 删除复杂度=o(nk)$，因此合并复杂度均摊仅为$o(nk)$
但这样的字符串个数挺多的，那么模数就要比较大，而且还不能用map（会TLE），可以再对结果取模然后挂链即可

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 200005

 4 #define K 50

 5 #define P 4999999

 6 #define mod 998244353

 7 #define ll unsigned long long

 8 struct ji{

 9     int nex,tot;

10     ll val;

11 }edge[N*100];

12 int E,n,m,p,x,y,f[K<<2],a[N],pre[N],nex[N],head[P+100];

13 char s[N*50];

14 void add(ll x,int y){

15     int z=x%P;

16     for(int i=head[z];i!=-1;i=edge[i].nex)

17         if (edge[i].val==x){

18             edge[i].tot+=y;

19             return;

20         }

21     edge[E].nex=head[z];

22     edge[E].val=x;

23     edge[E].tot=y;

24     head[z]=E++;

25 }

26 int query(ll x){

27     int y=x%P;

28     for(int i=head[y];i!=-1;i=edge[i].nex)

29         if (edge[i].val==x)return edge[i].tot;

30     return 0;

31 }

32 void update(int x,int y,int p){

33     int l=K,r=K+1;

34     for(int i=x;(i)&&(l);i=pre[i],l--)f[l]=a[i];

35     for(int i=y;(i)&&(r<=K*2);i=nex[i],r++)f[r]=a[i];

36     l++;

37     r--;

38     for(int i=K;i>=l;i--){

39         ll hash=0;

40         for(int j=i;j<=K;j++)hash=hash*11+f[j];

41         for(int j=K+1;j<=min(r,i+K-1);j++){

42             hash=hash*11+f[j];

43             add(hash,p);

44         }

45     }

46     if (p<0)nex[x]=pre[y]=0;

47     else{

48         nex[x]=y;

49         pre[y]=x;

50     }

51 }

52 int main(){

53     scanf("%d%d",&n,&m);

54     memset(head,-1,sizeof(head));

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

56         scanf("%d",&a[i]);

57         add(a[i],1);

58     }

59     for(int i=1;i<=m;i++){

60         scanf("%d",&p);

61         if (p==1){

62             scanf("%d%d",&x,&y);

63             update(x,y,1);

64         }

65         if (p==2){

66             scanf("%d",&x);

67             y=nex[x];

68             update(x,y,-1);

69         }

70         if (p==3){

71             scanf("%s%d",s,&x);

72             y=strlen(s);

73             ll mi=1,hash=0;

74             for(int j=0;j<x;j++){

75                 mi=mi*11;

76                 hash=hash*11+s[j]-'0';

77             }

78             int ans=query(hash);

79             for(int j=x;j<y;j++){

80                 hash=hash*11+s[j]-'0'-(s[j-x]-'0')*mi;

81                 ans=1LL*ans*query(hash)%mod;

82             }

83             printf("%d\n",ans);

84         }

85     }

86 }

巴特西

[bzoj4943]蚯蚓排队

最新文章

热门文章