写在前面的

好久没有写这样令人心旷神怡的题目了。

分析

在区间 中选取一个字典序严格大于 的且字典序尽量小的字串 。我们先考虑如何让 的字典序严格大于 ，那么必然存在一个 使得 并且 。既然是要让字典序最小，所以考虑从大到小枚举 ，找到第一个可行的 就退出，就可以保证字典序的最小。那么现在就是询问这个 区间中，是否有这样的一个字串 。这让我们想到了后缀自动机，后缀自动机可以根据 等价类来处理这个串是否出现。我们先在后缀自动机上根据转移边匹配 ，匹配的最长长度为 。那么我们就由小到大枚举字母，如果有这样一条转移边。我们就查询转移节点的 集合中，是否有一个 是属于 ，如果有，那么这个就是可行的子串，退出就好了。

关于线段树合并

上述算法已经解决大部分问题，但是查询转移节点的 集合中，是否有一个 是属于 。这个步骤的时间复杂度的非常的高，达到了 级别。必须考虑优化，这个优化也比较显然。对于一个区间是否有一个数，这里不是线段树常使用的地方吗。所以我们考虑线段树合并。有一个小细节，因为我们还有使用合并后的子树节点，所以我们必须新开节点来记录合并值，不能破坏原树结构。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 100;
struct Node{int len,link,nxt[26];}st[N<<1];
int last = 0,si = 0;
int lc[N * 20],rc[N * 20],rt[N],cnt[N * 20],size,n,m;
vector<int> G[N];
void insert(int &u,int l,int r,int pos) {
    u = ++size;cnt[u]++;if(l == r) return;
    int mid = l + r >> 1;
    if(pos <= mid) insert(lc[u],l,mid,pos);
    else insert(rc[u],mid+1,r,pos);
}
int merge(int x,int y,int l,int r) {
    if(!x || !y) return x|y;
    int mid = l + r >> 1;int i = ++size;
    cnt[i] = cnt[x] + cnt[y];
    if(l == r) return i;
    lc[i] = merge(lc[x],lc[y],l,mid);
    rc[i] = merge(rc[x],rc[y],mid+1,r);
    return i;
}
bool ask(int u,int l,int r,int L,int R) {
    if(!u) return 0;
    if(l > R || r < L) return 0;
    if(L <= l && r <= R) return (cnt[u] > 0);
    int mid = l + r >> 1;
    return ((ask(lc[u],l,mid,L,R) + (ask(rc[u],mid+1,r,L,R))) > 0);
}
void init() {st[0].link = -1;si++;}
void insert(int c,int endpos) {
    int cur = si++;st[cur].len = st[last].len + 1;
    int p = last; insert(rt[cur],1,n,endpos);
    while(p != -1 && !st[p].nxt[c]) {
        st[p].nxt[c] = cur;p = st[p].link;
    }
    if(p == -1) st[cur].link = 0;
    else {
        int q = st[p].nxt[c];
        if(st[q].len == st[p].len + 1) st[cur].link = q;
        else {
            int cl = si++;st[cl].len = st[p].len + 1;st[cl].link = st[q].link;
            for(int i = 0;i < 26;i++) st[cl].nxt[i] = st[q].nxt[i];
            while(p != -1 && st[p].nxt[c] == q) {
                st[p].nxt[c] = cl;p = st[p].link;
            }
            st[cur].link = st[q].link = cl;
        }
    }
    last = cur;
}
char S[N],ch[N];
int stk[N],top;
void dfs(int x) {for(auto y:G[x]) {dfs(y);rt[x] = merge(rt[x],rt[y],1,n);}}
int main() {
    scanf("%s%d",S+1,&m);n = strlen(S+1);init();
    for(int i = 1;i <= n;i++) insert(S[i]-'a',i);
    for(int i = 1;i < si;i++) {G[st[i].link].push_back(i);};
    dfs(0);
    while(m--) {
        int l,r;scanf("%d%d%s",&l,&r,ch+1);int len = strlen(ch+1);
        stk[top = 1] = 0;ch[len + 1] = 'a' - 1;
        for(int i = 1,p = 0;i <= len && st[p].nxt[ch[i] - 'a'];i++) 
        stk[++top] = p = st[p].nxt[ch[i] - 'a'];
        bool check = 0;
        for(int i = min(r-l+1,top);i >= 1 && (check==0);i--) {
            for(int j = ch[i] - 'a' + 1;j < 26;j++) {
                if(st[stk[i]].nxt[j] == 0) continue; 
                if(ask(rt[ st[stk[i]].nxt[j] ],1,n,l+i-1,r)) {
                    for(int k = 1;k < i;k++) printf("%c",ch[k]);
                    printf("%c",(char)(j + 'a'));
                    printf("\n");
                    check = 1;
                    break;
                }
            }
        }
        if(check == 0) puts("-1");
    }
    return 0;
}