題意

給定長度為 \(n\) 的字符串 \(s\) 和權值序列 \(v\)。求所有子串 \(s[l,r]\) 使得 \(s[l,r]\) 在所有子串去重后的字典序降序排名，恰好等于 \(v[l,r]\) 的區間和。\(1\leq n\leq 10^5\)。

題解

注意到固定左端點 \(l\) 后，隨著右端點 \(r\) 遞增，\(s[l,r]\) 的字典序降序排名單調遞減，\(v[l,r]\) 的區間和單調遞增，因此每個 \(l\) 最多對應一個合法的 \(r\)。考慮對 \(v\) 的區間和和子串的排名的差值二分，找到第一個 \(\geq 0\) 的 \(r\)。現在我們需要對一個子串 \(s[l,r]\)，求出其在所有子串去重后的字典序降序排名。

考察怎樣的子串 \(s[l',r']\) 會 \(>s[l,r]\)，要么 \(s[l,r]\) 是 \(s[l',r']\) 的前綴，要么 \(s[l',r']\) 在 LCP 的后一位比 \(s[l,r]\) 對應位置要大。不難發現若 \(s[l',r']>s[l,r]\)，則 \(s[l',r''](r'<r''\leq n)\) 也一定 \(>s[l,r]\)，所以我們轉而考慮所有合法的 \(s[l',r']\) 對應的后綴 \(suf_{l'}\) 的性質。

對于第一種 case，相當于固定了一段前綴，那么所有合法后綴的排名必然是一段連續區間 \([L,R]\)。對于第二種 case，我們發現這樣的后綴的排名其實就是 \([R+1,n]\)。因為 \(suf_{rk_R}\) 是排名最大的以 \(s[l,r]\) 為前綴的后綴，那么對于 \(suf_{rk_{R+1}}\) 來說，一定是在一段 LCP 之后，比 \(s[l,r]\) 的對應位大，這就和第二個條件完全契合了。

所以，所有合法的 \(s[l',r']\) 一定是排名處于 \([L,n]\) 之中的后綴的一段前綴。因此 \(s[l,r]\) 的字典序降序排名，實際上就是排名處于 \([L,n]\) 之中的后綴的本質不同前綴個數，減去 \(r-l\)。注意減去 \(r-l\) 是因為我們會把 \(s[l,r]\) 的真前綴也算進去。套用經典結論，排名在 \([L,n]\) 中的后綴的本質不同前綴個數就是 \(\sum\limits_{i=L}^n(n-sa_i+1)-\sum\limits_{i=L+1}^nht_i\)，容易預處理后綴和計算。

至于 \(L\)，可以發現它就是最小的 \(i\)，使得排名在 \([i,rk_l]\) 中的后綴的 LCP 長度 \(\geq r-l+1\)，用 ST 表維護 \(ht\) 即可二分求出。

時間復雜度是 \(\mathcal{O}(n\log^2{n})\) 的。

代碼

#include <bits/stdc++.h>

using namespace std;

#define lowbit(x) ((x) & -(x))
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 5, LGN = 18;

template<typename T> inline void chk_min(T &x, T y) { x = min(x, y); }
template<typename T> inline void chk_max(T &x, T y) { x = max(x, y); }

int n, sz, val[N], pre[N], lg2[N], ans[N];
int sa[N], rk[N], trk[N << 1], id[N], pid[N], buc[N], ht[N];
ll suf1[N], suf2[N];
char s[N];

struct ST {
	int f[LGN][N];
	inline void init() {
		for (int i = 1; i <= n; ++i) f[0][i] = ht[i];
		for (int i = 1; i <= lg2[n]; ++i) for (int j = 1; j <= n - (1 << i) + 1; ++j)
			f[i][j] = min(f[i - 1][j], f[i - 1][j + (1 << i - 1)]);
	}
	inline int query(int l, int r) {
		int k = lg2[r - l + 1];
		return min(f[k][l], f[k][r - (1 << k) + 1]);
	}
} st;

inline void build() {
	int m = 26;
	for (int i = 1; i <= n; ++i) ++buc[rk[i] = s[i] - 'a' + 1];
	for (int i = 1; i <= m; ++i) buc[i] += buc[i - 1];
	for (int i = n; i; --i) sa[buc[rk[i]]--] = i;
	for (int w = 1, p = 0; p < n; w <<= 1, m = p) {
		p = 0;
		for (int i = n - w + 1; i <= n; ++i) id[++p] = i;
		for (int i = 1; i <= n; ++i) if (sa[i] > w) id[++p] = sa[i] - w;
		fill(buc + 1, buc + m + 1, 0);
		for (int i = 1; i <= n; ++i) ++buc[pid[i] = rk[id[i]]];
		for (int i = 1; i <= m; ++i) buc[i] += buc[i - 1];
		for (int i = n; i; --i) sa[buc[pid[i]]--] = id[i];
		p = 0, copy(rk + 1, rk + n + 1, trk + 1);
		for (int i = 1; i <= n; ++i) rk[sa[i]] = (trk[sa[i - 1]] == trk[sa[i]] && trk[sa[i - 1] + w] == trk[sa[i] + w]) ? p : ++p;
	}
	for (int i = 1, k = 0; i <= n; ++i) {
		if (k) --k;
		while (s[i + k] == s[sa[rk[i] - 1] + k]) ++k;
		ht[rk[i]] = k;
	}
	for (int i = n; i; --i) suf1[i] = suf1[i + 1] + sa[i], suf2[i] = suf2[i + 1] + ht[i];
}
inline int getl(int p, int len) {
	int l = 1, r = p;
	while (l < r) {
		int mid = l + r >> 1, v = mid == p ? len : st.query(mid + 1, p);
		v >= len ? r = mid : l = mid + 1;
	}
	return l;
}
inline ll rnk(int l, int r) {
	int L = getl(rk[l], r - l + 1);
	return (ll)(n - L + 1) * (n + 1) - suf1[L] - suf2[L + 1] - (r - l);
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> s + 1, n = strlen(s + 1);
	for (int i = 1; i <= n; ++i) cin >> val[i], pre[i] = pre[i - 1] + val[i];
	for (int i = 2; i <= n; ++i) lg2[i] = lg2[i >> 1] + 1;
	build(), st.init();
	for (int i = 1; i <= n; ++i) {
		int l = i, r = n;
		while (l < r) {
			int mid = l + r >> 1;
			pre[mid] - pre[i - 1] - rnk(i, mid) >= 0 ? r = mid: l = mid + 1;
		}
		if (pre[l] - pre[i - 1] == rnk(i, l)) ans[i] = l, ++sz;
	}
	cout << sz << '\n';
	for (int i = 1; i <= n; ++i) if (ans[i]) cout << i << ' ' << ans[i] << '\n';
	return 0;
}