题解：AT_abc430_f [ABC430F] Back and Forth Filling

残阳如血 · 2025-12-04 14:28:23 · 题解

对于这种限制比较宽松的计数题首先考虑图论建模。

令边 u\to v 表示 u 在 v 的左边，那么字符串就可以转化为 n-1 条边，得到一张链状的图。

考虑记录每个点的前驱数量 \text{pre}_u 和 \text{nxt}_u，那么 u 可以填的位置为 [\text{pre}_u+1,n-\text{nxt}_u]，也就对这个答案区间产生 1 的贡献。这个是可以使用差分轻松维护的。

考虑如何求前驱后继。先转化为就前驱。对于链状的 DAG 父亲贡献是可以直接相加的，直接做就完了。

时间复杂度 O(n+m)，AC Link。