Preface
想记录一些有意思的题，结果发现有点难度的题全是 ds。/gg
一些过于板的题或者板子题就不写了。
Text
斐波那契 \(\to\) 矩阵乘法，所以线段树套矩阵乘，每次修改时在懒标记上往前推 \(x\) 次就行了。
时间复杂度：\(O(n\log^2n)\)。
构建一个竞赛图，其中有一个结论：将所有点按入度升序排序后，若前 \(n\) 个点的入度和为 \(\frac{n(n-1)}{2}\)，且不存在更小的 \(n\) 满足这一条件，则这 \(n\) 个点构成一个强连通分量。
简易证明上述结论后就可以得到正解。
一共询问 \(n\) 次。
做一个异或前缀和，然后莫队，用桶记录一下区间中的数，每次加入的时候匹配一下即可。
时间复杂度：\(O(n\sqrt n)\)。
发现每次交换一个结点左右子树时，影响到的只会是跨越两棵子树的逆序对。
那么就比较是交换逆序对少，还是不交换，然后线段树合并。
时间复杂度：\(O(n \log n)\)，空间复杂度：\(O(n \log n)\)。
计算 \(p\) 级表亲不如计算它的 \(p\) 级祖先有多少个 \(p\) 级子孙。
然后就是线段树合并。
时间复杂度：\(O(n \log n)\)，空间复杂度：\(O(n \log n)\)。
看完斜率优化 dp 的日报突发奇想写的。(
以后就当斜率优化 dp 复习题了。
迎来了第一道有点思维难度的题。
对于点 \(l,r\) 的联通性，可以转化为一个二维平面。
考虑用 \(set\) 维护连通块，若点亮 \(x\) 相当于合并连通块 \([l,x]\) 和连通块 \([x+1,r]\)，熄灭 \(x\) 则相反。
因为要查询每个时刻的值，所以考虑求平面上每个点的贡献，可以自己考虑怎么定贡献的值，要注意的是对于每次修改，我们做一个左上角为 \((l,x+1)\)，右下角为 \((x,r)\) 的二维平面加。
涉及二维平面加和单点查询，使用树状数组套主席树维护。
时间复杂度：\(O(n \log^2 n)\)，空间复杂度：\(O(n \log n)\)。
用普通莫队+\(set\) 可以做到 \(O(n\sqrt n \log n)\)。
思考如何优化，发现链表可以预处理出排序后的序列，但只能删除，于是考虑用删除莫队+链表。
时间复杂度：\(O(n\sqrt n)\)，被 2log 做法吊打。
算一道神题？
在大神 dreamerkk 的帮助下 A 了这题。
解题思路的关键点就在于对一个数进行 \(\textrm{popcount}\) 过后，值域变为 \(\log V\)。
可以用一个置换 \(f\)，那么原来的数 \(x:=f(\textrm{popcount}(x)+a)+b\)。
线段树，时间复杂度和空间复杂度都是 \(O(n \log n \log V)\) 的。
数据范围限制了线段树做法，所以剩下来做法的就只有 ODT 和动态开点线段树了。
ODT 在这种题里都可以被动态开点线段树替代，而且在其他题中容易被卡，码长也相较线段树来说较长，所以我个人认为 ODT 可能不太重要。
懒得写了。
之前忘做的一道分块经典题。
如果是普通的分块，一块一块地合并出各数出现的次数是 \(O(n)\) 的，这样做显然不现实。
所以考虑预处理出所有块的边界端点组成的区间的众数与区间中各个数出现的次数。
如果设块长为 \(\frac{n}{B}\)，那么这种区间一共有 \(B^2\) 个，所以时间复杂度为 \(O(nB^2 + \frac{nm}{B})\)。
取 \(B\) 为 \(n^\frac{1}{3}\)，时间复杂度为 \(O(n^\frac{5}{3}+mn^\frac{2}{3})\)。
标签：frac,log,记录,线段,提交,杂题,复杂度 From： https://www.cnblogs.com/kowenxrz/p/17112350.html