模拟赛的时候纯暴力竟然骗了\(70\)分……

首先对于一堆\(g\)怎么计算概率应该很好想，用总的区间数减去不合法的区间数就行了，简而言之对\(g\)排个序，每一段长为\(d\)的连续序列的区间有\(\frac{d(d+1)}{2}\)，那么对于每一个\([g_{i-1}+1,g_{i}-1]\)的区间，把它能贡献的子区间减去就行了

其次它是询问，而且不强制在线，那么很容易想到莫队

然而单纯的莫队不可做，因为很有可能加一个字符串会导致好几个长度满足条件，这样一次转移就不是\(O(1)\)的了

这个问题也不难解决，我们把所有的字符串首尾相接看做一个字符串，那么每一次转移只会加上一个前缀，转移就可以做到\(O(1)\)了。对于\(g\)开一个\(set\)，加入数字的时候查一下前驱\(pre\)和后继\(next\)，把\([next+1,pre-1]\)的贡献删掉，同时把\([next+1,g-1]\)和\([g+1,pre-1]\)的贡献加上去。删除数字的时候同理

\(ok\)到了现在交上去发现还是\(T\)，因为\(set\)有一个\(\log\)，还是不够

我们发现\(set\)可以用链表优化，链表的删除是\(O(1)\)的，撤销也是\(O(1)\)的

但是莫队除了删除还有插入，这个时候就需要用到一个叫做回滚莫队的黑科技了

简单来说，我们在对询问排序的时候先按左端点所在块从小到大排序，再按右端点（不是所在块！）从大到小排序。对于左端点在同一块内的询问，右端点是递减的，那么每一次删除的复杂度是\(O(1)\)，暴力删除右端点的贡献是\(O(n)\)，这一部分的复杂度是\(O(n\sqrt{n})\)。对于左端点，每一次都从该块的最左端一直删除到左端点，每一次复杂度为\(O(\sqrt{n})\)，这一部分的府再度也是\(O(n\sqrt{n})\)

所以最后的复杂度是\(O(n\sqrt{n})\)

//minamoto#include
    
     #define R register#define inf 0x3f3f3f3f#define ll long long#define fp(i,a,b) for(R int i=a,I=b+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)template
      
       inline bool cmax(T&a,const T&b){return a
       
        
         inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}using namespace std;//char buf[1<<21],*p1=buf,*p2=buf;//inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}#define getc() getchar()int read(){    R int res,f=1;R char ch;    while((ch=getc())>'9'||ch<'0'){(ch=='-')&&(f=-1);if(ch==EOF)return EOF;}    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}int read(char *s){    R int len=0;R char ch;while((ch=getc())>'z'||ch<'a');    while(s[++len]=ch,((ch=getc())>='a'&&ch<='z'));return s[len+1]=0,len;}char sr[1<<21],z[20];int K=-1,Z=0;inline void Ot(){fwrite(sr,1,K+1,stdout),K=-1;}void print(R ll x){    if(K>1<<20)Ot();if(x<0)sr[++K]='-',x=-x;    while(z[++Z]=x%10+48,x/=10);    while(sr[++K]=z[Z],--Z);sr[++K]='\n';}const int N=3e5+5;int a[N],len[N],ch[N][26],pos[N],v[N],dep[N];int bl[N],g[N],ls[N],rs[N],st[N],cnt[N];struct node{    int l,r,id;    inline bool operator <(const node &b)const{return bl[l]==bl[b.l]?r>b.r:bl[l]
         
          =C:0;}inline ll calc(R int x){return 1ll*x*(x+1)>>1;}void ins(char *s,int vva,int len){ int p=0; fp(i,1,len){ int c=s[i]-'a'; if(!ch[p][c])ch[p][c]=++num,dep[num]=dep[p]+1; p=ch[p][c],pos[++tot]=p,v[tot]=vva; }}void del(R int i){ int x=pos[i]; if(ck(F[x],dep[x])&&!ck(F[x]-v[i],dep[x])&&!--cnt[g[dep[x]]]){ int k=g[dep[x]],l=ls[k],r=rs[k]; ls[r]=l,rs[l]=r,res-=calc(r-k-1),res-=calc(k-l-1),res+=calc(r-l-1); }F[x]-=v[i];}void add(R int i){ int x=pos[i]; if(!ck(F[x],dep[x])&&ck(F[x]+v[i],dep[x])&&!cnt[g[dep[x]]]++){ int k=g[dep[x]],l=ls[k],r=rs[k]; ls[r]=rs[l]=k,res-=calc(r-l-1),res+=calc(r-k-1),res+=calc(k-l-1); }F[x]+=v[i];}int main(){// freopen("testdata.in","r",stdin);// freopen("string.in","r",stdin);// freopen("string.out","w",stdout); n=read(),A=read(),B=read(),C=read();fp(i,1,n)a[i]=read(); fp(i,1,n)cmax(mx,len[i]=read(s)),ins(s,a[i],len[i]),len[i]+=len[i-1]; S=sqrt(tot);fp(i,1,tot)bl[i]=(i-1)/S+1; fp(i,1,mx)g[i]=read(); m=read(),qwq=calc(mx); fp(i,1,m){ l=read(),r=read(); q[i].l=len[l-1]+1,q[i].r=len[r],q[i].id=i; } sort(q+1,q+1+m); for(R int i=1,x=pos[i];i<=tot;F[x]+=v[i],x=pos[++i]) if(!ck(F[x],dep[x])&&ck(F[x]+v[i],dep[x])&&!cnt[g[dep[x]]]++) st[++top]=g[dep[x]]; st[++top]=0,st[++top]=mx+1,sort(st+1,st+1+top); fp(i,1,top)ls[st[i]]=st[i-1],rs[st[i]]=st[i+1]; fp(i,2,top)res+=calc(st[i]-st[i-1]-1); for(R int i=1,j=S,t=1,l=i,r=tot;t<=m&&i<=tot;i+=S,j+=S){ while(t<=m&&q[t].l>=i&&q[t].l<=j){ while(r>q[t].r)del(r--);while(l
          
           i)add(--l);++t; }while(r
           
            <=j)del(l++); }fp(i,1,m){ d=__gcd(qwq,ans[i]); print(ans[i]/d),sr[K]='/',print(qwq/d); } return Ot(),0;}