Codeforces #442 Div2 F

#442 Div2 F

题意

给出一些包含两种类型（a, b）问题的问题册，每本问题册有一些题目，每次查询某一区间，问有多少子区间中 a 问题的数量等于 b 问题的数量加 \(k\) 。

分析

令包含 a 问题的问题册的问题数取正值，包含 b 问题的问题册的问题数取负值，那么问题就是求有多少子区间的和为 \(k\) 。

先求前缀和，记录 \(i\) 出现的次数 \(cnt[i]\)。当计算完前缀和 \(b[i-1]\) 后，考虑前缀和 \(b[i]\) ，\(cnt[b[i]-k]\)为对答案的贡献。

对于这种多个区间的询问，且区间从 \([L,R]\) 到 \([L,R+1]\) 或 \([L-1,R]\) 只需要 \(O(1)\) 的复杂度时，可以用莫队算法去优化，离线 + 分块。

注意，并不能直接用数组去存 \(cnt\) ，用 \(map\) 也会超时，这里可以离散化掉所有可能的值，因为我们只关心某种数字出现的次数。

code

#include<bits/stdc++.h>

typedef long long ll;

using namespace std;

const int MAXN = 1e5 + 10;

const int BLOCK = 300;

int n, k;

ll a[MAXN], b[MAXN];

ll s[MAXN << 2];

int x[MAXN], y[MAXN], z[MAXN];

ll O[MAXN << 2];

struct P {

    int l, r, b, i;

    bool operator < (const P& o) const {

        if(b != o.b) return b < o.b;

        return r < o.r;

    }

}p[MAXN];

ll ans[MAXN];

int main() {

    scanf("%d%d", &n, &k);

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

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

        if(a[i] != 1) a[i] = -1;

    }

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

        scanf("%lld", &b[i]);

        if(!i) b[i] = a[i] * b[i];

        else b[i] = b[i - 1] + a[i] * b[i];

    }

    int c = 0;

    b[n] = 0;

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

        s[c++] = b[i];

        s[c++] = b[i] + k;

        s[c++] = b[i] - k;

    }

    sort(s, s + c);

    int cc = unique(s, s + c) - s;

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

        x[i] = lower_bound(s, s + cc, b[i] - k) - s;

        y[i] = lower_bound(s, s + cc, b[i]) - s;

        z[i] = lower_bound(s, s + cc, b[i] + k) - s;

    }

    int q;

    scanf("%d", &q);

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

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

        p[i].l--;

        p[i].r--;

        p[i].b = p[i].l / BLOCK;

        p[i].i = i;

    }

    sort(p, p + q);

    int L = 0, R = 0;

    ll res = 0;

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

        int l = p[i].l, r = p[i].r;

        if(!i) {

            if(l == 0) O[y[n]]++;

            else O[y[l - 1]]++;

            for(int j = l; j <= r; j++) {

                res += O[x[j]];

                O[y[j]]++;

            }

        } else {

            for(int j = R + 1; j <= r; j++) {

                res += O[x[j]];

                O[y[j]]++;

            }

            for(int j = L - 1; j >= l; j--) {

                if(j == 0) { res += O[z[n]]; O[y[n]]++; }

                else { res += O[z[j - 1]]; O[y[j - 1]]++; }

            }

            for(int j = R; j > r; j--) {

                O[y[j]]--;

                res -= O[x[j]];

            }

            for(int j = L; j < l; j++) {

                if(j == 0) { O[y[n]]--; res -= O[z[n]]; }

                else { O[y[j - 1]]--; res -= O[z[j - 1]]; }

            }

        }

        L = l;

        R = r;

        ans[p[i].i] = res;

    }

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

    return 0;

}

巴特西

Codeforces #442 Div2 F

#442 Div2 F

题意

分析

code

最新文章

热门文章