当前位置: 首页 > news >正文

题解:Luogu P4143 采集矿石

题意

给定长度为 \(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;
}
http://www.hskmm.com/?act=detail&tid=35335

相关文章:

  • 从18w到1600w播放量,我的一点思考。
  • 扣一个细节问题
  • 10.20java作业
  • 题解:Luogu P14175 【MX-X23-T5】向死存魏
  • 题解:Luogu P14254 分割(divide)
  • 题解:Luogu P6898 [ICPC 2014 WF] Metal Processing Plant
  • 20251020
  • 32-腾讯IM接入资料和定价
  • 题解:AtCoder ARC207A Affinity for Artifacts
  • 构造单
  • [笔记]高斯消元
  • 半导体设备各细分领域的国内外龙头公司
  • CSP-S 34
  • 02.Python百行代码实现抽奖系统
  • CSP-S 35
  • CSP-S 29
  • 2025网络安全振兴杯wp
  • 10.20每日总结
  • CSP-S 31
  • 后缀树
  • ES原理、zookeeper、kafka
  • CF1606E Arena 题解(动态规划)
  • 服务器CPU市场概况2025
  • CSP-S 24
  • 读书笔记:深入理解java虚拟机
  • CSP-S 19
  • CSP-S 20
  • Flutter应用设置插件 - 轻松打开iOS和Android系统设置
  • CSP-S 22
  • Project. 2025.11化学小组pre