【洛谷 P4688】 [Ynoi2016]掉进兔子洞（bitset，莫队）

题目链接

第一道Ynoi

显然每次询问的答案为三个区间的长度和减去公共数字个数*3.

如果是公共数字种数的话就能用莫队+bitset存每个区间的状态，然后3个区间按位与就行了。

但现在是个数，bitset中除了保存每个数是否出现外，还要保存出现的次数。

这时我们发现每个数字的出现次数之和\(=n\)

于是想到离散化以后每个数字占bitset中的一格。

还记得\(SA\)里的基数排序吗？这样就能使第\(n\)次加入区间的同一个数字有固定的位置安放。

于是就能莫队了。

但是一看数据范围，好像开不下\(1e5\)个长度为\(1e5\)的bitset啊。

没关系，把答案分成3组，一组一组来就行了。

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <bitset>

#include <cmath>

#include <iostream>

using namespace std;

const int MAXN = 100010;

const int MAXM = 34010;

bitset <MAXN> ans[MAXM], now;

int n, m, a[MAXN];

inline int read(){

    int s = 0;

    char ch = getchar();

    while(ch < '0' || ch > '9') ch = getchar();

    while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); }

    return s;

}

int Q;

struct lsh{

    int val, id;

    int operator < (const lsh A) const{

        return val < A.val;

    }

}p[MAXN];

struct ask{

    int l, r, id;

    int operator < (const ask A) const{

        return l / Q == A.l / Q ? r < A.r : l < A.l;

    }

}q[MAXM * 3];

int val[MAXN], cnt, sum[MAXN], v[MAXN], all, Ans[MAXM];

void work(){

    sort(q + 1, q + all + 1);

    now.reset();

    memset(v, 0, sizeof v);

    int l = 1, r = 1; now.set(val[1]); v[val[1]] = 1;

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

        while(r < q[i].r){ ++r; now.set(val[r] - v[val[r]]); ++v[val[r]]; }

        while(l > q[i].l){ --l; now.set(val[l] - v[val[l]]); ++v[val[l]]; }

        while(r > q[i].r){ --v[val[r]]; now.set(val[r] - v[val[r]], 0); --r; }

        while(l < q[i].l){ --v[val[l]]; now.set(val[l] - v[val[l]], 0); ++l; }

        ans[q[i].id] &= now;

    }

}

int main(){

    n = read(); m = read(); Q = sqrt(n);

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

        p[i].val = read(), p[i].id = i;

	for(int i = 1; i <= 33337; ++i)

	   ans[i].set();

    sort(p + 1, p + n + 1);

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

        if(p[i].val != p[i - 1].val)

            val[p[i].id] = ++cnt;

        else val[p[i].id] = cnt;

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

        ++sum[val[i]];

    for(int i = 1; i <= cnt; ++i)

        sum[i] += sum[i - 1];

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

    	val[i] = sum[val[i]];

    int o = m / 3;

    if(o){

        for(int qqc = 1; qqc <= 2; ++qqc){

            cnt = 0;

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

                q[++cnt].id = i; q[cnt].l = read(); q[cnt].r = read(); Ans[i] += q[cnt].r - q[cnt].l + 1;

                q[++cnt].id = i; q[cnt].l = read(); q[cnt].r = read(); Ans[i] += q[cnt].r - q[cnt].l + 1;

                q[++cnt].id = i; q[cnt].l = read(); q[cnt].r = read(); Ans[i] += q[cnt].r - q[cnt].l + 1;

            }

            all = o * 3; work();

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

                printf("%d\n", Ans[i] - int(ans[i].count()) * 3);

                Ans[i] = 0; ans[i].set();

            }

        }

    }

    m -= o * 2; cnt = 0;

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

        q[++cnt].id = i; q[cnt].l = read(); q[cnt].r = read(); Ans[i] += q[cnt].r - q[cnt].l + 1;

        q[++cnt].id = i; q[cnt].l = read(); q[cnt].r = read(); Ans[i] += q[cnt].r - q[cnt].l + 1;

        q[++cnt].id = i; q[cnt].l = read(); q[cnt].r = read(); Ans[i] += q[cnt].r - q[cnt].l + 1;

    }

    all = m * 3; work();

    for(int i = 1; i <= m; ++i)

        printf("%d\n", Ans[i] - int(ans[i].count()) * 3);

    return 0;

}

巴特西

【洛谷 P4688】 [Ynoi2016]掉进兔子洞（bitset，莫队）

最新文章

热门文章