BZOJ4943 & 洛谷3823 & UOJ315：[NOI2017]蚯蚓排队——题解

题面太长自己看吧orz。

参考：洛谷题解。

用链表暴力维护每个蚯蚓，每次合并和分离只对k*k的元素有影响，哈希一下存起来query时候比较就好了。

没了。

（具体复杂度我不会证明，以及bzoj卡空间，正常的哈希表空间总觉得不能开如代码所示的这么小。）

（自然溢出hash真的块）

#include<cmath>

#include<stack>

#include<vector>

#include<cstdio>

#include<cctype>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int N=2e5+;

const int K=;

const int mod=;

const int p=;

const int B=;

inline int read(){

    int X=,w=;char ch=;

    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}

    while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();

    return w?-X:X;

}

struct node{

    int nxt,cnt;

    ll w;

}e[];

char s[];

int n,m,cnt,head[p+],t[],a[N];

int nxt[N],pre[N];

ull f[K*+],base[K+];

inline void add(ull w,int on){

    int u=w%p;

    for(int i=head[u];i;i=e[i].nxt){

    if(e[i].w==w){

        e[i].cnt+=on;return;

    }

    }

    e[++cnt].cnt=;e[cnt].w=w;e[cnt].nxt=head[u];head[u]=cnt;

}

inline int ask(ull w){

    int u=w%p;

    for(int i=head[u];i;i=e[i].nxt){

    if(e[i].w==w)return e[i].cnt;

    }

    return ;

}

void merge(int x,int y){

    int l=K+,r=K;

    memset(f,,sizeof(f));

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

    for(int j=y;j&&r<*K;j=nxt[j])f[++r]=a[j];

    for(int i=l;i<=r;i++)f[i]+=f[i-]*B;

    for(int i=l;i<=K;i++){

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

        add(f[j]-f[i-]*base[j-i+],);

    }

    }

    nxt[x]=y;pre[y]=x;

}

void split(int x,int y){

    int l=K+,r=K;

    memset(f,,sizeof(f));

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

    for(int j=y;j&&r<*K;j=nxt[j])f[++r]=a[j];

    for(int i=l;i<=r;i++)f[i]+=f[i-]*B;

    for(int i=l;i<=K;i++){

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

        add(f[j]-f[i-]*base[j-i+],-);

    }

    }

    nxt[x]=;pre[y]=;

}

int query(int k){

    ll ans=;ull val=;int len=strlen(s+);

    if(k==)

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

        ans=ans*t[s[i]-'']%mod;

    else{

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

        val=val*B+s[i]-'';

        if(i>k)val-=base[k]*(s[i-k]-'');

        if(i>=k)ans=ans*ask(val)%mod;

    }

    }

    return ans;

}

int main(){

    n=read(),m=read();

    base[]=;

    for(int i=;i<=K;i++)base[i]=base[i-]*B;

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

    a[i]=read();t[a[i]]++;

    }

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

    int op=read();

    if(op==){

        int x=read(),y=read();

        merge(x,y);

    }

    if(op==){

        int x=read();

        split(x,nxt[x]);

    }

    if(op==){

        scanf("%s",s+);

        int k=read();

        printf("%d\n",query(k));

    }

    }

    return ;

}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。　　　　　　　　　　　　　　+

+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/ +

+++++++++++++++++++++++++++++++++++++++++++