(莫队算法)

题意：

\(给出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
    
     #define LL long longusing 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
     
       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;}