Codeforces 877F Ann and Books 莫队

转换成前缀和， 预处理一下然后莫队。

#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ull unsigned long long
using namespace std;

const int N = 2e5 + 7;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-8;

const int B = 300;

struct Qus {
    int L, R, id;
    bool operator < (const Qus& rhs) const {
        if(L / B == rhs.L / B) return R < rhs.R;
        return L / B < rhs.L / B;
    }
} qus[N];

int n, k, q, l, r, tot, t[N];
int after[N], befor[N], cnt[N];
LL ans[N], a[N], hs[N], val;

int main() {
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++) scanf("%d", &t[i]);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        if(t[i] == 1) a[i] = a[i - 1] + a[i];
        else a[i] = a[i - 1] - a[i];
        hs[tot++] = a[i];
    }
    hs[tot++] = 0;
    sort(hs, hs + tot);
    tot = unique(hs, hs + tot) - hs;
    for(int i = 0; i <= n; i++) a[i] = lower_bound(hs, hs + tot, a[i]) - hs;
    for(int i = 0, p; i < tot; i++) {
        after[i] = befor[i] = -1;
        p = lower_bound(hs, hs + tot, hs[i] + k) - hs;
        if(p < n && hs[p] == hs[i] + k) after[i] = p;
        p = lower_bound(hs, hs + tot, hs[i] - k) - hs;
        if(p < n && hs[p] == hs[i] - k) befor[i] = p;
    }
    scanf("%d", &q);
    for(int i = 1; i <= q; i++) {
        scanf("%d%d", &qus[i].L, &qus[i].R);
        qus[i].id = i; qus[i].L--;
    }
    sort(qus + 1, qus + 1 + q);
    l = 0, r = -1;
    for(int i = 1; i <= q; i++) {
        int L = qus[i].L, R = qus[i].R, id = qus[i].id;
        while(r < R) r++, val += befor[a[r]] == -1 ? 0 : cnt[befor[a[r]]], cnt[a[r]]++;
        while(l > L) l--, val += after[a[l]] == -1 ? 0 : cnt[after[a[l]]], cnt[a[l]]++;
        while(r > R) cnt[a[r]]--, val -= befor[a[r]] == -1 ? 0 : cnt[befor[a[r]]], r--;
        while(l < L) cnt[a[l]]--, val -= after[a[l]] == -1 ? 0 : cnt[after[a[l]]], l++;
        ans[id] = val;
    }
    for(int i = 1; i <= q; i++) printf("%lld
", ans[i]);
    puts("");
    return 0;
}
/*
*/