勇者的后缀

题目链接：luogu U142356

题目大意

给你一个字符串，每次询问给你 i,l,r 要你求所有 l~r 为起点的后缀中哪一个跟 i 为起点的后缀的最长公共前缀最长。
如果有多个一样长的，输出字典序最小的。

思路

首先考虑 SA / SAM。
然后如果是 SA，那两个后缀之间的最长公共前缀就是 $\mathrm{rnk}$ 区间中的 $\min$。
如果是 SAM，那就是 fail 树上的 LCA（反着建）

然后考虑怎么找 $\min$ 中最大的或者 LCA 最下面的。（其实会发现大概是同一种）
那因为是 $\min$，自然是短的时候才会出现（LCA 其实最下面的也是要在 dfs 序最近的）
所以我们就找到它的前驱后继。

然而我们只能找 $l\sim r$ 的，所以我们可以用主席树来维护找。
（然后找前驱后继有一个简单的方法是先找它前面一共有多少个 $k$，然后前驱就是定位到第 $k-1$ 个，同理后继就是 $k$）
（什么为啥总是大家都知道的我不知道，流眼泪的了）

然后发现如果答案相同要选字典序最小的。
考虑怎么搞，首先两个答案比一比，如果右边比左边优那右边肯定是右边最优的（因为都是按字典序排的，SAM 的 dfs 序其实也是字典序）

那左边的呢？
那我们就二分找到最左边的，然后就用那个即可。

代码

#include
#include
#include
#include
#include

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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164