为了练习分块 莫队 bitset黑科技 我会写几道Ynoi 放到这里。
LINK:luogu4688掉进兔子洞
我挑了一道最简单的莫队+bitset的题目 题目中说三个区间每次都要同时删掉一个数字问最后剩下的数字个数和.
n,m都是1e5.我们直接考虑莫队找区间 然后考虑找到区间之后如何快速的维护上述操作。
发现如果数字都不相同我们直接bitset来做 最后是集合大小之和 - 3*|S|.
但是如果数字相同怎么办 这里有一个小trick我们离散化的时候把相同的数字离散成不同的。
加入的时候如果加的是某个数字 这个数字出现多次我们就给bitset上对应的那个位置变成1.
这样我们就解决了数字相同的问题了。
最后 还有一个trick 1e5个大小为1e5的bitset我们是开不下的所以要进行分块回答。
大概分上3,4块以至于空间可以开下即可 这个浪费不了多少时间。
复杂度 莫队msqrt(n)+mn/64.应该可以勉强卡过。
相关文章
- 03-17LeetCode练题——122. Best Time to Buy and Sell Stock II
- 03-172021年CS保研经历(三):清华大学自动化学院大数据专硕预推免
- 03-17随手练——C语言网-1096: Minesweeper
- 03-17[Luogu P5068][Ynoi2015]我回来了
- 03-17Windows API一日一练 4 MessageBox函数
- 03-17BZOJ 4939: [Ynoi2016]掉进兔子洞(莫队+bitset)
- 03-17Ynoi专练
- 03-17每日一练(7):旋转数组的最小数字
- 03-17P5048-[Ynoi2019 模拟赛]Yuno loves sqrt technology III【分块】
- 03-17[Ynoi2019 模拟赛] Yuno loves sqrt technology III