首页 > 编程语言 >【学习笔记】根号算法

【学习笔记】根号算法

时间:2023-06-06 09:13:28浏览次数:88  
标签:分块 复杂度 笔记 算法 sqrt 区间 莫队 根号 指针

分块

经典操作

暴力思想

先考虑最暴力的做法如何实现。

平衡思想

设长度 \(n\),块长 \(B\)。

多数是定一个块长,使整块与散块、查询与修改的复杂度近似相等,并分别考虑整块好散块的情况。

暴力重构

指对散块处理时如果会破坏一个块的既有标记等等,可以选择暴力重新构建当前的标记。

复杂度分析

根据一次操作最多涉及两个散块,以及操作本身的性质,可以得到低于纸面复杂度的复杂度。

LOJ 数列分块入门

数列分块入门 1

区间加,单点查询。

查询复杂度为 \(O(1)\),对散块修改复杂度 \(O(B)\),对整块修改复杂度 \(O\left(\dfrac{n}{B}\right)\),总复杂度 \(O\left(B+\dfrac{n}{B}\right)\),显然 \(B\) 取 \(\sqrt{n}\)。

数列分块入门 2

区间加,区间查小于某个值的个数。

最暴力做法是直接排序然后二分,考虑分块排序。

区间加对整块没有影响,对散块的影响一次只有两个,于是每次暴力重构这两个散块。

修改复杂度 \(O\left(B\log B +\dfrac{n}{B}\right)\),查询复杂度 \(O\left(B\log B+\dfrac{n}{B}\log \dfrac{n}{B}\right)\),\(B\) 取 \(\sqrt{n}\)。

数列分块入门 3

区间加,区间查前驱。

和上一题类似,暴力排序查前驱取最大值,复杂度相同。

数列分块入门 4

区间加,区间求和。

比较平凡,散块 \(O(B)\),整块 \(O\left(\dfrac{n}{B}\right)\),只有加法标记所以不用下传。

数列分块入门 5

区间开方,区间求和。

单点开方只需要 \(O(\log \log a)\) 次,对整块的每次操作都开方,每个块最劣复杂度 \(O(B^2\log\log a)\),总体复杂度 \(O\left(\dfrac{n}{B}\times B^2\log\log a\right)\),取 \(B=\sqrt{n}\)。

数列分块入门 6

单点插入,单点查询。

使用块状链表,类似于链表套链表,维持每个块的链表大小不超过 \(2\sqrt{n}\),这样复杂度降到了 \(O(\sqrt{n})\)。

数列分块入门 7

区间加,区间乘,单点查询。

乘法的加入使得散块修改会破坏懒标记,于是暴力重构。

数列分块入门 8

区间查询出现次数并赋值。

两个操作放在一起,设想暴力查询并赋值,整块赋值打上标记,这样每个块处理第一次被完全扫过之后,只有一部分作为散块被处理才需要再下一次经过是再扫一遍。于是每次操作只会增加两个块需要被完全扫过,复杂度是正确的。

数列分块入门 9

区间最小众数。

一个重要性质:两个区间的众数要么来自前者的众数要么来自后者中的元素。

预处理由整块组成的所有区间的众数。当合并区间时,大区间的众数已知,新扩展的一个块中每个元素的出现次数可以二分查询(也可以前缀和)。

这样询问时,整块部分已知,同样是将两个散块中的元素查询出现次数并比较。

值域分块

可以用于查询区间第 \(k\) 大等问题。

正常的数列分块中,我们可以暴力维护块内排好序的数据,但是查询时需要二分答案,复杂度多一个 \(\log\)。

如果对值域分块,每个块维护该值域内的个数,可以 \(O(\sqrt{n})\) 确定第 \(k\) 对应的块,再 \(O(\sqrt{n})\) 扫过这个块求出答案。

对值域分块与数列分块的关系可以类比权值线段树与普通线段树的关系,前者处理排名前驱后继等更为优秀,后者则是便于处理关于区间和、积等等。

莫队

普通莫队

概述

不带修,实际上是以一种排序方式使看似暴力的做法复杂度变优秀。

对于一类区间询问问题,如果可以以 \(O(k)\) 的复杂度将区间左右指针移动一位,那么按照某种方法排序可以做到 \(O(n\sqrt{n}\times k)\)。

