The brave suffix

题目链接：luogu U142356

题目大意

给你一个字符串,Each time you ask to you i,l,r To you all l~r As a starting point of the suffix which with i As a starting point of the suffix public longest prefix the longest.
If there are multiple as long,输出字典序最小的.

思路

首先考虑 SA / SAM.
然后如果是 SA,Between the two suffix public longest prefix is $\mathrm{rnk}$ 区间中的 $\min$.
如果是 SAM,那就是 fail 树上的 LCA（The opposite building）

Then consider how to find $\min$ The largest of or LCA 最下面的.（Actually find is probably the same）
那因为是 $\min$,Nature is a short time will appear（LCA In fact is on the bottom of the in dfs Order the latest）
So we find it is the precursor of subsequent.

However, we can only find $l\sim r$ 的,So we can use, chairman of the tree to maintain looking for.
（Then find precursor successor has a simple method is to look for the front of it there are many $k$,And then precursor is positioning to the first $k-1$ 个,Similarly a successor is $k$）
（What I don't know why everyone always know,Tears of）

Selected dictionary and found that if the answer is the same to the smallest.
Consider how make,The first two answers compare,If the right than the left superior right must be right that the optimum（Because all is according to the dictionary sequence row,SAM 的 dfs Order is the dictionary order）

What about on the left side of the？
Then we can find the most on the left side of the binary,And then use that can.

代码

#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 2e5 + 100; 
int n, ans1[N], ans2[N], ss[N];
char s[N];
struct Ask {
    
	int id, l, r;
};
vector <Ask> q[N];

int sa[N], xx[N], yy[N], fir[N], log2_[N];
int height[N][21], rnk[N], tong[N], kind, ynum;

void Sort(int m, int *x, int *y) {
    
	for (int i = 1; i <= m; i++) tong[i] = 0;
	for (int i = 1; i <= n; i++) tong[x[i]]++;
	for (int i = 2; i <= m; i++) tong[i] += tong[i - 1];
	for (int i = n; i >= 1; i--) sa[tong[fir[i]]--] = y[i];
}

void SA(int *r, int *sa, int n, int m) {
    
	int *x = xx, *y = yy;
	for (int i = 1; i <= n; i++) x[i] = r[i] + 1;
	for (int i = 1; i <= n; i++) y[i] = i;
	for (int i = 1; i <= n; i++) fir[i] = x[y[i]];
	Sort(m, x, y);
	
	for (int j = 1; j < n; j <<= 1) {
    
		ynum = 0;
		for (int i = n - j + 1; i <= n; i++)
			y[++ynum] = i;
		for (int i = 1; i <= n; i++)
			if (sa[i] > j) y[++ynum] = sa[i] - j;
		for (int i = 1; i <= n; i++) fir[i] = x[y[i]];
		Sort(m, x, y);
		
		swap(x, y);
		kind = 1;
		x[sa[1]] = 1;
		for (int i = 2; i <= n; i++)
			if (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + j] == y[sa[i - 1] + j]) x[sa[i]] = kind;
				else x[sa[i]] = ++kind;
		
		if (kind == n) break;
		m = kind;
	}
}

void get_height(int *r, int *sa, int n) {
    
	int k = 0, j;
	for (int i = 1; i <= n; i++) rnk[sa[i]] = i;
	for (int i = 1; i <= n; i++) {
    
		if (k) k--;
		j = sa[rnk[i] - 1];
		while (r[i + k] == r[j + k] && i + k <= n && j + k <= n) k++;
		height[rnk[i]][0] = k;
	}
}

void get_RMQ(int n) {
    
	log2_[0] = -1; for (int i = 1; i <= n; i++) log2_[i] = log2_[i >> 1] + 1;
	for (int i = 1; i <= 20; i++)
		for (int j = 1; j + (1 << i) - 1 <= n; j++)
			height[j][i] = min(height[j][i - 1], height[j + (1 << (i - 1))][i - 1]);
}

