「雅礼集训 2017 Day7」事情的相似度—

本文主要是介绍「雅礼集训 2017 Day7」事情的相似度——treap启发式合并，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

「雅礼集训 2017 Day7」事情的相似度

题解

这题的题解是我拖得最久的一篇，我半年前就第一次做这题，到现在才来填坑。

题目问的是区间（l，r）内任两个不同前缀的最长公共后缀，也就是对于所有 $a\geq l,b\leq r,a<b$ 的a、b，求 $max(lcs(:a,:b))$ ， $lcs(:a,:b)$ 表示前缀a和前缀b的最长公共后缀。

然后考虑把01串插入到后缀自动机里，记录一下每个前缀对应的parent树节点，那么两个前缀的最长公共后缀就是parent树上的最近公共祖先LCA的len值，或者所有公共祖先的len值取max。

所以对parent树跑一次dfs，那么一个节点的len值对子树中所有前缀两两之间都有贡献。考虑如何计算贡献：

设节点u有儿子_a、_b，_a的子树中所有前缀排序后构成数组a，b的子树中所有前缀排序后构成数组b，设u的len值为s，

那么对于每一个 $b_i$ 只要贪心地找到一个 $a_j$ 满足 $b_{i-1}<a_j<b_i,a_{j+1}>b_i$ ，就可以对所有 $l\leq a_j,r\geq b_i$ 的询问产生s的贡献，因为对于数组b的前缀之间已经算入了一个更大的贡献（即_b的len值），数组a同理，所以对 $l\leq b_{i-1}$ 的询问算s的贡献肯定不优了。而由于是对所有 $l\leq a_j,r\geq b_i$ 的询问产生的贡献，所以， $a_j$ 以前的贡献不用重复算，也就是只需要找到第一个小于 $b_i$ 的 $a_j$ 即可。

我们用非旋treap（或其它平衡树也行）维护每个子树内的所有前缀，那么每找一次并记录贡献的时间是 $O(\log|a|)$ 的，合并a、b数组的复杂度为 $O(|b|\log(|a|+|b|))$ ，直接做肯定会被卡到 $O(n^2\log n)$ ，考虑启发式合并，每次选长度较小的数组为b，那么期望情况下（parent树的形态接近堆）复杂度是 $O(n\log^2n)$ ，而长链情况下复杂度是 $O(n\log n)$ ，还小一些，所以总复杂度介于 $O(n\log n)$ ~ $O(n\log^2n)$ 之间。

最后只要把询问离线排序然后用个线段树处理一下贡献和询问就好了，复杂度也是 $O(n\log n)$ ~ $O(n\log^2n)$ 。

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<ctime>
#define ll long long
#define MAXN 100005
#define INF 0x3f3f3f3f
using namespace std;
inline ll read(){ll x=0;bool f=1;char s=getchar();while((s<'0'||s>'9')&&s>0){if(s=='-')f^=1;s=getchar();}while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+s-'0',s=getchar();return f?x:-x;
}
int n,m,ans[MAXN],tr[MAXN*3],p;    //zkw线段树处理贡献
inline void add(int l,int r,int z){for(l=p+l-1,r=p+r+1;l^1^r;l>>=1,r>>=1){if(~l&1)tr[l^1]=max(tr[l^1],z);if(r&1)tr[r^1]=max(tr[r^1],z);}
}
inline int sch(int x){int res=0;for(x=p+x;x>0;x>>=1)res=max(res,tr[x]);return res;
}
struct node{int x,y;node(){}node(int X,int Y){x=X,y=Y;}
};
vector<node>dat[MAXN],ask[MAXN];
struct itn{    //非旋treapint ls,rs,val,siz,l,r;itn(){}itn(int a){l=r=a,val=rand()%MAXN,siz=1,ls=rs=0;}
}t[MAXN];
inline void update(int x){t[x].siz=t[t[x].ls].siz+t[t[x].rs].siz+1;t[x].l=!t[t[x].ls].l?x:t[t[x].ls].l,t[x].r=max(t[t[x].rs].r,x);
}
inline node split(int x,int k){if(!x||!k)return node(0,x);node res;if(x<=k)res=split(t[x].rs,k),t[x].rs=res.x,update(x),res.x=x;else res=split(t[x].ls,k),t[x].ls=res.y,update(x),res.y=x;return res;
}
inline int mergg(int x,int y){if(!x||!y)return x|y;int res;if(t[x].val<t[y].val)res=x,t[x].rs=mergg(t[x].rs,y),update(x);else res=y,t[y].ls=mergg(x,t[y].ls),update(y);return res;
}
struct SAM{    //后缀自动机int ch[2],fa,len;SAM(){ch[1]=ch[2]=fa=len=0;}
}sam[MAXN<<1];
int las=1,tot=1,id[MAXN<<1],root[MAXN<<1];
inline void samadd(bool c,int x){int p=las,np=las=++tot;sam[np].len=sam[p].len+1;for(;p&&!sam[p].ch[c];p=sam[p].fa)sam[p].ch[c]=np;if(!p)sam[np].fa=1;else{int q=sam[p].ch[c],nq;if(sam[q].len==sam[p].len+1)sam[np].fa=q;else{nq=++tot,sam[nq]=sam[q],sam[nq].len=sam[p].len+1,sam[q].fa=sam[np].fa=nq;for(;p&&sam[p].ch[c]==q;p=sam[p].fa)sam[p].ch[c]=nq;}}id[np]=x;
}
vector<int>G[MAXN<<1];
inline void dfs(int x){if(id[x]>0)root[x]=id[x],t[id[x]]=itn(id[x]);for(int i=0;i<G[x].size();i++){int v=G[x][i];dfs(v);int a=root[x],b=root[v];if(t[a].siz>t[b].siz)swap(a,b);node c,d;while(a){c=split(b,t[a].l),dat[t[a].l].push_back(node(t[c.x].r,sam[x].len));if(c.y)dat[t[c.y].l].push_back(node(t[a].l,sam[x].len));d=split(a,t[a].l),b=mergg(mergg(c.x,d.x),c.y),a=d.y;}root[x]=b;}
}
inline bool getb(){char s=getchar();while(s!='0'&&s!='1'&&s>0)s=getchar();return s-'0';
}
signed main()
{srand(time(0));n=read(),m=read();for(int i=1;i<=n;i++)samadd(getb(),i);for(int i=2;i<=tot;i++)G[sam[i].fa].push_back(i);dfs(1);for(p=1;p<n+2;p<<=1);for(int i=1;i<=m;i++){int l=read(),r=read();ask[r].push_back(node(l,i));}for(int i=1;i<=n;i++){    //离线处理贡献和询问for(int j=0;j<dat[i].size();j++)add(1,dat[i][j].x,dat[i][j].y);for(int j=0;j<ask[i].size();j++)ans[ask[i][j].y]=sch(ask[i][j].x);}for(int i=1;i<=m;i++)printf("%d\n",ans[i]);return 0;
}

这篇关于「雅礼集训 2017 Day7」事情的相似度——treap启发式合并的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！