排序方法是:对序列分块,以左端点所在块为第一关键字升序排序,以右端点为第二关键字排序(奇数块升序偶数块降序)。

时间复杂度

设块长 \(B\),假设移动指针 \(O(1)\),分别考虑左右指针移动复杂度。

左指针在同一个块内,右指针最劣情况是移动 \(O(n)\),总复杂度是 \(O\left(\dfrac{n^2}{B}\right)\),左指针最劣情况是每次都移动 \(O(B)\),总复杂度是 \(O(nB)\),取 \(B=\sqrt{n}\),则算法复杂度是 \(O(n\sqrt{n})\)。

常数优化

在排序时,注意到第二关键字讨论了块的奇偶性,这使得我们升序扫完奇数块后,右端点左移的过程中已经开始处理偶数块,可以优化常数。

端点伸缩的顺序

可能会出现先缩小左区间再扩大右区间而导致当前的端点 \(l>r\),从而删去未加入的数据而导致错误。

保证正确且容易记住的顺序是:先扩大区间后缩小,先左端点后右端点。

带修莫队

概述

增加一维时间,需要改变排序方式。

以左端点所在块为第一关键字升序排序,以右端点所在块为第二关键字升序排序,以时间为第三关键字升序排序。

这样在处理每个询问时先移动左右指针,再移动时间指针并判断当前修改是否在左右指针范围内。

时间复杂度

  • 左指针:同样是每次最劣移动 \(O(B)\),总复杂度 \(O(nB)\)。

  • 右指针:左指针在同一个块时移动 \(O(nB)\),左指针改变块时移动 \(O\left(\dfrac{n^2}{B}\right)\)。

  • 时间指针:左右指针共构成 \(\dfrac{n^2}{B^2}\) 个块,最劣情况时每次移动 \(O(n)\),总复杂度 \(O\left(\dfrac{n^3}{B^2}\right)\)。

因此复杂度是 \(O\left(nB+\dfrac{n^2}{B}+\dfrac{n^3}{B^2}\right)\),取 \(B=n^{2/3}\),得到复杂度 \(O(n^{5/3})\)。

实际上,莫队是一类路径规划方法,在二维(普通莫队)与三维(带修莫队)的复杂度证明可以拓展,得到 \(k\) 维的复杂度:\(O(n^{2-1/k})\)。

回滚莫队

概述

以求区间众数为例,此类信息在增加元素时便于维护,但不便于删除,以 \(\mathrm{mex}\) 为例,此类信息在删除元素时便于维护,但不便于增加,于是可以使用回滚莫队,即只处理方便的部分,另一部分通过回溯版本来获得。

对于只增加莫队,以左端点所在块为第一关键字升序排序,以右端点为第二关键字升序排序,对于左端点所在块相同的询问,如果区间不跨块,直接暴力计算,反之则将左右指针定位在下一个块的第一个元素,右指针只升不降,左指针每次询问结束回到下一个块的第一个元素,这样规避了删除操作。

对于只删除莫队,排序方式仅需要把第二关键字改为降序,左指针在当前块的第一个元素,右指针在整个序列末尾,这样右指针只降不升,左指针每次询问回到当前块的第一个元素,规避了增加操作,容易发现只删除莫队是不需要考虑询问是否跨块的。

时间复杂度

  • 暴力计算复杂度 \(O(nB)\)。

  • 每个块内右指针只升不降,总复杂度 \(O\left(\dfrac{n^2}{B}\right)\)。

  • 每次询问左指针最多移动一个块,恢复时替换的信息规模与块长同级,总复杂度 \(O(nB)\)。

取 \(B=\sqrt{n}\),得到 \(O(n\sqrt{n})\) 的算法。

树上莫队

莫队二次离线?

例题

洛谷-P4462 [CQOI2018]异或序列

普通莫队。

子段异或和可以转换成前缀异或和的形式,这样增加一个元素时,其作为子段右端点的贡献是 \(sum_i\),作为子段左端点的贡献时 \(sum_{i-1}\),讨论增删时的位置即可。

洛谷-P3730 曼哈顿交易

普通莫队+值域分块。

求区间 \(k\) 小值,如果使用平衡树等数据结构维护是 \(O(\log n)\) 移动指针。

可以对值域分块,这样移动指针可以做到 \(O(1)\) 修改,而每次修改到要求区间后,询问又是 \(O(\sqrt{n})\) 的,总复杂度 \(O(n\sqrt{n})\)。

