Description
pps又开始dota视频直播了！一群每天被pps虐的蒟蒻决定学习pps的操作技术，他们把pps在这局放的技能记录了下来，每个技能用一个字符表示。经过研究，蒟蒻们发现字典序更大的连招威力更大。于是所有蒟蒻都想学习pps最强的连招。但是他们太弱了，不能学会整个视频里的连招，只能学会陈老师一段区间间内的连招，可是这个他们求不出，于是只好向你求助。为了蒟蒻们不再被pps虐（怎么可能），请你帮帮他们。简化题意：给你一个字符串，每次询问你一段区间的字典序最大的子串。
第一行是一个字符串S，表示pps放的技能
第二行一个正整数Q，表示询问个数
接下来Q行，每行两个正整数[l,r]，表示询问区间[l,r]中的字典序最大的子串。
Output
Q行，每行一个正整数，表示该区间内字典序最大的子串的起始位置。
1
2
3
4
5
6
7
| Lets_go_mod_p!
5
2 2
3 3
2 5
1 10
2 9
|
Sample Output
HINT
\begin{equation}
1 \le |S| \le 100000 \
1 \le Q \le 100000 \
1 \le l \le r \le |S|
\end{equation}
Solution
哇！神题！！
完全没有思路，点击这里 有题解。
离线+LCP+单调栈
我们考虑右端点r向右移动的过程，a_i表示i…r这一段的答案是多少。
对于两个后缀i,j(i<j)记lcp的长度为L，如果:
- rank[i]>rank[j] i一定比j优
- rank[i]<rank[j] && r-j+1<=L i比j优
- rank[i]<rank[j] && r-j+1>L j比i优（此时我们可以用j顶替i）
如果存在j比i优且j>i，那么i不可能成为答案。
这个很像单调栈，于是我们用一个栈来维护一个后缀第一次是被哪一个后面的后缀顶替的。
怎么维护呢？
从tail开始向前找，直到r不能顶替stack的末尾元素位置。
为什么r不会和tail-1发生顶替？因为a这个数组是单增的。用r去更新一段区间的答案已经不优秀了，这个区间如果再往左扩展，肯定不如原来的优秀。
然后我们加入r的时候需要删除掉所有满足加入r这个元素后此后缀会被顶替的后缀，同样，这个后缀不能成为答案了，本来就不如这个后缀优秀的后缀也不可能更新答案。
于是我们就变成了这么个问题：维护一些数字（可能成为答案的点），支持查询lower_bound（大于等于转折点的最靠左的位置）。
为什么是最靠左的？还是用单调栈来解决。如果他不是字典序最大的，我们肯定早就pop出来啦（类似单调栈求min/max，取队头）！
Code
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
| #include <set>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ULL;
const int maxn = 500005;
const ULL Base = 233ull;
set<int> S;
bool vis[maxn];
char str[maxn];
ULL T[maxn], H[maxn];
vector<int> h[maxn], s[maxn];
vector<pair<int, int> > q[maxn];
int ans[maxn], sta[maxn], tail, n, x, y, Q, l;
inline int getint() {int r=0;bool b=true;char c=getchar();while('0'>c||c>'9'){if(c=='-')b=false;c=getchar();}while('0'<=c&&c<='9'){r=(r<<3)+(r<<1)+(c-'0');c=getchar();}if(b)return r;return -r;}
ULL cal(int l, int r) { return H[r] - H[l-1] * T[r-l+1]; }
int lcp(int i, int j) {
int l = -1, r = n - i, mid;
while (l < r) {
mid = (l + r + 1) >> 1;
if (cal(i, i + mid) == cal(j, j + mid)) l = mid;
else r = mid - 1;
}
return l + 1;
}
void dfs(int now) {
if (vis[now]) return; vis[now] = true; S.erase(now);
for (int i = 0; i < s[now].size(); ++i) dfs(s[now][i]);
}
int main() {
register int i, j;
for (scanf("%s", str + 1), n = strlen(str + 1), T[0] = 1ull, i = 1; i <= n; ++i) { T[i] = T[i-1] * Base; H[i] = H[i-1] * Base + str[i]; }
for (Q = getint(), i = 0; i < Q; ++i) {x=getint();y=getint();q[y].push_back(make_pair(x,i));}
for (i = 1; i <= n; ++i) {
while (tail > 0) {
l = lcp(i, sta[tail]);
if (str[i+l] < str[sta[tail]+l]) break;
h[i+l].push_back(sta[tail]);
s[i].push_back(sta[tail]);
--tail;
}
S.insert(i);
sta[++tail] = i;
for (j = 0; j < h[i].size(); ++j) dfs(h[i][j]);
for (j = 0; j < q[i].size(); ++j) ans[q[i][j].second] = *S.lower_bound(q[i][j].first);
}
for (i = 0; i < Q; ++i) printf("%d\n", ans[i]);
}
|