HihoCoder#1513 : 小Hi的烦恼(五维数点 bitset 分块)
发布时间:2020-12-14 04:19:36 所属栏目:大数据 来源:网络整理
导读:题意 题目链接 Sol 五位数点问题, 写个cdq分治套cdq分治套cdq分治套cdq分析就完了 可以用bitset搞 对于每一科开 (n) 个bitset,其中 (b[i]) 表示的排名为 (1 - i) 的人是哪些 查询的时候把每科的bitset 起来就行了 复杂度 (kfrac{n^2}{32}) 然后可
题意题目链接 Sol五位数点问题, 对于每一科开(n)个bitset,其中(b[i])表示的排名为(1 - i)的人是哪些 查询的时候把每科的bitset &起来就行了 复杂度(kfrac{n^2}{32}) 然后可以分块加速一下 注意这里在预处理有个关于势能分析的操作:如果块内元素较少的话,可以每次跑根号个,然后和前面的|起来,如果元素较多的话直接从1开始跑 复杂度:(kfrac{nsqrt(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("%dn",tmp.count() - 1); } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |