TIOJ 2348：F. 守護魔摩市

TIOJ 2348：F. 守護魔摩市

題目大意：連結

解法：用倍增，存每個時間魔力值是 $A$，忍耐值是 $0$ 時，下一個人在哪，還有下一個魔力值 $A$、忍耐值 $0$ 的時間，還有之間 $f$ 的總和。每次詢問用建好的倍增算答案。

$\text{Code：}$

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 5e5 + 5;
const int H = __lg(N);

int n, q, A, B;
string s;
int R[N];
ll ans, sum[H + 1][N];
pair<int, int> to[H + 1][N];

inline ll cal(int l, int r) {
    return l <= r ? 1ll * (l + r) * (r - l + 1) / 2 : 0;
}
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> q >> A >> B;
    cin >> s, s = " " + s;
    R[n + 1] = n + 1;
    for (int i = n; i >= 1; i--) {
        R[i] = R[i + 1];
        if (s[i] == '1') R[i] = i;
    }
    to[0][n + 1] = {n + 1, n + 1};
    for (int i = 1; i <= n; i++) {
        auto &[x, y] = to[0][i];
        y = R[i + 1];
        if (y > n) x = y;
        else if (i + B >= y) {
            x = y;
            sum[0][i] = 1ll * A * (y - i);
        } else if (i + A + B >= y) {
            int len = y - i - B;
            x = min(n + 1, i + B + 2 * len);
            sum[0][i] = 1ll * A * B + cal(A - len, A) + cal(A - len + 1, A - 1);
        } else {
            x = min(n + 1, y + A);
            sum[0][i] = 1ll * A * (A + B);
        }
    }
    for (int i = 1; i <= H; i++) for (int j = 1; j <= n + 1; j++) {
        auto &[nx, ny] = to[i - 1][j];
        to[i][j] = to[i - 1][nx];
        sum[i][j] = sum[i - 1][j] + sum[i - 1][nx];
    }
    while (q--) {
        int l, r, pos;
        cin >> l >> r;
        pos = R[l];
        if (pos > r) {
            cout << "0\n";
            continue;
        }
        ans = cal(0, A - 1);
        pos = min(pos + A, n + 1);
        for (int i = H; i >= 0; i--) if (to[i][pos].second <= r) {
            ans += sum[i][pos];
            pos = to[i][pos].first;
        }
        ans += 1ll * A * B + cal(0, A);
        cout << ans << '\n';
    }
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！