HihoCoder#1513 : 小Hi的烦恼(五维数点 bitset 分块)

题意

题目链接

Sol

五位数点问题，写个cdq分治套cdq分治套cdq分治套cdq分析就完了可以用bitset搞

对于每一科开\(n\)个bitset，其中\(b[i]\)表示的排名为\(1 - i\)的人是哪些

查询的时候把每科的bitset &起来就行了

复杂度\(k\frac{n^2}{32}\)

然后可以分块加速一下

注意这里在预处理有个关于势能分析的操作：如果块内元素较少的话，可以每次跑根号个，然后和前面的|起来，如果元素较多的话直接从1开始跑

复杂度：\(k\frac{n\sqrt(n)}{32}\)

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 30001;

inline int read() {

    int x = 0, f = 1; char c = getchar();

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

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

    return x * f;

}

int N, a[5][MAXN], rak[5][MAXN], base = 1;

bitset<MAXN> B[5][175];

main() {

    N = read(); base = sqrt(N);

    for (int i = 1; i <= N; i++) for (int j = 0; j < 5; j++) a[j][i] = read(), rak[j][a[j][i]] = i;

    for (int j = 0; j < 5; j++)

        for (int i = 1; i * base <= N; i++)

            for(int k = 1; k <= i * base; k++) B[j][i].set(rak[j][k]);

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

        bitset<MAXN> tmp, cal; tmp.set();

        for(int j = 0; j < 5; j++) {

            cal.reset();

            int now = a[j][i] / base;

            cal |= B[j][now];

            for(int k = now * base + 1; k <= a[j][i]; k++) cal.set(rak[j][k]);

            tmp &= cal;

        }

        printf("%d\n", tmp.count() - 1);

    }

}

巴特西

HihoCoder#1513 : 小Hi的烦恼(五维数点 bitset 分块)

题意

Sol

最新文章

热门文章