分块

写一点。

数列分块入门6，主要是定期重构，如果数列的形态改变的话，那么设定阈值为每至少 \(\sqrt n\) 次操作做一次重构，时间复杂度是直接根号的。

数列分块入门8，主要是势能分析（好像是），统计一个区间的最大值和最小值，这个是容易统计的，然后你考虑一个区间询问有多少个相同的，对于最大值和最小值有疑问的就暴力扫一下否则就不管了，然后区间赋值，中间整块势能没了，旁边的加1

数列分块入门9，考虑离散化之后我们可以预处理出从第 \(i\) 个整块到第 \(j\) 个整块之间的众数，而区间询问的误差在于旁边的散块，于是我们考虑对于每个颜色我们先把散块的拉满然后再把整块区间的拿下，然后和预处理的整块答案比较一下取优的就行。

P4119未来日记，考虑先看询问再看修改，询问问区间k小，其实这个东西是很经典的问题了，但是这个修改就搞得挺难受的，考虑对于每个整块也做一个值域分块，然后每次相当于是在值域上面做 \(\sqrt n\) 次单点修改，这样维护值域之后能做什么？

我们考虑求第 \(k\) 大一直有一个很传统的方法就是直接二分答案后问排名，我们把这个套用过来，一段区间内的这个排名，我们考虑散块直接暴力问，整块的话我们统计一个值域分块上的前缀表示在这个区间内这个权值的数的数量（因为这个可减），但是我们做了二分之后不能直接求吧，对这个值域我们还得求个前缀和，如果要在这个修改的基础上维护前缀和的前缀和单log很难做到，但是可以直接值域分块，然后求一个的时间复杂度降为根号，而修改操作因为要修改后面的前缀和，这个随便拿个数据结构来维护就好了。

但是这个散块没法维护啊，实际上作为一个单点直接向上面那样维护就好了，时间复杂度根号带log。

upd:果然水平还是太低，根号log算法过不了啊！

考虑kth其实有一个根号做法就是对值域分块后枚举整块然后枚举散块可以做到单次根号（这个是真没想到，看题解了才发现，知道这个后面的就全都明白了），但是我们这个没办法这么做，我们有整整根号次修改，对块内的倒是影响不大，块外的就闹翻了，不过其实问题也不大，因为每次都只会动两个权值的前缀和，那么对这两个权值所在的块重做前缀和时间复杂度只有根号，这样两边时间复杂度都降下来了。

upd:果然水平还是太低，没考虑标记问题

刚开始的思路是并查集维护代表权值然后似了，考虑这个东西只要一合并就拆不开了，或者说难得拆开，所以每次如果没出冲突就不管出了就重构的时间复杂度是正确的。

然后就是卡常，卡了一上午加半个下午才过。。

那再来开一下P4118末日三问好了，区间加和区间最大子段和。

先来想想看，分块咋解决区间最大子段和问题，这个其实挺简单的，就像正常dp一样维护就好了。

那么我们要做的就是动态维护以块端点为分界点的往左往右的最大值。

但是还要做区间修改，散块倒是可以直接维护，整块的就有点乏力话说如果这个有办法直接维护我为啥不直接进行线段树，感觉还是不太可行。

那我们回到最开始，我们要想一个分块维护区间最大子段和的方法。

我们分块是能做的当且仅当分块之后可以对整块快速处理。

也就是说对整块的快速处理，