Description：

给出一个字符串 $S$ ，给出 $Q$ 个操作，给出 $L, R, T$ ，求字典序最小的 $S_1$ ，使得 $S_1$ 为 $S[L\dots R]$ 的子串，且 $S_1$ 的字典序严格大于 $T$ 。输出这个 $S_1$ ，如果无解输出 $-1$ $1 \leq |S| \leq 10 ^ 5, 1 \leq Q \leq 2 \times 10 ^ 5, 1 \leq L \leq R \leq |S|, \sum |T| \leq 2 \times 10 ^ 5$

Solution：

先建出后缀自动机，然后每次拿 $T$ 在上面跑，统计一下最长的合法的位置，这个合法指的是前几位都匹配，下一位必须还能再选出来一个比 $T$ 的下一位严格大的数，求出来这个然后再在下一位找一个比 $T$ 的下一位大一点的字母就求出解了，判断是否是 $S[L\dots R]$ 的子串可以用线段树维护 $Right$ 集合。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

#define MAXL 100010

char S[MAXL];

char c[MAXL];

int q;

namespace SEG

{

	struct node

	{

		int lc,rc;

	}t[MAXL * 60];

	int ptr = 0;

	int newnode(){return ++ptr;}

	int root[MAXL << 1];

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

	void insert(int &rt,int p,int l,int r)

	{

		if(rt == 0)rt = newnode();

		if(l == r)return;

		if(p <= mid)insert(t[rt].lc,p,l,mid);

		else insert(t[rt].rc,p,mid + 1,r);

		return;

	}

	int merge(int x,int y)

	{

		if(x == 0 || y == 0)return x + y;

		int rt = newnode();

		t[rt].lc = merge(t[x].lc,t[y].lc);

		t[rt].rc = merge(t[x].rc,t[y].rc);

		return rt;

	}

	bool query(int rt,int L,int R,int l,int r)

	{

		if(rt == 0)return 0;

		if(L <= l && r <= R)return true;

		bool res = false;

		if(L <= mid)res |= query(t[rt].lc,L,R,l,mid);

		if(R > mid)res |= query(t[rt].rc,L,R,mid + 1,r);

		return res;

	}

}

namespace SAM

{

	struct node

	{

		int par,maxl;

		int tr[27];

	}s[MAXL << 1];

	int ptr = 1,root = 1,last = 1;

	int newnode(int l){int k = ++ptr;s[k].maxl = l;return k;}

	void extend(int k)

	{

		int p = last;

		int np = newnode(s[p].maxl + 1);

		for(;p && s[p].tr[k] == 0;p = s[p].par)s[p].tr[k] = np;

		if(p == 0)s[np].par = root;

		else

		{

			int q = s[p].tr[k];

			if(s[p].maxl + 1 == s[q].maxl)s[np].par = q;

			else

			{

				int nq = newnode(s[p].maxl + 1);

				memcpy(s[nq].tr,s[q].tr,sizeof(s[q].tr));

				s[nq].par = s[q].par;

				s[q].par = s[np].par = nq;

				for(;p && s[p].tr[k] == q;p = s[p].par)s[p].tr[k] = nq;

			}

		}

		last = np;

		return;

	}

}

struct edge

{

	int to,nxt;

}e[MAXL << 1];

int edgenum = 0;

int lin[MAXL << 1] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	return;

}

void dfs(int k)

{

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		dfs(e[i].to);

		SEG::root[k] = SEG::merge(SEG::root[k],SEG::root[e[i].to]);

	}

	return;

}

int main()

{

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

	int l = strlen(S + 1);

	for(int i = 1;i <= l;++i)

	{

		SAM::extend(S[i] - 'a' + 1);

		SEG::insert(SEG::root[SAM::last],i,1,l);

	}

	for(int i = 2;i <= SAM::ptr;++i)add(SAM::s[i].par,i);

	dfs(1);

	scanf("%d",&q);

	int L,R;

	for(int i = 1;i <= q;++i)

	{

		scanf("%d%d%s",&L,&R,c + 1);

		int m = strlen(c + 1);c[++m] = 'a' - 1;

		int cur = SAM::root;

		int k = 0;

		int ans = 0;

		for(;k < m;++k)

		{

			int nxt = SAM::s[cur].tr[c[k + 1] - 'a' + 1];

			if(nxt != 0 && SEG::query(SEG::root[nxt],L + k,R,1,l))

			{

				cur = nxt;

			}

			else break;

			bool tag = false;

			for(int i = c[k + 2] - 'a' + 2;i <= 26;++i)

			{

				int nxt = SAM::s[cur].tr[i];

				if(nxt != 0 && SEG::query(SEG::root[nxt],L + k + 1,R,1,l))

				{

					tag = true;

					break;

				}

			}

			if(tag)ans = max(ans,k + 1);

		}

		bool found = false;

		cur = SAM::root;

		for(int i = 1;i <= ans;++i)

		{

			cur = SAM::s[cur].tr[c[i] - 'a' + 1];

			putchar(c[i]);

		}

		for(int i = c[ans + 1] - 'a' + 2;i <= 26;++i)

		{

			int nxt = SAM::s[cur].tr[i];

			if(nxt != 0 && SEG::query(SEG::root[nxt],L + ans,R,1,l))

			{

				found = true;

				putchar(i + 'a' - 1);puts("");

				break;

			}

		}

		if(!found)puts("-1");

	}

	return 0;

}