CF1037H Security 后缀自动机 + right集合线段树合并 + 贪心

题目描述：

给定一个字符串 $S$

给出 $Q$ 个操作，给出 $L,R,T$，求出字典序最小的 $S_{1}$ 为 $S[L...R]$的子串，且 $S_{1}$ 的字典序严格大于 $T$. 输出这个 $S_{1}$，如果无解输出 $-1$

$1\leqslant|S|\leqslant10^5,1\leqslant Q\leqslant2\times10^5,1\leqslant L\leqslant R\leqslant |S|,\sum|T|\leqslant2\times10^5$
 题解：

正解还是比较好想的.
不难想到 $S_{1}$ 一定是与 $T$ 有一段相等的前缀并在一个位置上不同.
也就是说，$S_{1}=Prefix(T)+c$ ，$('a'\leqslant c\leqslant'z')$
先考虑没有 $L,R$ 的限制.
先将 $T$ 在后缀自动机上进行匹配，直到匹配不了.
贪心地从后向前枚举不同的那个字符，如果当前找到了不同字符，则直接输出即可. (这一定是最优的，因为前缀更长)
现在有了 $L,R$ 的限制，直接来一遍线段树合并维护 $right$ 集合即可.
在后缀自动机上匹配的时候到线段树中判断一下在不在 $[L,R]$ 中即可. 

#include<bits/stdc++.h>

#define setIO(s) freopen(s".in","r",stdin)

#define maxn 220000

using namespace std;

int n;

int rt[maxn];

namespace tr

{

	#define mid ((l+r)>>1)

	#define lson t[x].l

	#define rson t[x].r

	int cnt;

	int newnode() { return ++cnt; }

	struct Node{ int l,r,sumv; }t[maxn * 50];

	int merge(int u,int v)

	{

		if(!u||!v) return u+v;

		int x=newnode();

		t[x].sumv=t[u].sumv+t[v].sumv;

		lson=merge(t[u].l,t[v].l);

		rson=merge(t[u].r,t[v].r);

		return x;

	}

	void update(int &x,int l,int r,int k,int delta)

	{

		if(!x)x=newnode();

		t[x].sumv+=delta;

		if(l==r) return;

		if(k<=mid) update(lson, l, mid, k, delta);

		else update(rson, mid + 1, r, k, delta);

	}

	int query(int x,int l,int r,int L,int R)

	{

		if(!x || L>R)return 0;

		if(l>=L&&r<=R) return t[x].sumv;

		int tmp=0;

		if(L<=mid) tmp+=query(lson,l,mid,L,R);

		if(R>mid) tmp+=query(rson, mid+1,r,L,R);

		return tmp;

	}

	#undef lson

	#undef rson

};

namespace SAM

{

	int tot,last;

	int len[maxn], ch[maxn][30], f[maxn], rk[maxn], C[maxn];

	void init() { tot = last = 1; }

	void extend(int c)

	{

		int np=++tot,p=last;

		last=np, len[np]=len[p]+1;

		while(p&&!ch[p][c]) ch[p][c]=np,p=f[p];

		if(!p) f[np]=1;

		else

		{

			int q=ch[p][c];

			if(len[q]==len[p]+1) f[np]=q;

			else

			{

				int nq=++tot;

				len[nq]=len[p]+1;

				memcpy(ch[nq],ch[q],sizeof(ch[q]));

				f[nq]=f[q],f[np]=f[q]=nq;

				while(p&&ch[p][c]==q) ch[p][c]=nq, p=f[p];

			}

		}

		tr::update(rt[np], 1, n, len[np], 1);

	}

	void prepare()

	{

		int i,j;

		for(i=1;i<=tot;++i) ++C[len[i]];

		for(i=1;i<=tot;++i) C[i]+=C[i-1];

		for(i=1;i<=tot;++i) rk[C[len[i]]--]=i;

		for(i=tot;i>=1;--i)

		{

			j=rk[i];

			rt[f[j]]=tr::merge(rt[f[j]], rt[j]);

		}

	}

};

char str[maxn], T[maxn], stac[maxn];

int cur[maxn];

int main()

{

	int i,j,Q;

	// setIO("input");

	scanf("%s",str+1);

	n=strlen(str+1);

	SAM::init();

	for(i=1;i<=n;++i)

	{

		SAM::extend(str[i]-'a');

	}

	SAM::prepare();

	scanf("%d",&Q);

	while(Q--)

	{

		int l,r,_len,trace=0,top=0,L;

		scanf("%d%d%s",&l,&r,T+1);

		L=l;

		_len=strlen(T+1);

		cur[0]=1;

		for(i=1;i<=min(_len,n-1);++i)

		{

			int c=T[i]-'a';

			if(SAM::ch[cur[i-1]][c] && tr::query(rt[SAM::ch[cur[i-1]][c]], 1, n, l, r))

			{

				cur[i]=SAM::ch[cur[i-1]][c];

				++l,   trace=i, stac[++top]=T[i];

			}

			else break;

		}

		T[0]='a';

		int flag=0;

		for(i=min(n-1,trace);i>=0;--i)

		{

			int c= i + 1 > _len ? -1 : T[i+1] - 'a';

		//	if(flag) break;

			for(j=c+1;j<27;++j)

			{

				if(SAM::ch[cur[i]][j] && tr::query(rt[SAM::ch[cur[i]][j]] , 1, n, l, r))

				{

					flag=1;

					stac[++top]='a'+j;

					break;

				}

			}

			if(flag) break;

			--l;

			--top;

		}

		if(!flag) printf("-1\n");

		else

		{

			for(i=1;i<=top;++i) printf("%c",stac[i]);

			printf("\n");

		}

	}

	return 0;

}

CF1037H Security 后缀自动机 + right集合线段树合并 + 贪心的相关教程结束。