Cptraser/ 二月 28, 2019/ 2019.2/ 0 comments

题目传送门

先将所有串用特殊字符连接起来,跑SA
记录每个字符属于哪个人。
对于每个询问,考虑字典序的性质,询问必然在SA数组上构成一个区间。
莫队处理即可。

#include <cmath>
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;

char tc(){static char tr[10000],*A=tr,*B=tr;return A==B&&(B=(A=tr)+fread(tr,1,10000,stdin),A==B)?EOF:*A++;}
void read(int &x){char c;for(;!isdigit(c=tc()););for(x=c-48;isdigit(c=tc());x=(x<<1)+(x<<3)+c-48);}

const int Maxn=1e5+5;

int N,M,Cnt,len,x,Sz,A[Maxn<<2],Be[Maxn<<2],Sio,Ans[Maxn<<1],pct,t[Maxn<<2],tot,gtp[Maxn<<2];
int SA[Maxn<<2],rak[Maxn<<2],tp[Maxn<<2],tax[Maxn<<2],dur[Maxn<<2],p,MaxS=1e4;

void Radix_Sort(void){
    for(int i=0;i<=Sz;i++)tax[i]=0;
    for(int i=1;i<=Cnt;i++)++tax[rak[i]];
    for(int i=1;i<=Sz;i++)tax[i]+=tax[i-1];
    for(int i=Cnt;i;i--)SA[tax[rak[tp[i]]]--]=tp[i];
}
void SuffixSort(void){
    Sz=MaxS,Radix_Sort();
    for(int w=1,p=0;p<Cnt;Sz=p,w<<=1){
        p=0;
        for(int i=1;i<=w;i++)tp[++p]=Cnt-w+i;
        for(int i=1;i<=Cnt;i++)if(SA[i]>w)tp[++p]=SA[i]-w;
        Radix_Sort(),swap(tp,rak),rak[SA[1]]=p=1;
        for(int i=2;i<=Cnt;i++)rak[SA[i]]=(tp[SA[i-1]]==tp[SA[i]]&&tp[SA[i-1]+w]==tp[SA[i]+w])?p:++p;
    }
}

struct Query{
    int x,y,id;
    bool operator<(const Query&O)const{
        return Be[x]==Be[O.x]?(Be[x]&1?y<O.y:y>O.y):x<O.x;
    }
}Qr[Maxn<<1];

void insert(int x,int gt){
    if(dur[x]>N)return ;
    if(++t[dur[x]]==1)++tot,gtp[dur[x]]+=pct-gt+1;
}
void del(int x,int gt){
    if(dur[x]>N)return ;
    if(!--t[dur[x]])--tot,gtp[dur[x]]-=pct-gt+1;
}
int main()
{
    read(N),read(M);
    for(int i=1;i<=N;i++)for(int k=0;k<2;k++){
        read(len);for(int j=1;j<=len;j++)read(x),rak[++Cnt]=x,A[Cnt]=x,tp[Cnt]=Cnt,dur[Cnt]=i;
        rak[++Cnt]=++MaxS,A[Cnt]=MaxS,tp[Cnt]=Cnt,dur[Cnt]=N+1;
    }Sio=sqrt(Cnt),SuffixSort();
    for(int i=1;i<=Cnt;i++)Be[i]=(i-1)/Sio+1;
    for(int Q=1;Q<=M;Q++){
        read(len);int L=1,R=Cnt;for(int i=1;i<=len;i++){
            read(x);
            if(L>R)continue;
            int l=L,r=R,Mid,res;
            for(;l<=r;){Mid=l+r>>1;if(A[SA[Mid]+i-1]< x)l=Mid+1;else r=Mid-1;}res=l,r=R,l=L;
            for(;l<=r;){Mid=l+r>>1;if(A[SA[Mid]+i-1]<=x)l=Mid+1;else r=Mid-1;}R=r,L=res;
        }
        if(L<=R)Qr[++pct]=(Query){L,R,Q};
    }sort(Qr+1,Qr+pct+1);
    for(int L=1,R=0,i=1;i<=pct;i++){
        while(R<Qr[i].y)insert(SA[++R],i);
        while(L>Qr[i].x)insert(SA[--L],i);
        while(R>Qr[i].y)del(SA[R--],i);
        while(L<Qr[i].x)del(SA[L++],i);
        Ans[Qr[i].id]=tot;
    }
    for(int i=1;i<=M;i++)printf("%d\n",Ans[i]);
    for(int i=1;i<=N;i++)printf("%d ",gtp[i]);
}
Share this Post

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
*
*