这里其实是一个平衡复杂度的思想,具体体现在移动指针总次数高于查询的总次数,因此在单次修改的复杂度应低于单词查询的复杂度。

洛谷-P1903 [国家集训队]数颜色/维护队列

带修莫队。

正常排序并处理即可。

洛谷-P5906 【模板】回滚莫队&不删除莫队

回滚莫队。

AtCoder-JOISC2014C 歴史の研究

回滚莫队。

类似区间众数,比较板子。

洛谷-P4137 Rmq Problem / mex

回滚莫队。

\(\mathrm{mex}\) 缩小区间比较好做,所以用只删除的回滚莫队。

为什么不用主席树?

参考资料

分块

莫队

标签:分块,复杂度,笔记,算法,sqrt,区间,莫队,根号,指针
From: https://www.cnblogs.com/SoyTony/p/Learning_Notes_about_Square_Root_Algorithms.html

相关文章

  • uni-app笔记
    uni-app笔记uni-app使用vue的语法+小程序的标签和API所有组件与属性名都是小写,单词之间以连字符-连接每个vue文件的根节点必须为<template>,且这个<template>下只能且必须有一个根<view>组件view==div<scriptlang="ts">//通过使用lang="ts"可以直接编写typescript......
  • Vue笔记
    Vue笔记vuex-router-sync插件:https://segmentfault.com/a/1190000037680351学到vue.js路由就没学了!还有过渡和动画、混入、AJAX、响应接口没学进度:https://learning.dcloud.io/#/?vid=5https://cn.vuejs.org/v2/guide/index.html模板组件化应用构建//问题:props是什么?技巧:......
  • uniCloud笔记
    uniCloud笔记结合:uni-admin实现后台的云管理,schema2code辅助自动生成代码(只需要定义好表结构)云函数云函数,是将本地写好的函数上传到云端,在云端的node.js的环境中运行。可以在本地的页面中在生命周期函数(钩子函数)中调用云函数如下://在组件/页面加载时,调用云函数的回调函数on......
  • Vue-Cli笔记
    Vue-Cli笔记新手上路在创建模式的时候,选择最后一个模式:自定义模式,创建项目,只需勾选下图3个配置,使用空格进行选择和不选择。然后选择vue版本2.x在选择css预编译中选择less最后选择是否将babel、Eslint等文件放到一个独立的文件中或放入package.json,我们选择第一项独立的文......
  • javascript笔记
    javascript笔记获得焦点onfocus,失去焦点onblurisNaN()判断是非数字undefined和数字相加最后的结果是NaNnull和数字相加最后的结果是数字typeof空格变量名或typeof(变量名)可以检测变量的类型parseInt('120.8px')最后的结果是120->数字;自动去掉px......
  • 算法学习day44动态规划part06-518、377
    packageLeetCode.DPpart06;/***518.零钱兑换II*给你一个整数数组coins表示不同面额的硬币,另给一个整数amount表示总金额。*请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回0。*假设每一种面额的硬币有无限个。*题目数......
  • 算法学习day45动态规划part07-322、279
    packageLeetCode.DPpart07;/***322.零钱兑换*给你一个整数数组coins,表示不同面额的硬币;以及一个整数amount,表示总金额。*计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回-1。*你可以认为每种硬币的数量是无限的......
  • 算法学习day46动态规划part08-139
    packageLeetCode.DPpart08;importjava.util.HashSet;importjava.util.List;/***139.单词拆分*给你一个字符串s和一个字符串列表wordDict作为字典。请你判断是否可以利用字典中出现的单词拼接出s。*注意:不要求字典中出现的单词全部都使用,并且字典中的单词......
  • 算法学习day48动态规划part09-377、213、198
    packageLeetCode.DPpart09;/***377.组合总和Ⅳ*给你一个由不同整数组成的数组nums,和一个目标整数target。请你从nums中找出并返回总和为target的元素组合的个数。*题目数据保证答案符合32位整数范围。*示例:*输入:nums=[1,2,3],target=4*输......
  • 算法学习day42动态规划part04-416
    packageLeetCode.DPpart04;/***416.分割等和子集*给你一个只包含正整数的非空数组nums。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。*示例:*输入:nums=[1,5,11,5]*输出:true*解释:数组可以分割成[1,5,5]和[11]。**/......