题解：P4143 采集矿石

#include <bits/stdc++.h>
using namespace std;
#define N 200005
#define int long long
int L[N << 2], R[N << 2], tag[N << 2], val[N << 2];

inline void cov(int u, int x) {
	if (~x)
		val[u] = (R[u] - L[u] + 1) * x, tag[u] = x;
}

inline void down(int u) {
	if (~tag[u])
		cov(u * 2, tag[u]), cov(u * 2 + 1, tag[u]), tag[u] = -1;
}

inline void up(int u) {
	val[u] = val[u * 2] + val[u * 2 + 1];
}

void build(int l, int r, int p) {
	L[p] = l, R[p] = r, tag[p] = -1;
	if (l == r)
		return;
	int m = (l + r) / 2;
	build(l, m, p * 2), build(m + 1, r, p * 2 + 1), up(p);
}

int qus(int l, int r, int p) {
	if (l <= L[p] && r >= R[p])
		return val[p];
	if (l > R[p] || r < L[p])
		return 0;
	down(p);
	return qus(l, r, p * 2) + qus(l, r, p * 2 + 1);
}

void add(int l, int r, int p, int v) {
	if (l <= L[p] && r >= R[p])
		return cov(p, v);
	if (l > R[p] || r < L[p])
		return;
	down(p), add(l, r, p * 2, v), add(l, r, p * 2 + 1, v), up(p);
}

inline int que(int r) {
	return qus(1, r, 1);
}
int ans[N], sa[N], rk[N << 1], hei[N], cnt[N], oldsa[N << 1], oldrk[N << 1], a[N], n, tot, res;
string s;

void SA() {
	for (int i = 1; i <= n; i++)
		cnt[rk[i] = s[i] - 'a' + 1]++;
	for (int i = 1; i <= 26; i++)
		cnt[i] += cnt[i - 1];
	for (int i = n; i; i--)
		sa[cnt[rk[i]]--] = i;
	for (int i = 1; i <= n; i++)
		oldrk[i] = rk[i];
	for (int i = 1, p = 0; i <= n; i++)
		rk[sa[i]] = (p += (oldrk[sa[i - 1]] != oldrk[sa[i]]));
	for (int d = 1; d < n; d <<= 1) {
		memset(cnt, 0, sizeof(cnt));
		for (int i = 1; i <= n; i++)
			cnt[rk[sa[i] + d]]++;
		for (int i = 1; i <= n; i++)
			cnt[i] += cnt[i - 1];
		for (int i = 1; i <= n; i++)
			oldsa[i] = sa[i];
		for (int i = n; i; i--)
			sa[cnt[rk[oldsa[i] + d]]--] = oldsa[i];
		memset(cnt, 0, sizeof(cnt));
		for (int i = 1; i <= n; i++)
			cnt[rk[sa[i]]]++;
		for (int i = 1; i <= n; i++)
			cnt[i] += cnt[i - 1];
		for (int i = 1; i <= n; i++)
			oldsa[i] = sa[i];
		for (int i = n; i; i--)
			sa[cnt[rk[oldsa[i]]]--] = oldsa[i];
		for (int i = 1; i <= n; i++)
			oldrk[i] = rk[i];
		for (int i = 1, p = 0; i <= n; i++)
			rk[sa[i]] = (p += (oldrk[sa[i - 1]] != oldrk[sa[i]] || oldrk[sa[i - 1] + d] != oldrk[sa[i] + d]));
	}
	for (int i = 1, k = 0; i <= n; i++) {
		if (rk[i] == 0)
			continue;
		if (k)
			k--;
		while (s[i + k] == s[sa[rk[i] - 1] + k])
			k++;
		hei[rk[i]] = k, tot -= k;
	}
}

main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> s, s = ' ' + s, n = s.size() - 1, tot = n * (n + 1) / 2;
	for (int i = 1; i <= n; i++)
		cin >> a[i], a[i] += a[i - 1], ans[i] = -1;
	SA(), build(1, n, 1);
	for (int i = 1; i <= n; i++) {
		if (i == 1)
			add(1, n - sa[i] + 1, 1, 1);
		else {
			int tot = qus(1, n - sa[i - 1] + 1, 1), lps = hei[i] ? qus(1, hei[i], 1) : 0;
			add(hei[i] + 1, hei[i] + 1, 1, tot - lps + 1);
			if (hei[i] < n - sa[i])
				add(hei[i] + 2, n - sa[i] + 1, 1, 1);
		}
		int l = sa[i], r = n;
		while (l ^ r) {
			int m = (l + r + 1) / 2, len = m - sa[i] + 1;
			if (tot - que(len) + 1 < a[m] - a[sa[i] - 1])
				r = m - 1;
			else
				l = m;
		}
		if (tot - que(l - sa[i] + 1) + 1 == a[l] - a[sa[i] - 1])
			ans[sa[i]] = l, res++;
	}
	cout << res << '\n';
	for (int i = 1; i <= n; i++)
		if (~ans[i])
			cout << i << ' ' << ans[i] << '\n';
}