LOJ#2303. 「NOI2017」蚯蚓排队

$n \leq 200000$的$1 \leq a_i \leq 6$的蚯蚓，有三种操作：让一只队头蚯蚓接在一只队尾蚯蚓后面；让一队蚯蚓从某个蚯蚓后面断成两队；问：给个字符串，问他的。。算了你们直接看题吧

这什么沙雕题QAQ

所有询问的串只有$nk$种，把他们全丢进hash里面就好了。。注意双hash，一个用来当链表一个用来在链表里判重。

复杂度的话，只考虑合并是$nk$的（相当于把所有串算一次），而拆分是$ck^2$的，拆对合并的复杂度影响是跟拆本身复杂度一样的。

 //#include<iostream>

 #include<cstring>

 #include<cstdio>

 //#include<math.h>

 //#include<set>

 //#include<queue>

 //#include<bitset>

 //#include<vector>

 #include<algorithm>

 #include<stdlib.h>

 using namespace std;

 #define LL long long

 int qread()

 {

     char c; int s=,f=; while ((c=getchar())<'' || c>'') (c=='-') && (f=-);

     do s=s*+c-''; while ((c=getchar())>='' && c<=''); return s*f;

 }

 //Pay attention to '-' , LL and double of qread!!!!

 int n,m;

 #define maxn 200011

 #define maxh 1000007

 int a[maxn],bb[]; LL cc[];

 struct Hash

 {

     struct Edge{LL to; int v,next;}edge[maxn*]; int first[maxh],le;

     Hash() {le=;}

     void in(LL x,int h,int v)

     {

         for (int i=first[h];i;i=edge[i].next)

         {

             Edge &e=edge[i];

             if (e.to==x) {e.v+=v; return;}

         }

         Edge &e=edge[le]; e.to=x; e.v=; e.next=first[h]; first[h]=le++;

     }

     int find(LL x,int h)

     {

         for (int i=first[h];i;i=edge[i].next)

         {

             Edge &e=edge[i];

             if (e.to==x) return e.v;

         }

         return ;

     }

 }h;

 int Nxt[maxn],Pre[maxn];

 char s[maxn*]; int len;

 int main()

 {

     bb[]=; for (int i=;i<=;i++) bb[i]=bb[i-]*%maxh;

     cc[]=; for (int i=;i<=;i++) cc[i]=cc[i-]*;

     n=qread(); m=qread();

     for (int i=;i<=n;i++) {Pre[i]=Nxt[i]=; a[i]=qread(); h.in(a[i],a[i],);}

     int op; char c; int x,y;

     while (m--)

     {

         op=qread();

         if (op==)

         {

             x=qread(); y=qread();

             Nxt[x]=y; Pre[y]=x;

             LL B=,C=;

             for (int i=x,cnt=,w=;cnt && i;i=Pre[i],w++,cnt--)

             {

                 B=(B+1ll*a[i]*bb[w])%maxh;

                 C=C+1ll*a[i]*cc[w];

                 LL nb=B,nc=C;

                 for (int j=y,k=;j && k<=cnt;j=Nxt[j],k++)

                 {

                     nb=(nb*+a[j])%maxh;

                     nc=nc*+a[j];

                     h.in(nc,nb,);

                 }

             }

         }

         else if (op==)

         {

             x=qread(); y=Nxt[x];

             Nxt[x]=; Pre[y]=;

             LL B=,C=;

             for (int i=x,cnt=,w=;cnt && i;i=Pre[i],w++,cnt--)

             {

                 B=(B+1ll*a[i]*bb[w])%maxh;

                 C=C+1ll*a[i]*cc[w];

                 LL nb=B,nc=C;

                 for (int j=y,k=;j && k<=cnt;j=Nxt[j],k++)

                 {

                     nb=(nb*+a[j])%maxh;

                     nc=nc*+a[j];

                     h.in(nc,nb,-);

                 }

             }

         }

         else if (op==)

         {

             len=;

             while ((c=getchar())<'' || c>'');

             do s[++len]=c; while ((c=getchar())>='' && c<='');

             x=qread();

             LL B=,C=;

             for (int i=;i<x;i++) B=(B*+s[i]-'')%maxh,C=C*+s[i]-'';

             int ans=;

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

             {

                 B=(B*+s[i]-'')%maxh; C=C*+s[i]-'';

                 ans=1ll*ans*h.find(C,B)%;

                 B=(B-(s[i-x+]-'')*bb[x-])%maxh+maxh; B%=maxh;

                 C=C-(s[i-x+]-'')*cc[x-];

             }

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

         }

     }

     return ;

 }

巴特西

LOJ#2303. 「NOI2017」蚯蚓排队

最新文章

热门文章