题解 | 1or0

#include <iostream>
using namespace std;

//类似前缀和
int main() {
    int n;
    cin >> n;
    string str;
    cin >> str;
    long long ans[200005] = {};

    int tmp;
    if (str[0] == '0') {
        ans[0] = 0;
        tmp = 1;
    } else {
        ans[0] = 1;
        tmp = 0;
    }

    for (int i = 1; i < str.length(); i++) {
        if (str[i] == '0') {
            ans[i] = ans[i - 1] + i - tmp;
            tmp += 1;
        } else {
            ans[i] = ans[i - 1] + i + 1;
            tmp = 0;
        }
    }

    int loc_l1[200005] = {}, l1 = -1;
    for (int i = 0; i < str.length(); i++) {
        if (str[i] == '1') {
            l1 = i;
            loc_l1[i] = l1;
        } else {
            loc_l1[i] = l1;
        }
    }

    int loc_r1[200005] = {}, r1 = -1;
    for (int i = str.length() - 1; i >= 0; i--) {
        if (str[i] == '1') {
            r1 = i;
            loc_r1[i] = r1;
        } else {
            loc_r1[i] = r1;
        }
    }

    int q;
    cin >> q;
    int l, r, k1, k2;
    long long res = 0;
    for (int i = 0; i < q; i++) {
        cin >> l >> r;
        if (l == 1) {
            cout << ans[r - 1] << endl;
            continue;
        } else if (l == r) {
            cout << str[l - 1] << endl;
            continue;
        } else {
            if (str[l - 1] == '1') {
                cout << ans[r - 1] - ans[l - 2] - (long long)(l - 1) * (long long)(
                         r - l + 1) << endl;
                continue;
            } else {
                k1 = loc_l1[l - 1];
                k2 = loc_r1[l - 1];
                
                res = ans[r - 1] - ans[l - 2];
                if (k1 != -1) {
                    res = res - (long long)(k1 + 1) * (long long)(r - l + 1);
                }
                if (k2 != -1 && k2 <= r - 1) {
                    res = res - (long long)(r - k2) * (long long)(l - 1);
                }
                if (k1 != -1 && k2 != -1 && k2 <= r - 1) {
                    res = res + (long long)(k1 + 1) * (long long)(r - k2);
                }
                cout << res << endl;
                continue;
            }
        }
    }
}
// 64 位输出请用 printf("%lld")