NOI2017蚯蚓排队

原题链接

发现 k<=50 ，在插入和删除时最多会影响不超过 k² 个串，用链表实现插入和删除,然后只需用哈希表维护每个长度不超过k的串的出现次数，哈希的话可以先用比较大的范围的值处理冲突，再映射到1e8的桶里统计。

考虑复杂度。

首先在删除时由于保证了 c<=1000 所以这部分复杂度是O(ck²)的。

插入时，如果插入操作很慢只有可能是连接两个长度不小于k的串，而长度不小于k的串最多有n/k个，所以这部分复杂度是O(nk)的

所以总复杂度是O(nk+ck²+|s|)。

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<vector>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

using namespace std;

inline void read(int &re)

{

    char ch=getchar();int g=1;

    while(ch<'0'||ch>'9') {if(ch=='-')g=-1;ch=getchar();}

    re=0;

    while(ch<='9'&&ch>='0') re=(re<<1)+(re<<3)+(ch^48),ch=getchar();

    re*=g;

}

typedef long long ll;

typedef double db;

typedef unsigned long long ul;

const ul bas=7u;

const ll mod=998244353;

const ul mod2=99999971u;

const int N=200050;

int head[N],tail[N],cnt=0,nex[20050000],fir[100000000];

int num[20050000];

ul hax[20050000];

char leng[N];

inline ul qpow(ul a,int n)

{

    ul ans=1;

    for(;n;n>>=1,a=a*a) if(n&1) ans=ans*a;

    return ans;

}

inline void insert(ul x)

{

    ul m=x%mod2;

    int u=fir[m];

    if(!u)

    {

        fir[m]=++cnt; hax[cnt]=x;

        num[cnt]++; return ;

    }

    if(hax[u]==x) {num[u]++;return ;}

    while(nex[u])

    {

        u=nex[u];

        if(hax[u]==x) {num[u]++; return ;}

    }

    cnt++;

    nex[u]=cnt;

    hax[cnt]=x; num[cnt]++;

}

inline void del(ul x)

{

    ul m=x%mod2;

    int u=fir[m];

    while(u)

    {

        if(hax[u]==x) {num[u]--;return ;}

        u=nex[u];

    }

}

inline int query(ul x)

{

    ul m=x%mod2;

    int u=fir[m];

    while(u)

    {

        if(hax[u]==x) return num[u];

        u=nex[u];

    }

    return 0;

}

char a[10000050];

int n,m;

int main()

{

#ifndef ONLINE_JUDGE

    freopen("queue.in","r",stdin);freopen("queue.out","w",stdout);

#endif

    int i,j,opt,x,y,k;

    read(n);read(m);

    for(i=1;i<=n;++i)

    {

        read(opt),leng[i]=opt+48;

        ul has=leng[i]-48u;

        insert(has);

    }

    while(m--)

    {

        read(opt);

        if(opt==1)

        {

            read(x);read(y);//--x y--

            tail[x]=y;head[y]=x;

            int u=x,v;

            for(i=1;i<=50-2&&head[u];++i) u=head[u];

            for(;u!=y;u=tail[u])

            {

                bool can=0;

                v=u;

                ul has=0;

                has=leng[u]-48u;

                for(i=1;i<50;++i)

                {

                    v=tail[v];

                    if(!v) break;

                    has=has*bas+leng[v]-48u;

                    if(v==y||can)

                    {

                        can=1;

                        insert(has);

                    }

                }

            }

        }

        else if(opt==2) // --x || y--

        {

            read(x);

            int u=x,v;

            y=tail[x];

            for(i=1;i<=50-2&&head[u];++i) u=head[u];

            for(;u!=y;u=tail[u])

            {

                bool can=0;

                v=u;

                ul has=leng[u]-48u;

                for(i=1;i<50;++i)

                {

                    v=tail[v];

                    if(!v) break;

                    has=has*bas+leng[v]-48u;

                    if(v==y||can)

                    {

                        can=1;

                        del(has);

                    }

                }

            }

            head[y]=0;tail[x]=0;

        }

        else

        {

            ll ans=1;

            scanf("%s",a);read(k);

            int len=strlen(a);

            ul has=0,powbas=qpow(bas,k-1);

            for(i=0;i<k;++i) has=has*bas+a[i]-48u;

            ans=ans*(ll)query(has);

            for(i=1;i<=len-k;++i)

            {

                has=(has-(a[i-1]-48u)*powbas)*bas+a[i+k-1]-48u;

                ans=ans*(ll)query(has)%mod;

            }

            printf("%lld\n",ans);

        }

    }

    return 0;

}

NOI2017蚯蚓排队的相关教程结束。