cf 442 div2 F. Ann and Books(莫队算法)

题意：

\(给出n和k,和a_i,sum_i表示前i个数的和,有q个查询[l,r]\)

每次查询区间\([l,r]内有多少对(i,j)满足l <= i <= j <= r 且 sum[j] - sum[i-1] = k\)

思路:

区间左右端点的挪动对答案的贡献符合加减性质，直接用莫队算法即可

复杂度\(O(n * sqrt(n) * log(maxsum))\) 过高

考虑先离散化预处理出所有位置 将\(log\)去掉

#include<bits/stdc++.h>

#define LL long long

using namespace std;

const int N = 2e5 + 10;

struct Q{

    int l,r,bl,id;

    Q(){};

    bool operator<(const Q&rhs){

         if(bl == rhs.bl) return r < rhs.r;

         return bl < rhs.bl;

    }

}qr[N];

int n,k;

LL ans[N],value[N];

int x[N],y[N],z[N],cnt[N * 3],type[N];

vector<LL> se;

int main(){

    while(cin>>n>>k){

        memset(cnt, 0, sizeof(cnt));

        se.clear();

        for(int i = 1;i <= n;i++) scanf("%d",&type[i]);

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

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

            if(type[i] == 1) value[i] += value[i-1];

            else value[i] = value[i-1] - value[i];

        }

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

            se.push_back(value[i]);

            se.push_back(value[i] + k);

            se.push_back(value[i] - k);

        }

        sort(se.begin(), se.end());

        se.erase(unique(se.begin(),se.end()),se.end());

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

            x[i] = lower_bound(se.begin(),se.end(),value[i]) - se.begin();

            y[i] = lower_bound(se.begin(),se.end(),value[i] + k) - se.begin();

            z[i] = lower_bound(se.begin(),se.end(),value[i] - k) - se.begin();

        }

        int block_size = sqrt(n + 0.5);

        int q;

        cin>>q;

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

            scanf("%d%d",&qr[i].l,&qr[i].r);

            qr[i].id = i;

            qr[i].l--;

            qr[i].bl = qr[i].l / block_size;

        }

        sort(qr, qr + q);

        int L = 0,R = -1;

        LL res = 0;

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

                while(qr[i].l > L) {

                    cnt[x[L]]--;

                    res -= cnt[y[L++]];

                }

                while(qr[i].l < L) {

                    res += cnt[y[--L]];

                    cnt[x[L]]++;

                }

                while(qr[i].r > R){

                    res += cnt[z[++R]];

                    cnt[x[R]]++;

                }

                while(qr[i].r < R) {

                    cnt[x[R]]--;

                    res -= cnt[z[R--]];

                }

            ans[qr[i].id] = res;

        }

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

    }

    return 0;

}

cf 442 div2 F. Ann and Books(莫队算法)的相关教程结束。