int RMQ_sa(int l, int r) {
    
	if (!l || !r) return 0;
	if (l == r) return n - l + 1;
	l = rnk[l]; r = rnk[r]; if (l > r) swap(l, r);
	l++; int k = log2_[r - l + 1];
	return min(height[l][k], height[r - (1 << k) + 1][k]);
}

int RMQ_rnk(int l, int r) {
    
	if (!l || !r) return 0;
	if (l == r) return n - sa[l] + 1;
	if (l > r) swap(l, r);
	l++; int k = log2_[r - l + 1];
	return min(height[l][k], height[r - (1 << k) + 1][k]);
}

struct XD_tree {
    
	int ls[N << 6], rs[N << 6], sum[N << 6], tot;
	
	int copy(int x) {
    
		int now = ++tot; ls[now] = ls[x]; rs[now] = rs[x]; sum[now] = sum[x]; return now;
	}
	
	void insert(int &now, int l, int r, int pl) {
    
		now = copy(now); sum[now]++;
		if (l == r) return ; int mid = (l + r) >> 1;
		if (pl <= mid) insert(ls[now], l, mid, pl); else insert(rs[now], mid + 1, r, pl);
	}
	
	int get_sum(int now1, int now2, int l, int r, int L, int R) {
    
		if (!(sum[now2] - sum[now1])) return 0;
		if (L <= l && r <= R) return sum[now2] - sum[now1];
		int mid = (l + r) >> 1, re = 0;
		if (L <= mid) re += get_sum(ls[now1], ls[now2], l, mid, L, R);
		if (mid < R) re += get_sum(rs[now1], rs[now2], mid + 1, r, L, R);
		return re;
	}
	
	int get_k(int now1, int now2, int l, int r, int k) {
    
		if (l == r) return l;
		int mid = (l + r) >> 1;
		if (k <= sum[ls[now2]] - sum[ls[now1]]) return get_k(ls[now1], ls[now2], l, mid, k);
			else return get_k(rs[now1], rs[now2], mid + 1, r, k - (sum[ls[now2]] - sum[ls[now1]]));
	}
}T;
int rt[N];

int main() {
    
	scanf("%s", s + 1); n = strlen(s + 1);
	for (int i = 1; i <= n; i++) ss[i] = s[i] - 'a';
	
	SA(ss, sa, n, n);
	get_height(ss, sa, n);
	get_RMQ(n);
	for (int i = 1; i <= n; i++)
		rt[i] = rt[i - 1], T.insert(rt[i], 1, n, rnk[i]);
	
	int Q; scanf("%d", &Q);
	for (int i = 1; i <= Q; i++) {
    
		int x, l, r; scanf("%d %d %d", &x, &l, &r);
		q[x].push_back((Ask){
    i, l, r});
	}
	for (int i = 1; i <= n; i++) {
    
		int x = rnk[i];
		for (int j = 0; j < q[i].size(); j++) {
    
			int id = q[i][j].id, l = q[i][j].l, r = q[i][j].r;
			int num = T.get_sum(rt[l - 1], rt[r], 1, n, 1, x - 1), L = 0, R = 0;
			if (num) L = T.get_k(rt[l - 1], rt[r], 1, n, num);
			if (num < T.sum[rt[r]] - T.sum[rt[l - 1]]) R = T.get_k(rt[l - 1], rt[r], 1, n, num + 1);
			int re1 = RMQ_rnk(L, x), re2 = RMQ_rnk(x, R);
			if (re2 > re1) {
    
				ans1[id] = re2; ans2[id] = sa[R];
			}
			else {
    
				int L_ = 1, R_ = L, re = L;
				while (L_ <= R_) {
    
					int mid = (L_ + R_) >> 1;
					if (RMQ_rnk(mid, x) >= re1) re = mid, R_ = mid - 1;
						else L_ = mid + 1;
				}
				int numb = T.get_sum(rt[l - 1], rt[r], 1, n, 1, re - 1);
				L = T.get_k(rt[l - 1], rt[r], 1, n, numb + 1);
				ans1[id] = re1; ans2[id] = sa[L];
			}
		}
	}
	
	for (int i = 1; i <= Q; i++) printf("%d %d\n", ans1[i], ans2[i]);
	
	return 0;
}