HihoCoder#1513 : 小Hi的烦恼(五维数点 bitset 分块)
程序员文章站
2022-07-08 19:59:48
题意 "题目链接" Sol 五位数点问题,~~写个cdq分治套cdq分治套cdq分治套cdq分析就完了~~ 可以用bitset搞 对于每一科开$n$个bitset,其中$b[i]$表示的排名为$1 i$的人是哪些 查询的时候把每科的bitset &起来就行了 复杂度$k\frac{n^2}{32}$ ......
题意
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); } }