雅礼集训 Day3 数据结构
均值法
根号算法的本质是让两部分的复杂度接近从而使总复杂度最小，这在我们学线段树的时候比较前缀和和差分是一个道理。这种让两端复杂度均衡来达到最优的方法就叫均值法。
例题：舌尖上的由乃
- 区间加
- 区间k大
首先有个朴素的做法：每块维护排序后的序列，每次二分答案并判定，散块暴力，整块在排序后的序列上二分，块大小取 \(\sqrt n\)，复杂度是\(O(n\sqrt n\log^2 n)\)。
然后分析一下把块大小取\(\sqrt{n\log n}\)可以做到\(O(n\sqrt{n\log n}\log n)\)
其实修改的时候散块不用重构，直接归并即可。散块查询也可以先提出来再二分，总复杂度\(O(n/k\log^2n +\log ^2n+k)\)，当\(n/klog^2n=k\)的时候最优，为\(O(n\sqrt n \log n)\)
莫队算法复杂度
设块大小为k，每块内右端点单调，每次跨块右端点最多O(n)移动量，因此复杂度是\(O(n^2/k)\)。
跨块均摊左端点改变量是k，在同块内每次左端点移动量不超过k，因此复杂度是\(O(mk)\)。
总复杂度是\(O(n^2/k+mk)\)
当\(k=n/\sqrt m\)时复杂度最优，为\(n\sqrt m\)
杜教筛也运用了均值法。
Gty的二逼妹子序列
Autumn和Bakser又在研究Gty的妹子序列了！但他们遇到了一个难题。
对于一段妹子们，他们想让你帮忙求出这之内美丽度∈[a,b]的妹子的美丽度的种类数。
为了方便，我们规定妹子们的美丽度全都在[1,n]中。
给定一个长度为n(1<=n<=100000)的正整数序列s(1<=si<=n)，对于m(1<=m<=1000000)次询问“l,r,a,b”，每次输出sl...sr中，权值∈[a,b]的权值的种类数。
莫队+线段树，注意到莫队查询只有\(m\)次，而添加/删除是\(n\sqrt m\)次的，那么我们权值分块即可做到\(n\sqrt m+m\sqrt n\)（这能过？？？）
根号算法的互相结合
[hackerrank]Range Modular Queries
一个序列，值域是40000，每次区间询问模x等于y的数有多少个。
n<=40000
之前好像做过...
考虑对值域根号分治，\(x\leq 200\)的直接分块，处理\(200*200*200\)的前缀和+暴力。
\(x\geq 200\)的使用莫队，每次暴力在桶里找即可，容易证明每次询问\(O(\sqrt n)\)
"区间第k小"
给你一个序列元素均在[0,n)内，并给定常数w。
每次在线询问区间第k小，要求忽略区间出现次数>w的数。n<=100000
离线可以莫队+维护一个值域分块和桶，>w的时候处理一下即可。
现在要求在线，考虑为什么要莫队，因为我们想要得到一段区间的值域分块和桶。这个时候就要掏出分块套分块了，我们把序列分块，处理出第i块到第j块的值域分块，剩下的暴力加进去。
麻烦的是桶不能这样做，但是我们并不需要知道一个区间的桶，具体的我们只需要知道一个数在一个区间的出现次数，这个可以预处理每个数在前i块中出现了多少次，然后只需要对剩余部分暴力维护出桶。
对于>w的处理，可以先搞出桶再暴力搞值域分块。
[hdu6079]Yuno And Claris
一个序列，支持两种操作：
1、区间内值为x全部变成y。
2、区间询问第k大。n,m<=100000
我们可以将序列分块，对前缀块维护值域分块，现在问题是修改时的整块和散块，以及查询时的散块。
也就是我们要怎么操作才会获取每个位置是什么数？
对于每个块，每种数值维护一个链表，表示这种数值的所有位置，按任意顺序链接即可。
当对于整块执行了一个x->y时，直接把x的头接在y的尾上。
散块执行时，直接分裂出来接到y最后。
散块查询时，直接暴力扫所有链表，得到每个位置的数值。
复杂度\(O(n\sqrt n)\)
分块算法上树
子树分块
直接dfn序上分块。
链分块
随机\(\sqrt n\)个点为关键点，然后将关键点形成的虚树建出来，每条树边就是一个块。
没有被归入任何块的，那就当做散块。块数显然是\(O(\sqrt n)\)的，而且可以发现散块暴力期望长度也是\(O(\sqrt n)\)（不会证）
后记
后面还有一些杂题，自己看了看，就不写了。