Ynoi专练
2024-10-09 10:27:18
为了练习分块 莫队 bitset黑科技 我会写几道Ynoi 放到这里。
bitset 每一位占1bit int 每一位占 4 bitye bool占1 bitye long long 8bitye
LINK:luogu4688掉进兔子洞
我挑了一道最简单的莫队+bitset的题目 题目中说三个区间每次都要同时删掉一个数字问最后剩下的数字个数和.
n,m都是1e5.我们直接考虑莫队找区间 然后考虑找到区间之后如何快速的维护上述操作。
发现如果数字都不相同我们直接bitset来做 最后是集合大小之和 - 3*|S|.
但是如果数字相同怎么办 这里有一个小trick我们离散化的时候把相同的数字离散成不同的。
加入的时候如果加的是某个数字 这个数字出现多次我们就给bitset上对应的那个位置变成1.
这样我们就解决了数字相同的问题了。
最后 还有一个trick 1e5个大小为1e5的bitset我们是开不下的所以要进行分块回答。
大概分上2,3块以至于空间可以开下即可 这个浪费不了多少时间。
复杂度 莫队msqrt(n)+mn/64.应该可以勉强卡过。
最新文章
- FFmpeg滤镜实现区域视频增强 及 D3D实现视频播放区的拉大缩小
- JavaScript和html5 canvas生成圆形印章
- Shader Model 3.0:Using Vertex Textures SM3:使用顶点纹理 (NVIDIA spec, 6800支持使用D3DFMT_R32F and D3DFMT_A32B32G32R32F的纹理格式实现Vertex Texture。)
- K2十年:专注BPM
- 自定义的UITabbar上面的按钮的x坐标的计算方法
- Document Set 【一】
- UVA 12382 Grid of Lamps 贪心
- C# : 操作Word文件的API - (将C# source中的xml注释转换成word文档)
- ASP.NET MVC+EF框架+EasyUI实现权限管理系列(16)-类库架构扩展以及DLL文件生成修改和用户的简单添加
- 整理JRE瘦身或精简JRE
- SpringMVC 集成velocity
- FineUIMvc随笔(6)对比WebForms和MVC中表格的数据库分页
- CentOS升级Python2.7导致使用pip等命令安装模块失败
- 8.javaweb之session
- SQL 收缩日志
- Python内置模块之random
- “2014年CityEngine三维建模与设计精英培训班”——全国巡回举办
- Java_myBatis入门写法
- Ubuntu 14.04 vi 退格键不能删除字符
- 分布式部署下的报表调用 API调用 权限问题以及性能方案
热门文章
- 什么是DevOps?该如何正确的在企业内进行实践
- pycharm连接远程服务器(拉取版本)
- Django---进阶14
- C#foreach原理
- python实现二维码、条形码识别
- 从 (a==1&;&;a==2&;&;a==3) 成立中看javascript的隐式类型转换
- It is indirectly referenced from required .class files错误查找的解决办法如下
- ModuleNotFoundError: No module named 'phkit.pinyin'
- ResNeXt论文阅读笔记.md
- JAVA I/O基本操作