LOJ6277 To LOJ6285 - Click Here
9/9
前言
感谢KsCla的关心。
LOJ6277
Solutions考虑对序列分块。对于修改操作，若包含整个块则用个tag保存，否则暴力修改。
设每块元素为$m$，则时间复杂度$O(n(\frac{n}{m}+m))$。当$m$取$\sqrt n$时，时间复杂度$O(n\sqrt n)$
CODE
CODE - Click Here
LOJ6278
Solutions考虑对序列分块，对于每个块都维护其升序序列。
对于修改操作，若包含整个块，则用tag保存，否则暴力修改，并重新维护；对于查询操作，需要对整块二分查找。
设每块元素为$m$，则时间复杂度$O(n( \frac{n}{m} \, \log \,m+m \, \log \, m))$。当$m$取$\sqrt n$时，时间复杂度$O(n \sqrt n \, \log \, \sqrt n)$
CODE
CODE - Click Here
LOJ6279
Solutions做法与LOJ6278一致。
CODE
CODE - Click Here
LOJ6280
SolutionsLOJ6277的加强版，从单点查询变为区间查询。
对于区间查询，可以考虑对每个块维护块内元素和，这样区间查询时即可快速得到整块的答案。
时间复杂度分析同LOJ6277，$O(n \sqrt n)$
CODE
CODE - Click Here
LOJ6281
Solutions对于数字$a$，其开根号次数大概在$log \, log \, a$左右。因此，对于int范围的整数，至多6次数字就变为0或1。
基于这个事实，我们可以对于根号操作暴力修改，如果某个块均为0或1的话，则可以跳过修改。而查询操作与上文类似。
现在考虑下时间复杂度。在每次修改中，整块至多修改6次，即$6n$，而对于不完整的块内的元素，本身受到块大小限制，因此不会有问题。这样，这题就能够解决了。
时间复杂度分析类似LOJ6280，$O(n \sqrt n)$
CODE
CODE - Click Here
LOJ6282
Solutions若暴力插入，时间复杂度为$O(N)$。考虑对序列分块，这样插入时间复杂度与块大小相关。再加之数据随机可知块大小是期望增加$\frac{Qm}{n}$的(其中m为块大小)，块大小只是常数上的变化，因此可令$m=\sqrt n$得到$O(n \sqrt n)$的做法。
现在来考虑下数据不随机的做法。由于数据不随机，可能会存在疯狂往一个块里插入的情况，这样时间复杂度会倒退到暴力复杂度。因此，需要维护每个块来保证其时间复杂度不会倒退。
这里引入一个重构的思想。当某个块大小过大或者操作数过多时，选择重新对新序列分块。下面给出的是限制操作数做法，阀值为$\sqrt m$。此种做法在随机情况下劣于限制块大小，因此常数略大。
CODE
CODE - Click Here
LOJ6283
Solutions其实和LOJ6277一样，只是多了一个乘法。注意好乘法优先度大于加法，然后分别维护tag即可。
时间复杂度分析同LOJ6277，$O(n \sqrt n)$
CODE
CODE - Click Here
LOJ6284
Solutions一道相当有趣的题。
注意到序列不同颜色数是与操作数相关的。基于这点，考虑对序列分块，并对每个块维护一个tag，表示该块是否颜色相同。对于查询操作，如果整块颜色不同则暴力查询，否则$O(1)$得到答案。
现在分析一下时间复杂度。原序列可以认为是由一个纯色序列$n$次修改得到的，因此假定序列一开始颜色相同。对于一次操作，若要达到$O(N)$的复杂度，必须保证其区间内不存在一个纯色的块，即需要$\frac{N}{m}$(其中$m$为块大小)次操作才能够使得该操作达到$O(N)$复杂度，均摊时间复杂度为$O(m)$。同时，单次操作的时间复杂度为$O(m+\frac{N}{m})$，其数值大于均摊时间复杂度，所以可以将每次操作时间复杂度认为是$O(m+\frac{N}{m})$。令$m=\sqrt N$，则可知该做法时间复杂度$O(N \sqrt N)$。
这题其实还有$\log$的级别做法。其思路的来源大概是因为，分块本质上是一个$\sqrt N$叉树，根据这点类推到二叉树上。但是对于任意的$m$叉树是否都能有类似复杂度，我并没有推出来……
其构造方法与分块类似，对于每个节点都记录一个tag，用于保存其子节点是否为相同颜色，然后询问就暴力在二叉树上寻找即可。
同样的，来分析下复杂度。我们认为原序列一开始是纯色序列。对于一个操作，其操作区域对应二叉树上的$\log N$个节点。而经过一次操作后，只有包含最左或最右节点的节点会更改其tag。换言之，一次操作会导致$\log N$个非纯色节点的产生。而一次查询操作，需要的时间复杂度为$\log N$加上其包含的所有非纯色节点，并且在查询过后，这些节点都会变为纯色节点。
现在定义非纯色节点数为势函数，则势函数始终大于等于0。又因为均摊代价里，势能的变化量和查询的额外代价相抵消，因此得到最终时间复杂度是$O(N \log N)$的。
CODE
CODE(分块做法) - Click Here
CODE($N \log N$做法) - Click Here
LOJ6285
Solutions经典的区间众数问题。
首先是一个比较显然的做法，莫队算法。考虑到对于一个区间，如果维护以数量为第一关键字，数值大小为第二关键字的堆，便能在$\log N$的时间内转移左右端点。因此直接跑莫队算法即可。
接着是分块做法。对于这题，有一个重要的结论，假设$mode(A)$表示$A$集合的众数集合，那么$mode(A \cup B) \subseteq mode(A) \cup B$。这个结论比较显然，思考一下即可得到。基于这一点，可以得知，如果求出任意区间的众数的话，需要得到完整块的众数，以及任意元素在区间内的个数。
先来解决任意元素在区间内的个数。这个很好解决，可以对于每个元素，都记录其在哪些位置出现过。然后询问区间内个数，等价于询问位置集合对应的前驱、后驱，直接二分即可。那么对于完整块的众数，也可以用同样的方法解决，看成是一个完整块与非完整块的合并。根据简单的分析可知，该做法时间复杂度为$O(N \sqrt N \log N)$。
当然，这种做法显然并不优秀。我们考虑优化这种做法。上诉做法的瓶颈仅仅在于如何求出任意元素在区间内的个数。由于非完整块的元素是需要扫描一遍的，因此其实只需要知道任意元素在块内的个数。这个只需要对每个元素求其块的前缀和即可。根据简单分析，可知时间复杂度为$O(N \sqrt N)$。
最后跑出来，只有$N \sqrt N$跑过去了，其余两个都TLE的……
CODE
CODE(莫队算法) - Click Here
CODE($N \sqrt N$做法) - Click Here
CODE($N \sqrt N \log N$做法) - Click Here