permu 莫队 总结
2024-09-01 11:17:55
由于每次询问静态区间里完整值域段的最大大小
貌似很好用莫队转移，所以考虑怎么转移
当给它扩展一个数时，就是给值域添加了一个值
这个值可能已经存在，也可能是新的
有的神仙做法是维护了一个并查集,然而我这码力..
所以我用了一个更加初级的操作，给每个点打上向左连续最远和向右连续最远的标记
添加一个新点时，同时更新它的向左连续最远和向右连续最远的值的标记
这是添加，删除呢
目前来看，如果不记录每个点的影响及其所有后续影响及其影响前的状态，删除操作就算萎了
所以要尽量不删除
可以知道莫队有个性质，在同一个左端点分块里，右端点具有单调性
虽然左端点没单调性，但他们的范围限制在一个很小的区间里（根号N的分块里）
而且对于每个左端点分块，跑一遍O（N）的操作是没问题的
如果只想添加，不想删除的话..
每次换个分块就把计数清空，把左右端点放在分块的右端点，记录此状态state
每次拓展右边，更新state
每次拓展左边，记录拓展前的state，拓展后恢复state
这样保证了每个询问至多有个根号N复杂度的左记录和恢复
每个分块至多有个O（N）的清空
复杂度变成了O（N√N）.
最新文章
- swift与OC之间不得不知道的21点
- 1 Maximum Product Subarray_Leetcode
- 跟我学Windows Azure 四 Cloud Service中的WebRole与WorkRole，及他们之间的通信
- vuejs动态组件给子组件传递数据
- 一次简单的MySQL数据库导入备份
- Nginx图片剪裁模块探究 http_image_filter_module
- 网络工程实训_2路由器基本配置及IOS介绍
- Windows服务调用Quartz.net 实现消息调度
- 修改NGINX版本名称为任意WEB SERVER
- 研究了下apache的漏洞CVE-2012-0053
- django FileFIeld和ImageField 上传路径改写
- Spring MVC 中采用注解方式 Action中跳转到另一个Action的写法
- 图片上传插件用法,net语法【二】
- iOS Plugins
- ASP.NET core1.0 EF MYSQL搭建中碰到几个问题记录
- Spring学习之路三——第一个Spring程序（体会IoC）
- Nginx的内部(进程)模型
- Business Intelligence Tools We Recommend 1/4 – Metabase
- [vue开发记录]全局loading组件
- jq的遍历关系元素方法集合