题目链接

luogu P4688 [Ynoi2016]掉进兔子洞

题解

莫队维护bitset区间交个数

代码

// luogu-judger-enable-o2

#include<cmath>

#include<bitset>

#include<cstdio>

#include<cstring>

#include<algorithm>

inline int read() {

    int x = 0,f = 1;

    char c = getchar();

    while(c < '0' || c > '9') {if(c == '-')f = -1 ; c = getchar(); }

    while(c <= '9' && c >= '0') x = x * 10 + c - '0', c = getchar();

    return x * f;

}

const int whattt = 20001;

const int maxn = 100007;

int a[maxn],bel[maxn],b[maxn];

int l1[maxn],r1[maxn],l2[maxn],r2[maxn],l3[maxn],r3[maxn];

int sum[maxn];

int n,m,k;

struct Que {

    int l,r,id;

     Que(int l = 0,int r = 0,int id = 0) :l (l),r (r),id (id){};

     bool operator < (const Que & a) const {

            if(bel[l] == bel[a.l]) return r < a.r;

    		return bel[l] < bel[a.l];

    }

} q[33334 * 3 + 7];

std::bitset<100000> F[whattt + 7],f;

bool mark[33334 + 7];

int len;

int cnt[maxn],c[whattt * 3 + 7];

void update(int k,int ty) {

    k = a[k]; cnt[k] += ty;

    if(ty == 1) f[k + cnt[k] - 2] = 1;

    else f[k + cnt[k] - 1] = 0;

}

void solve() {

    memset(mark,0,sizeof mark);

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

    std::sort(q + 1,q + len + 1);

    int l = 1,r = 0;

    f.reset();

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

        while(r < q[i].r) update(++ r,1);

        while(r > q[i].r) update(r --,-1);

        while(l < q[i].l) update(l ++,-1);

        while(l > q[i].l) update(-- l,1);

        if(mark[q[i].id])F[q[i].id] &= f,c[q[i].id] = F[q[i].id].count();

        else F[q[i].id] = f,mark[q[i].id] = 1;

    }

}

int main() {

    //freopen("xp1.in","r",stdin);

    n = read(),m = read();

    k = sqrt(n);

    for(int i = 1;i <= n;++ i) b[i] = a[i] = read(),bel[i] = (i - 1) / k + 1;

    std::sort(b + 1,b + n +1);

    len = n;

    for(int i = 1;i <= n;++ i) a[i] = std::lower_bound(b + 1,b + len + 1,a[i]) - b;

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

        l1[i] = read(),r1[i] = read(),l2[i] = read(),r2[i] = read(),l3[i] = read(),r3[i] = read();

        sum[i] = r1[i] - l1[i] + 1 + r2[i] - l2[i] + 1 + r3[i] - l3[i] + 1;

    }

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

        len = 0;

        for(int j = i;j <= i + whattt - 1; ++ j) {

            if(j > m) break;

            q[++ len] = Que(l1[j],r1[j],j - i + 1);

            q[++ len] = Que(l2[j],r2[j],j - i + 1);

            q[++ len] = Que(l3[j],r3[j],j - i + 1);

        }

        solve();

        for(int j = i;j < i + whattt; ++ j) {

            if(j > m) break;

            printf("%d\n",sum[j] - 3 * c[j - i + 1]);

            //return 0;

        }

    }

    return 0;

}

luogu P4688 [Ynoi2016]掉进兔子洞 bitset 莫队的相关教程结束。