# [JZOJ 5027] [NOI2017 simulation 3.25] historical journey

## Description

People's life not only depends on self struggle, but also considers the historical journey.
The journey of history can be abstracted into a 01 string. As an older person, you want to get some knowledge from the journey of history.
You find that one thing can be regarded as a prefix of 01 string, and the right position of the prefix is the end time of this thing.
The similarity of two things can be seen as the longest common suffix length of these two prefixes.
Now you're curious, what's the similarity between the two most similar things that end up in a range?

## Input

The first line contains two positive integers, n,m, representing the string length and the number of queries.
The second line is a 01 string with a length of n, indicating the history of the journey.
Next m lines, each line has two positive integers l,r indicates that the query interval is from the first position to the r position, including the endpoint, ensuring that 1 < = l < = r < = n.

## Output

Output m lines, and output an integer for each query to represent the maximum similarity.

4 2
0101
1 3
2 4

1
2

## thinking

Consider merging SA according to height from small to large, and maintain the queries in each block.
bitset, O(n ^ 2 / w)

## Code

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define mid (l + r >> 1)
#define ls (k << 1)
#define rs (k << 1 | 1)
using namespace std;

typedef set<int>::iterator I;
const int maxn = 100010;
int n, m, SZ, ans[maxn], rk[maxn], sa[maxn], mx[maxn << 2];
int ht[maxn], buc[maxn], sc[maxn], fa[maxn], id[maxn], cur[maxn];
char s[maxn];
vector<pair<int, int> > Q[maxn], M[maxn];
set<int> pos[maxn];
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
bool comp(int i, int j) { return ht[i] > ht[j]; }

for (int i = 1; i <= SZ; i++) buc[i] = 0;
for (int i = 1; i <= n; i++) buc[rk[i]]++;
for (int i = 1; i <= SZ; i++) buc[i] += buc[i - 1];
for (int i = n; i; i--) sa[buc[rk[sc[i]]]--] = sc[i];
}

void calc_sa() {
for (int i = 1; i <= n; i++) {
rk[i] = s[i] - '0' + 1, sc[i] = i;
}
for (int k = 1; k <= n; k <<= 1) {
int cnt = 0;
for (int i = n - k + 1; i <= n; i++) sc[++cnt] = i;
for (int i = 1; i <= n; i++) {
if (sa[i] > k) sc[++cnt] = sa[i] - k;
}
radix_sort(), swap(rk, sc), rk[sa[1]] = cnt = 1;
for (int i = 2; i <= n; i++) {
rk[sa[i]] = (sc[sa[i]] == sc[sa[i - 1]] &&
sc[sa[i] + k] == sc[sa[i - 1] + k] ? cnt : ++cnt);
}
SZ = cnt; if (cnt == n) break;
}
for (int i = 1, j = 0; i <= n; i++) {
if (rk[i] == 1) { j = ht[rk[i]] = 0; continue; }
j = max(0, j - 1);
while (s[sa[rk[i] - 1] + j] == s[i + j]) j++;
ht[rk[i]] = j;
}
}

void init() {
for (int i = 1; i <= n; i++) {
fa[i] = id[i] = i, pos[i].insert(i);
}
sort(id + 2, id + n + 1, comp);
for (int i = 2; i <= n; i++) {
int x = sa[id[i]], y = sa[id[i] - 1], len = ht[id[i]];
int fx = find(x), fy = find(y);
if (pos[fx].size() > pos[fy].size()) swap(fx, fy);
for (I it1 = pos[fy].begin(); it1 != pos[fy].end(); it1++) {
I it2 = pos[fx].insert(*it1).first, it3;
if (it2 != pos[fx].begin()) {
it3 = it2; it3--;
if (find(*it2) != find(*it3)) {
M[*it3].push_back(make_pair(*it2, len));
}
}
it3 = it2; it3++;
if (it3 != pos[fx].end() && find(*it2) != find(*it3)) {
M[*it2].push_back(make_pair(*it3, len));
}
}
fa[fy] = fx;
}
}

void upd(int k, int l, int r, int p, int v) {
if (l == r) { mx[k] = v; return; }
if (mid >= p) upd(ls, l, mid, p, v);
else upd(rs, mid + 1, r, p, v);
mx[k] = max(mx[ls], mx[rs]);
}

int query(int k, int l, int r, int ql, int qr) {
if (l >= ql && r <= qr) return mx[k];
int ans = 0;
if (mid >= ql) ans = max(ans, query(ls, l, mid, ql, qr));
if (mid < qr) ans = max(ans, query(rs, mid + 1, r, ql, qr));
return ans;
}

int main()
{
freopen("history.in", "r", stdin);
freopen("history.out", "w", stdout);
scanf("%d %d %s", &n, &m, s + 1);
reverse(s + 1, s + n + 1), calc_sa(), init();
for (int i = 1, l, r; i <= m; i++)
{
scanf("%d %d", &r, &l);
l = n - l + 1, r = n - r + 1;
Q[l].push_back(make_pair(r, i));
}
for (int i = n; i; i--)
{
for (int j = 0; j < M[i].size(); j++)
{
cur[M[i][j].first] = max(cur[M[i][j].first], M[i][j].second);
upd(1, 1, n, M[i][j].first, cur[M[i][j].first]);
}
for (int j = 0; j < Q[i].size(); j++)
{
ans[Q[i][j].second] = query(1, 1, n, i, Q[i][j].first);
}
}
for (int i = 1; i <= m; i++)
{
printf("%d\n", ans[i]);
}
return 0;
}
705 original articles published, 392 praised, 140000 visitors+

Added by peerData on Sun, 26 Jan 2020 11:50:25 +0200