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