当前位置 博文首页 > 文章内容

    LuoguP5576 [CmdOI2019]口头禅 后缀树+线段树+暴力

    作者: 栏目:未分类 时间:2020-08-10 9:00:20

    本站于2023年9月4日。收到“大连君*****咨询有限公司”通知
    说我们IIS7站长博客,有一篇博文用了他们的图片。
    要求我们给他们一张图片6000元。要不然法院告我们

    为避免不必要的麻烦,IIS7站长博客,全站内容图片下架、并积极应诉
    博文内容全部不再显示,请需要相关资讯的站长朋友到必应搜索。谢谢!

    另祝:版权碰瓷诈骗团伙,早日弃暗投明。

    相关新闻:借版权之名、行诈骗之实,周某因犯诈骗罪被判处有期徒刑十一年六个月

    叹!百花齐放的时代,渐行渐远!



    一个比较暴力的解法.  

    先对所有串建出广义后缀自动机提取出后缀树然后按照询问的右端点离线.   

    考虑插入第 $i$ 个串,那么会被 $i$ 及 $i$ 的祖先遍历到的点的表示范围会从 $[l,r] \rightarrow [l,r+1]$.   

    未被遍历到的点的表示范围出现了一个“断点”,则表示范围就是 $i$ 之后最近的串 $j$,$[j,j]$.    

    将串在自动机上匹配的复杂度是 $O(len)$ 的,暴力跳 $parent$ 树均摊 $O(\sqrt {len})$,总复杂度是 $O(len \sqrt{len} \log n)$.      

    暴力跳 $parent$ 树未必能保证复杂度正确,但好像很难卡.  

    代码: 

    #include <cstdio>
    #include <vector> 
    #include <cstring>
    #include <algorithm>   
    #define N 20004   
    #define M 400009 
    #define ll long long 
    #define pb push_back  
    #define lson now<<1 
    #define rson now<<1|1    
    #define setIO(s) freopen(s".in","r",stdin) 
    using namespace std;  
    int last,tot,n,Q;   
    char str[M]; 
    int an[N];  
    int ch[M<<1][2],mx[M<<1],pre[M<<1];  
    int L[N],R[N],arr[M],Min[M<<1],Max[M<<1],era[N<<2],tag[N<<2];                 
    struct que {
    	int l,r,id; 
    	que(int l=0,int r=0,int id=0):l(l),r(r),id(id){}   
    	bool operator<(const que b) const {
    		return r<b.r;   
    	}
    }; 
    vector<que>a[N];  
    void extend(int c) {
    	if(ch[last][c]) {
    		int p=last,q=ch[last][c];  
    		if(mx[q]==mx[p]+1) last=q;  
    		else {
    			int nq=++tot;  
    			mx[nq]=mx[p]+1;
    			memcpy(ch[nq],ch[q],sizeof(ch[q]));   
    			pre[nq]=pre[q],pre[q]=nq;  
    			for(;p&&ch[p][c]==q;p=pre[p]) ch[p][c]=nq;  
    			last=nq;  
    		}
    	}
    	else { 
    		int np=++tot,p=last;  
    		last=np,mx[np]=mx[p]+1;   
    		for(;p&&!ch[p][c];p=pre[p]) ch[p][c]=np;  
    		if(!p) pre[np]=1;  
    		else {
    			int q=ch[p][c]; 
    			if(mx[q]==mx[p]+1) pre[np]=q;     
    			else {
    				int nq=++tot;  
    				mx[nq]=mx[p]+1;  
    				memcpy(ch[nq],ch[q],sizeof(ch[q]));
    				pre[nq]=pre[q],pre[q]=pre[np]=nq; 
    				for(;p&&ch[p][c]==q;p=pre[p]) ch[p][c]=nq;  
    			}
    		}
    	}
    }       
    void mark(int now,int v) {
    	tag[now]=max(tag[now],v);      
    }
    void clea(int now) {
    	tag[now]=0,era[now]=1;   
    }
    void pushdown(int now) {
    	if(era[now]) {
    		clea(lson); 
    		clea(rson); 
    		era[now]=0;
    	} 
    	if(tag[now]) {
    		mark(lson,tag[now]); 
    		mark(rson,tag[now]); 
    		tag[now]=0; 
    	}
    }
    void modify(int l,int r,int now,int L,int R,int v) {
    	if(l>=L&&r<=R) {       
    		mark(now,v);   
    		return; 
    	} 
    	pushdown(now); 
    	int mid=(l+r)>>1; 
    	if(L<=mid) modify(l,mid,lson,L,R,v); 
    	if(R>mid)  modify(mid+1,r,rson,L,R,v);  
    }
    int query(int l,int r,int now,int p) {
    	if(l==r) return tag[now];  
    	pushdown(now); 
    	int mid=(l+r)>>1;  
    	if(p<=mid) return query(l,mid,lson,p); 
    	else return query(mid+1,r,rson,p);   
    }
    int trans,output[M];        
    void get(int x,int id) {
    	for(int i=x;i;i=pre[i]) {
    		if(Max[i]==id) break;  
    		if(Max[i]==id-1) {        
    			++Max[i];            
    		}
    		else {
    			Min[i]=id-1;    
    			Max[i]=id;        
    		}
    		modify(1,n,1,Min[i]+1,Max[i],mx[i]);      
    	}
    }
    void upd(int k,int id) {
    	trans=ch[trans][k];   
    	get(trans,id);   
    }
    int main() { 
    	// setIO("input"); 
    	scanf("%d%d",&n,&Q);   
    	last=tot=1; 
    	for(int i=1;i<=n;++i) {
    		scanf("%s",str+1); 
    		int len=strlen(str+1); 
    		last=1; 
    		for(int j=1;j<=len;++j) {
    			extend(str[j]-'0');   
    		}
    		L[i]=R[i-1]+1; 
    		R[i]=L[i]-1;   
    		for(int j=1;j<=len;++j) {
    			arr[++R[i]]=str[j]-'0';    
    		}     
    	}      
    	int x,y,z; 
    	for(int i=1;i<=Q;++i) {
    		scanf("%d%d",&x,&y);  
    		a[y].pb(que(x,y,i));    
    	}    
    	for(int i=1;i<=n;++i) {
    		trans=1;     
    		clea(1);    
    		for(int k=L[i];k<=R[i];++k) {
    			upd(arr[k],i);     
    		}      
    		for(int k=0;k<a[i].size();++k) {
    			que p=a[i][k];    
    			output[p.id]=query(1,n,1,p.l);       
    		}
    	}
    	for(int i=1;i<=Q;++i) {
    		printf("%d\n",output[i]);  
    	}
    	return 0;
    }