题解 | #1or0#

nc周赛的E题已经开始出莫队了，有点小吃惊。

幸好是个简单的无回滚无持久化非树上莫队，但是也需要仔细推一下。

看到m次区间查询，无非线段树或者莫队。看起来线段树不可行（因为没有明确的合并性质）

那么看看从区间的一端向推时是否有的性质：

假设我们有字符串为例，假如当前，则取到时，每次都是增加一系列以为右端点的字符串，因此答案增量是以位置在5的0结尾的字符串，而不行。

由于or的性质，每次增量取到的字符串分两种情况分析，当时，所有字符串都是新的解；当时，有贡献的字符串的左端点可以从l一直取到r前面的最后一个1。这个操作可以预处理完成。

而且这个推理是可以反过来删除的，因此可以用莫队。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

const int N = 200020;
int a[N], blk[N];
int n, m;
int pre[N], nxt[N];
ll ans[N], now;
struct Query {
    int l, r, i;
};
int sz;
Query q[N];

void addr(int l, int r) {
    if (a[r] == 1)
        now += ll(r - l + 1);
    else {
        int i = pre[r];
        if (i >= l)
            now += ll(i - l + 1);
    }
}

void remr(int l, int r) {
    if (a[r] == 1)
        now -= ll(r - l + 1);
    else {
        int i = pre[r];
        if (i >= l)
            now -= ll(i - l + 1);
    }
}

void addl(int l, int r) {
    if (a[l] == 1)
        now += ll(r - l + 1);
    else {
        int i = nxt[l];
        if (i <= r)
            now += ll(r - i + 1);
    }
}

void reml(int l, int r) {
    if (a[l] == 1)
        now -= ll(r - l + 1);
    else {
        int i = nxt[l];
        if (i <= r)
            now -= ll(r - i + 1);
    }
}


int main(){
    //freopen("in.txt", "r", stdin);
    scanf("%d", &n);
    char ts[200020];
    scanf("%s", ts);
    sz = sqrt(n);
    for (int i = 1; i <= n; ++i) {
        a[i] = ts[i - 1] - '0';
    }
    for (int i = 1; i <= n; ++i) {
        blk[i] = i / sz;
    }
    int t = 0;
    for (int i = 1; i <= n; ++i) {
        pre[i] = t;
        if (a[i] == 1) {
            t = i;
        }
    }
    t = n + 1;
    for (int i = n; i >= 1; --i) {
        nxt[i] = t;
        if (a[i] == 1) {
            t = i;
        }
    }
    scanf("%d", &m);
    for (int i = 0; i < m; ++i) {
        int l, r;
        scanf("%d%d", &l, &r);
        q[i] = { l, r, i };
    }
    sort(q, q + m, [&](Query x, Query y) {
        if (blk[x.l] == blk[y.l]) {
            return blk[x.l] & 1 ? x.r > y.r : x.r < y.r;
        }
        else return blk[x.l] < blk[y.l];
        });
    int R = 0, L = 1;
    for (int i = 0; i < m; ++i) {
        auto [l, r, idx] = q[i];
        while (R < r) {
            ++R;
            addr(L, R);
        }
        while (L > l) {
            --L;
            addl(L, R);
        }
        while (R > r) {
            remr(L, R);
            --R;
        } 
        while (L < l) {
            reml(L, R);
            ++L;
        }
        ans[idx] = now;
    }
    for (int i = 0; i < m; ++i) {
        printf("%lld\n", ans[i]);
    }
    return 0;
}