ABC430

C. Truck Driver

二分或双指针
固定区间左端点 \(l\)，找到区间中至少有 \(A\) 个 a 的最小右端点 \(r_a\)，以及区间中至少有 \(B\) 个 \(b\) 的最小右端点 \(r_b\)。显然条件二更紧，所以用 \(r_b-r_a\) 来更新答案即可。
注意，\(r_b\) 可能在 \(r_a\) 的左边。

代码实现

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)using namespace std;
using ll = long long;int main() {int n, a, b;string s;cin >> n >> a >> b >> s;vector<int> sa(n+1), sb(n+1);rep(i, n) {if (s[i] == 'a') sa[i+1] = 1; else sb[i+1] = 1; }rep(i, n) sa[i+1] += sa[i];rep(i, n) sb[i+1] += sb[i];ll ans = 0;rep(l, n) {int ra, rb;{int wa = l, ac = n+1;while (abs(ac-wa) > 1) {int wj = (ac+wa)/2;if (sa[wj] - sa[l] >= a) ac = wj; else wa = wj;}ra = ac;}{int ac = l, wa = n+1;while (abs(ac-wa) > 1) {int wj = (ac+wa)/2;if (sb[wj] - sb[l] < b) ac = wj; else wa = wj;}rb = wa;}ans += max(0, rb-ra);}cout << ans << '\n';return 0;
}

D. Neighbor Distance

用一个 std::set 按位置维护当前出现的点 \((X_i, i)\)，并且维护每个已出现点的“到最近人的距离” dist[i]，和这些距离之和 ans。每插入一个新点，只会影响新点与它左右直接相邻的点，按增量更新即可 —— 因此每次插入 \(O(\log n)\)。

代码实现

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)using namespace std;
using ll = long long;
using P = pair<int, int>;int main() {int n;cin >> n;ll ans = 0;vector<int> dist(n+2);set<P> st;st.emplace(0, 0);st.emplace(2e9, n+1);dist[0] = 2e9; ans += 2e9;auto upd = [&](int i, int d) {ans -= dist[i];dist[i] = min(dist[i], d);ans += dist[i];};for (int i = 1; i <= n; ++i) {int x;cin >> x;auto it = st.emplace(x, i).first;int dprev = x - prev(it)->first;int dnext = next(it)->first - x;dist[i] = min(dprev, dnext);ans += dist[i];int pi = prev(it)->second;int ni = next(it)->second;upd(pi, dprev);upd(ni, dnext);cout << ans << '\n';}return 0;
}

E. Shift String

找 \(B\) 在 \(A+A\) 中第一次出现的起始下标
具体实现可以用哈希，\(Z\) 算法或 \(\text{kmp}\)

代码实现

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
#define rep(i, n) for (int i = 0; i < (n); ++i)using namespace std;void solve() {string a, b;cin >> a >> b;int n = a.size();vector<int> z = z_algorithm(b+"s"+a+a);rep(i, n) {if (z[n+1+i] == n) {cout << i << '\n';return;}}puts("-1");
}int main() {int t;cin >> t;while (t--) solve();return 0;
}

F. Back and Forth Filling

对每一个数，计算它最早能放到的格子和最晚能放到的格子，于是这个数能占据的格子的区间是一个闭区间 [最早, 最晚]。然后用差分就能求出每个格子中能填多少种数了。
先预处理出 \(4\) 个数组：

• ll[i]：表示 \(i\) 左边紧跟着的连续的 L 的个数
• lr[i]：表示 \(i\) 左边紧跟着的连续的 R 的个数
• rl[i]：表示从 \(i\) 开始向右的连续的 L 的个数
• rr[i]：表示从 \(i\) 开始向右的连续的 R 的个数

最早 \(= \text{lr}[i]+\text{rl}[i]\)，有连续的 \(\text{ll}[i]+\text{rr}[i]\) 个数要填在 \(i\) 的左边
最晚 \(= N-1-(\text{ll}[i]+\text{rr}[i])\)，有连续的 \(\text{ll}[i]+\text{rr}[i]\) 个数要填在 \(i\) 的右边

代码实现

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)using namespace std;void solve() {int n;string s;cin >> n >> s;vector<int> ll(n), lr(n);vector<int> rl(n), rr(n);rep(i, n-1) if (s[i] == 'L') ll[i+1] = ll[i]+1;rep(i, n-1) if (s[i] == 'R') lr[i+1] = lr[i]+1;for (int i = n-2; i >= 0; --i) {if (s[i] == 'L') rl[i] = rl[i+1]+1; else rr[i] = rr[i+1]+1;}vector<int> d(n+1);rep(i, n) {int s = lr[i]+rl[i], t = ll[i]+rr[i];d[s]++; d[n-t]--;}rep(i, n) d[i+1] += d[i];rep(i, n) cout << d[i] << " \n"[i == n-1];
}int main() {int t;cin >> t;while (t--) solve();return 0;
}

G. Range Set Modifying Query

线段树beats