LOJ #6499. 「雅礼集训 2018 Day2」颜色
2022/2/12 23:48:08
本文主要是介绍LOJ #6499. 「雅礼集训 2018 Day2」颜色,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
突然想起来这个题,作为总结写个题解。
考虑这个问题比区间数颜色强很多,那么要不然就离线,要不然在线考虑非 polylog 的做法。
颜色数信息比较难合并,考虑用 bitset 来记录颜色,合并就是 bitset 的按位或。
在线做法:四毛子,分成 \(w\) 个块以及它们的颜色 bitset,然后用 ST 表预处理出块的区间 bitset。询问的时候整块直接查 ST 表,散块暴力扫,时间复杂度 \(\mathcal{O}(\frac{nm}{w})\).
离线做法:用莫队把询问的区间的 bitset 扫出来,最后再合并,时间复杂度 \(\mathcal{O}(n\sqrt m+\frac{nm}{w})=\mathcal{O}(\frac{nm}{w})\).
注意空间问题,由于卡空间后者应该过不了。
在线做法:
#include<iostream> #include<cstdio> #include<bitset> #include<cmath> template <typename T> T Min(T x, T y) { return x < y ? x : y; } template <typename T> T Max(T x, T y) { return x > y ? x : y; } template <typename T> T &read(T &r) { r = 0; bool w = 0; char ch = getchar(); while(ch < '0' || ch > '9') w = ch == '-' ? 1 : 0, ch = getchar(); while(ch >= '0' && ch <= '9') r = r * 10 + (ch ^ 48), ch = getchar(); return r = w ? -r : r; } const int N = 100001; const int w = 64; int n, m, p, a[N], _lg[N], lst; int blo, bl[N]; std::bitset<100001>st[7][w+1], now; void calc(int l, int r) { for(int i = l; i <= r; ++i) now[a[i]] = 1; } int main() { read(n); read(m); read(p); blo = std::ceil(1.0 * n / w); for(int i = 1; i <= n; ++i) { read(a[i]); _lg[i] = _lg[i-1] + ((1 << _lg[i-1]) == i ? 1 : 0); bl[i] = (i - 1) / blo + 1; st[0][bl[i]][a[i]] = 1; } for(int i = 1; i <= n; ++i) --_lg[i]; for(int i = 1; i <= 6; ++i) for(int j = 1; j <= w && j + (1 << i) - 1 <= w; ++j) st[i][j] = st[i-1][j] | st[i-1][j+(1<<(i-1))]; for(int i = 1, k, l, r; i <= m; ++i) { now.reset(); read(k); for(int j = 1; j <= k; ++j) { read(l); read(r); if(p && i != 1) l = (l ^ lst) % n + 1, r = (r ^ lst) % n + 1; if(l > r) std::swap(l, r); if(bl[l] == bl[r]) calc(l, r); else { int cl = bl[l], cr = bl[r]; if(l != bl[l] * blo - blo + 1) calc(l, bl[l] * blo), ++cl; if(r != bl[r] * blo) calc(bl[r] * blo - blo + 1, r), --cr; if(cl > cr) continue; int t = _lg[cr - cl + 1]; now |= st[t][cl] | st[t][cr-(1<<t)+1]; } } lst = now.count(); printf("%d\n", lst); } return 0; }
这篇关于LOJ #6499. 「雅礼集训 2018 Day2」颜色的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?