Codeforces 877F Ann and Books 莫队

时间：2023-03-09 23:43:40
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 + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + ;

const double eps = 1e-;

const int B = ;

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 = ; i <= n; i++) scanf("%d", &t[i]);

    for(int i = ; i <= n; i++) {

        scanf("%d", &a[i]);

        if(t[i] == ) a[i] = a[i - ] + a[i];

        else a[i] = a[i - ] - a[i];

        hs[tot++] = a[i];

    }

    hs[tot++] = ;

    sort(hs, hs + tot);

    tot = unique(hs, hs + tot) - hs;

    for(int i = ; i <= n; i++) a[i] = lower_bound(hs, hs + tot, a[i]) - hs;

    for(int i = , p; i < tot; i++) {

        after[i] = befor[i] = -;

        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 = ; i <= q; i++) {

        scanf("%d%d", &qus[i].L, &qus[i].R);

        qus[i].id = i; qus[i].L--;

    }

    sort(qus + , qus +  + q);

    l = , r = -;

    for(int i = ; i <= q; i++) {

        int L = qus[i].L, R = qus[i].R, id = qus[i].id;

        while(r < R) r++, val += befor[a[r]] == - ?  : cnt[befor[a[r]]], cnt[a[r]]++;

        while(l > L) l--, val += after[a[l]] == - ?  : cnt[after[a[l]]], cnt[a[l]]++;

        while(r > R) cnt[a[r]]--, val -= befor[a[r]] == - ?  : cnt[befor[a[r]]], r--;

        while(l < L) cnt[a[l]]--, val -= after[a[l]] == - ?  : cnt[after[a[l]]], l++;

        ans[id] = val;

    }

    for(int i = ; i <= q; i++) printf("%lld\n", ans[i]);

    puts("");

    return ;

}

/*

*/

相关文章