【Luogu4143】采集矿石（SA，线段树，二分）

Description

https://www.luogu.org/problemnew/show/P4143

Code

/************************************************ * Au: Hany01 * Prob: Platform * Email: hany01@foxmail.com ************************************************/

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)
#define rep(i, j) for (register int i = 0, i##_end_ = (j); i < i##_end_; ++ i)
#define For(i, j, k) for (register int i = (j), i##_end_ = (k); i <= i##_end_; ++ i)
#define Fordown(i, j, k) for (register int i = (j), i##_end_ = (k); i >= i##_end_; -- i)
#define Set(a, b) memset(a, b, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define x first
#define y second
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) ((int)(a).size())
#define INF (0x3f3f3f3f)
#define INF1 (2139062143)
#define Mod (1000000007)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define y1 wozenmezhemecaia

template <typename T> inline bool chkmax(T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }

inline int read()
{
register int _, __; register char c_;
for (_ = 0, __ = 1, c_ = getchar(); c_ < '0' || c_ > '9'; c_ = getchar()) if (c_ == '-') __ = -1;
for ( ; c_ >= '0' && c_ <= '9'; c_ = getchar()) _ = (_ << 1) + (_ << 3) + (c_ ^ 48);
return _ * __;
}

const int maxn = 200005;

int n, val[maxn], c[maxn], mm, sum[maxn];
char s[maxn];
vector<PII> lst;

int rk[maxn << 1], sa[maxn << 1], tp[maxn << 1], height[maxn << 1];
LL rksum[maxn], tot;

inline void RadixSort()
{
For(i, 1, mm) c[i] = 0;
For(i, 1, n) ++ c[rk[i]];
For(i, 1, mm) c[i] += c[i - 1];
Fordown(i, n, 1) sa[c[rk[tp[i]]] --] = tp[i];
}

inline void build(char *s)
{
For(i, 1, n) rk[i] = s[i], tp[i] = i;
mm = 300, RadixSort();
for (register int k = 1, p; k <= n; k <<= 1) {
p = 0;
For(i, n - k + 1, n) tp[++ p] = i;
For(i, 1, n) if (sa[i] > k) tp[++ p] = sa[i] - k;
RadixSort(), swap(rk, tp), rk[sa[1]] = 1, mm = 1;
For(i, 2, n) rk[sa[i]] = tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i] + k] == tp[sa[i - 1] + k] ? mm : ++ mm;
if (mm == n) break;
}

for (int i = 1, j, k = 0; i <= n; height[rk[i ++]] = k)
for (k = k ? k - 1 : 0, j = sa[rk[i] - 1]; s[i + k] == s[j + k]; ++ k) ;
}

inline void calc() {
For(i, 1, n) rksum[i] = rksum[i - 1] + n + 1 - height[i] - sa[i];
}

struct SegmentTree //Maintain the minimum
{
int tr[maxn << 2];
#define lc (t << 1)
#define rc (lc | 1)
#define mid ((l + r) >> 1)
void build(int t, int l, int r) {
if (l == r) tr[t] = height[l];
else build(lc, l, mid), build(rc, mid + 1, r), tr[t] = min(tr[lc], tr[rc]);
}
int query(int t, int l, int r, int x, int y, int v)
{
if (l == r) return tr[t] < v ? l : 1;
if (x > mid) return query(rc, mid + 1, r, x, y, v);
if (y <= mid) return query(lc, l, mid, x, y, v);
int tmp;
if (tr[rc] >= v) return query(lc, l, mid, x, y, v);
if ((tmp = query(rc, mid + 1, r, x, y, v)) != 1) return tmp;
return query(lc, l, mid, x, y, v);
}
#undef mid
}ST;

inline LL check(int l, int r) //Return the rank minus the value
{
register int pos = rk[l], p = ST.query(1, 1, n, 1, pos, r - l + 1), len = r - l + 1, st, ed1, ed2, real = sa[p] + len - 1;
ed1 = (st = sa[p]) + height[p], ed2 = n;
register LL Rk = rksum[p - 1] + real - ed1 + 1;
return (tot - Rk + 1) - (sum[r] - sum[l - 1]);
}

inline int solve()
{
calc(), ST.build(1, 1, n);
tot = rksum[n];
int Ans = 0, st, ed1, ed2, now = 0, l, r, mid;
For(i, 1, n)
{
st = sa[i], l = st, r = n;
while (l < r) {
mid = (l + r) >> 1;
if (check(st, mid) > 0) l = mid + 1; else r = mid;
}
if (!check(st, l)) ++ Ans, lst.pb(mp(st, l));
}
return Ans;
}

int main()
{
File("platform");

scanf("%s", s + 1), n = strlen(s + 1), build(s);
For(i, 1, n) sum[i] = sum[i - 1] + (val[i] = read());
printf("%d\n", solve());
sort(ALL(lst));
rep(i, SZ(lst)) printf("%d %d\n", lst[i].x, lst[i].y);

return 0;
}
//寂寞空庭春欲晚，梨花满地不开门。
// -- 刘方平《春怨》