LOJ6041. 「雅礼集训 2017 Day7」事情的相似度 [后缀树，LCT]

LOJ

思路

建出反串的后缀树，发现询问就是问一个区间的点的\(lca\)的深度最大值。

一种做法是dfs的时候从下往上合并\(endpos\)集合，发现插入一个点的时候只需要把与前驱后继的贡献算进去就可以了。

另一种做法是从小到大枚举结尾，把到根的一条链全都打上自己的标记，并且如果原来有标记就更新答案，发现可以用LCT维护。

本质其实差不多。

代码

我又傻傻地把树状数组能做的事搞成了线段树……

#include<bits/stdc++.h>

clock_t t=clock();

namespace my_std{

    using namespace std;

    #define pii pair<int,int>

    #define fir first

    #define sec second

    #define MP make_pair

    #define rep(i,x,y) for (int i=(x);i<=(y);i++)

    #define drep(i,x,y) for (int i=(x);i>=(y);i--)

    #define go(x) for (int i=head[x];i;i=edge[i].nxt)

    #define templ template<typename T>

    #define sz 202020

    typedef long long ll;

    typedef double db;

    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

    templ inline T rnd(T l,T r) {return uniform_int_distribution<T>(l,r)(rng);}

    templ inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}

    templ inline bool chkmin(T &x,T y){return x>y?x=y,1:0;}

    templ inline void read(T& t)

    {

        t=0;char f=0,ch=getchar();double d=0.1;

        while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();

        while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();

        if(ch=='.'){ch=getchar();while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();}

        t=(f?-t:t);

    }

    template<typename T,typename... Args>inline void read(T& t,Args&... args){read(t); read(args...);}

    char __sr[1<<21],__z[20];int __C=-1,__zz=0;

    inline void Ot(){fwrite(__sr,1,__C+1,stdout),__C=-1;}

    inline void print(register int x)

    {

        if(__C>1<<20)Ot();if(x<0)__sr[++__C]='-',x=-x;

        while(__z[++__zz]=x%10+48,x/=10);

        while(__sr[++__C]=__z[__zz],--__zz);__sr[++__C]='\n';

    }

    void file()

    {

        #ifdef NTFOrz

        freopen("a.in","r",stdin);

        #endif

    }

    inline void chktime()

    {

        #ifndef ONLINE_JUDGE

        cout<<(clock()-t)/1000.0<<'\n';

        #endif

    }

    #ifdef mod

    ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x%mod) if (y&1) ret=ret*x%mod;return ret;}

    ll inv(ll x){return ksm(x,mod-2);}

    #else

    ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x) if (y&1) ret=ret*x;return ret;}

    #endif

//	inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;}

}

using namespace my_std;

int n,m;

char s[sz];

namespace SegmentTree

{

	int mx[sz<<2];

	#define ls k<<1

	#define rs k<<1|1

	#define lson ls,l,mid

	#define rson rs,mid+1,r

	void modify(int k,int l,int r,int x,int y)

	{

		if (!x) return;

		chkmax(mx[k],y);

		if (l==r) return;

		int mid=(l+r)>>1;

		if (x<=mid) modify(lson,x,y);

		else modify(rson,x,y);

	}

	int query(int k,int l,int r,int x,int y)

	{

		if (x<=l&&r<=y) return mx[k];

		int mid=(l+r)>>1,ret=0;

		if (x<=mid) chkmax(ret,query(lson,x,y));

		if (y>mid) chkmax(ret,query(rson,x,y));

		return ret;

	}

	#undef ls

	#undef rs

	#undef lson

	#undef rson

}

using namespace SegmentTree;

namespace LCT

{

	int rt[sz],val[sz],fa[sz],ch[sz][2];

	int dep[sz];

	#define ls ch[x][0]

	#define rs ch[x][1]

	void pushup(int x){rt[x]=(ls?rt[ls]:x);}

	int get(int x){return ch[fa[x]][1]==x;}

	int nroot(int x){return ch[fa[x]][0]==x||ch[fa[x]][1]==x;}

	void rotate(int x)

	{

		int y=fa[x],z=fa[y],k=get(x),w=ch[x][!k];

		if (nroot(y)) ch[z][get(y)]=x;ch[x][!k]=y;ch[y][k]=w;

		if (w) fa[w]=y;fa[y]=x;fa[x]=z;

		pushup(y),pushup(x);

	}

	void splay(int x){for (int y;y=fa[x],nroot(x);rotate(x)) if (nroot(y)) rotate(get(x)==get(y)?y:x);}

	void access(int x,int pos)

	{

		int _x=x;

		for (int y=0;x;x=fa[y=x])

		{

			splay(x);

			if (rs) val[rt[rs]]=val[rt[x]];

			rs=y,modify(1,1,n,val[rt[x]],dep[x]);

		}

		splay(_x),val[rt[_x]]=pos;

	}

	#undef ls

	#undef rs

}

namespace SAM

{

	struct hh{int link,len,ch[2];}a[sz];

	int cnt=1,lst=1;

	int add(int c)

	{

		int cur=++cnt,p=lst;lst=cur;

		a[cur].len=a[p].len+1;

		#define v a[p].ch[c]

		while (p&&!v) v=cur,p=a[p].link;

		if (!p) return a[cur].link=1,cur;

		int q=v;

		if (a[q].len==a[p].len+1) return a[cur].link=q,cur;

		int t=++cnt;a[t]=a[q];a[t].len=a[p].len+1;a[q].link=a[cur].link=t;

		while (p&&v==q) v=t,p=a[p].link;

		#undef v

		return cur;

	}

	void work(){rep(i,1,cnt) LCT::fa[i]=a[i].link,LCT::dep[i]=a[i].len,LCT::rt[i]=i;}

}

int pos[sz];

struct hh{int l,r,id;const bool operator < (const hh &x) const {return r<x.r;}}q[sz];

int ans[sz];

int main()

{

    file();

	read(n,m);

	cin>>(s+1);

	rep(i,1,n) pos[i]=SAM::add(s[i]-'0');

	SAM::work();

	int x,y;

	rep(i,1,m) read(x,y),q[i]=(hh){x,y,i};

	sort(q+1,q+m+1);

	int p=1;

	rep(i,1,n)

	{

		LCT::access(pos[i],i);

		while (p<=m&&q[p].r==i) ans[q[p].id]=query(1,1,n,q[p].l,q[p].r),++p;

	}

	rep(i,1,m) printf("%d\n",ans[i]);

	return 0;

}