首页 > 代码库 > BZOJ3946 : 无聊的游戏
BZOJ3946 : 无聊的游戏
首先把所有串拼起来，后插入的串在前面，得到一个大串。
那么任意时刻，每个串是由这个大串的若干个不相交的子串从左到右拼接而成。
用线段树维护每个串，每个节点维护一个标记，表示区间内的串要加上什么前缀。
用可持久化线段树维护这些串和标记，那么合并就是线段树的合并，因为取值区间互不相交，所以每次合并的复杂度为$O(\log L)$。
这样就可以在$O(m\log n\log L)$的时间内支持区间加操作。
然后考虑如何计算区间LCP，设$height_i=LCP(s_i,s_{i+1})$，那么询问$[L,R]$就是询问$\min(height_L,height_{L+1},...,height_{R-1})$。
用线段树维护$height$，每当区间加的时候，对$height$的修改就是区间加上一个定值，然后两端点暴力重新计算LCP。
计算两个串的LCP可以考虑维护Hash值，然后二分答案，单次查询的复杂度为$O(\log^2L)$。
时间复杂度$O(m(\log n+\log L)\log L)$。
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;typedef unsigned int U;const int N=50010,M=600010,MAXN=131100;int n,m,i,j,x,len,cur,st[N],en[N],q[N][3],stq[N],enq[N];U po[M];char op[9],s[M],pool[M],str[M];int pre[MAXN],T[N],h[MAXN],tag[MAXN];namespace DS{const int MAXM=15000000;int tot,l[MAXM],r[MAXM],v[MAXM];U f[MAXM];inline void up(int x){ v[x]=v[l[x]]+v[r[x]]; f[x]=f[l[x]]*po[v[r[x]]]+f[r[x]];}int build(int a,int b,int c,int d){ int x=++tot; if(a==b){ v[x]=1; f[x]=str[a]; return x; } int mid=(a+b)>>1; if(c<=mid)l[x]=build(a,mid,c,d); if(d>mid)r[x]=build(mid+1,b,c,d); return up(x),x;}int merge(int x,int y,int a,int b){ if(!x||!y)return x+y; int z=++tot,mid=(a+b)>>1; l[z]=merge(l[x],l[y],a,mid); r[z]=merge(r[x],r[y],mid+1,b); return up(z),z;}inline U hash(int x,int k){ int a=1,b=cur,mid,t;U h=0; while(a<b){ mid=(a+b)>>1,t=v[l[x]]; if(k<=t)b=mid,x=l[x];else h=h*po[t]+f[l[x]],k-=t,a=mid+1,x=r[x]; } return h*po[v[x]]+f[x];}}inline void ins(int x,int p){pre[x]=DS::merge(pre[x],p,1,cur);}inline void down(int x){if(pre[x])ins(x<<1,pre[x]),ins(x<<1|1,pre[x]),pre[x]=0;}void push(int x,int a,int b,int c,int d,int p){ if(c<=a&&b<=d){ins(x,p);return;} down(x); int mid=(a+b)>>1; if(c<=mid)push(x<<1,a,mid,c,d,p); if(d>mid)push(x<<1|1,mid+1,b,c,d,p);}void root(int x,int a,int b,int c){ if(a==b){ T[a]=DS::merge(T[a],pre[x],1,cur); pre[x]=0; return; } down(x); int mid=(a+b)>>1; if(c<=mid)root(x<<1,a,mid,c);else root(x<<1|1,mid+1,b,c);}inline int lcp(int x,int y){ root(1,1,n,x),root(1,1,n,y); x=T[x],y=T[y]; int l=1,r=min(DS::v[x],DS::v[y]),mid,t=0; while(l<=r){ mid=(l+r)>>1; if(DS::hash(x,mid)==DS::hash(y,mid))l=(t=mid)+1;else r=mid-1; } return t;}inline void tag1(int x,int p){h[x]+=p;tag[x]+=p;}inline void pb(int x){if(tag[x])tag1(x<<1,tag[x]),tag1(x<<1|1,tag[x]),tag[x]=0;}inline void up(int x){h[x]=min(h[x<<1],h[x<<1|1]);}void build(int x,int a,int b){ if(a==b){h[x]=lcp(a,a+1);return;} int mid=(a+b)>>1; build(x<<1,a,mid),build(x<<1|1,mid+1,b); up(x);}void cal(int x,int a,int b,int c){ if(a==b){h[x]=lcp(a,a+1);return;} pb(x); int mid=(a+b)>>1; if(c<=mid)cal(x<<1,a,mid,c);else cal(x<<1|1,mid+1,b,c); up(x);}void change(int x,int a,int b,int c,int d,int p){ if(c<=a&&b<=d){tag1(x,p);return;} pb(x); int mid=(a+b)>>1; if(c<=mid)change(x<<1,a,mid,c,d,p); if(d>mid)change(x<<1|1,mid+1,b,c,d,p); up(x);}int ask(int x,int a,int b,int c,int d){ if(c<=a&&b<=d)return h[x]; pb(x); int mid=(a+b)>>1,t=M; if(c<=mid)t=ask(x<<1,a,mid,c,d); if(d>mid)t=min(t,ask(x<<1|1,mid+1,b,c,d)); return t;}inline void makepush(int l,int r,int A,int B){ push(1,1,n,l,r,DS::build(1,cur,A,B)); if(l<r)change(1,1,n-1,l,r-1,B-A+1); if(l>1)cal(1,1,n-1,l-1); if(r<n)cal(1,1,n-1,r);}inline int query(int l,int r){ if(l==r)return lcp(l,l); return ask(1,1,n-1,l,r-1);}int main(){ scanf("%d%d",&n,&m); for(i=1;i<=n;i++){ scanf("%s",s); len=strlen(s); st[i]=cur+1; for(j=0;j<len;j++)pool[++cur]=s[j]; en[i]=cur; } for(i=1;i<=m;i++){ scanf("%s%d%d",op,&q[i][1],&q[i][2]); if(op[0]==‘Q‘)q[i][0]=1; else{ scanf("%s",s); len=strlen(s); stq[i]=cur+1; for(j=0;j<len;j++)pool[++cur]=s[j]; enq[i]=cur; } } for(cur=0,i=m;i;i--)if(!q[i][0]){ x=cur+1; for(j=stq[i];j<=enq[i];j++)str[++cur]=pool[j]; stq[i]=x,enq[i]=cur; } for(i=1;i<=n;i++){ x=cur+1; for(j=st[i];j<=en[i];j++)str[++cur]=pool[j]; st[i]=x,en[i]=cur; } for(po[0]=i=1;i<=cur;i++)po[i]=po[i-1]*233; for(i=1;i<=n;i++)T[i]=DS::build(1,cur,st[i],en[i]); build(1,1,n-1); for(i=1;i<=m;i++)if(q[i][0])printf("%d\n",query(q[i][1],q[i][2])); else makepush(q[i][1],q[i][2],stq[i],enq[i]); return 0;}
BZOJ3946 : 无聊的游戏
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。