几个离线算法的介绍幻灯片.pptx

山神昨天讲了对拍保平安的相关内容 那我今天就讲暴力出奇迹 先讲个故事 有个老司机带大弟子和二弟子上南山学习了，回来之后二徒弟就觉得给同学们普及一下新姿势吧，想了想决定要普及一下数据结构姿势。 先讲个故事 然后二徒弟回想了一下自己和大师兄会点啥： 栈 队列 散列表 并查集 线段树 树状数组 堆 可并堆 树堆 伸展树 树链剖分 动态树 先讲个故事 然后二徒弟回想了机房的平均水平会点啥： 栈 队列 散列表 先讲个故事 刚学了点啥？树套树和煮席树。 如何拯救你们？四月份就省选了而你们还每天在机房里放肆，省实验联赛被吊打的那帮人，比你们高到不知道哪去了。 也罢也罢，咱们就是靠暴力拼出一片天的，数据结构不会，我们也可以暴力。 先说说讲点啥吧 莫队算法 CDQ分治 整体二分 你问我为啥这是暴力？因为 这是离线的艺术， 这是高端的暴力。 为啥要讲这些 观众老爷们反映了： 这些玩意逼格太高学不会咋办？ 学这些有什么卵用吗？ 离线在线是啥能吃吗？ 不如来一局炉石传说如何？ 为啥要讲这些 你们啥杰宝数据结构都不会，万一考几个数据结构题不就团灭了？ 放心这些玩意没那么难。 离线就是你可以先把操作存下来慢慢做。 就跟你假期补作业一样。 好好看好好学很有用的。 莫队算法 例题：OJ2011 背景 Background  dydxh又给mzx出了一道数据结构题，mzx这种菜逼还是不会做。 描述 Description  dydxh又没有强制在线，于是mzx又可以开心地水过了，不过他发现，在线貌似不可做？给定长度为n的数列以及正整数，有m个询问每次询问给定两个数l,r，求l≤i≤j≤r，且a(i) xor a(i+1) xor a(i+2) xor ... xor a(j)=k的(i,j)的个数。 莫队算法 这是cf#340上的一道题。 当时我和山神都没做出来。 然而赛后： 莫队算法 我：知道[l,r]的答案就能在O（1）时间内算出[l-1,r][l+1,r][l,r-1][l,r+1]的答案了，可是怎么办呢？ 山神：如果我能在知道[l,r]的答案的前提下在O(1)的时间内算出[l-1,r][l+1,r][l,r-1][l,r+1]的答案的话我就能用莫队算法了。 然后就没有然后了。 莫队算法 题目本质： 给定一个数列a[i]，你可以通过异或前缀和求出s[i]，每次求[l-1,r]内s[i] xor s[j]=k的(i,j)的对数。 莫队算法 莫队的标志： 记cnt[x]为当前区间内s[i]=x的i的数量，那么如果我们知道询问[l,j]的答案ans和cnt数组的话，考虑将l-1或r+1加入（删除左右端点反之）这个区间，设要加入的这个数为x。 那么ans+=cnt[x^k]，cnt[x]++即可。 莫队算法 如何通过规划一个合理的求答案的顺序来优化程序？我在考场上想了将近一个小时。 分块。 前天晚上有个菜B在群里说无法理解分块的强大，我来教你做人。 莫队算法 先将询问排序。 然后干啥？分块啊。 假设我们将询问数组分为p块，每块长度为l，那么显然l*p≈m。 莫队算法 假设我们在f(n,len)的时间内处理完一个块内的询问，而且在g(n)的时间内处理掉从一个块到另一个块的跳转，那么很显然我们能在O(f(n,len)*p+p*g(n))的时间内解决所有询问。 莫队算法 分块的标志是根号，因为大多数分块算法中l和p对复杂度的贡献是相乘的，所以根据基本不等式l和p应该是相等的。 莫队算法 不瞎扯淡了直接讲怎么分吧。 我们先按照左端点排序，然后分块。 然后在每个块内按右端点排序。 然后顺序处理即可。 莫队算法 块内复杂度： 因为块内右端点是递增的，所以右端点至多变化O(n)次，而左端点 不一定，所以是O(l*l)=O(n)次。 块间跳转：撑死了O(n)。 总复杂度：O(n^1.5)。 莫队算法 例题：OJ2012 作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜子过程，于是他决定听天由命……具体来说，小Z把这N只袜子从1到N编号，然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否一左一右，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。你的任务便是告诉小Z，他有多大的概率抽到两只颜色相同的袜子。当然，小Z希望这个概率尽量高，所以他可能会询问多个(L,R)以方便自己选择。100%的数据中 N,M ≤ 50000，1 ≤ L R ≤ N，Ci ≤ N。 莫队算法 总结几点： 区间端点移动时的处理证明正