分块真是博大精深呢。。。

• 一些难以合并的问题可以通过分块去解决。因为它实在是太暴力了。

• 还有一种思想叫做定期重构。每进行\(\sqrt N\)次操作之后就以\(O(n)\)的代价去重构整个序列。于是在询问的时候，我们最多处理\(\sqrt N\)个操作。

• 另外，还有一种分类讨论的思想。把某一个值和\(\sqrt N\)进行比较，进而得到两种不同的算法。

P3591 [POI2015]ODW

发现可以分类讨论k。

当k大的时候，一次跨1步（k条边）是可以接受的。

当k小的时候，一次必须多跨几步。于是我们可以预处理出跨\(2^i\)步即\(2^i\times k\)条边的代价，之后可以\(O(logn)\)求得答案。

预处理虽好，但显然是需要\(O(nlogn)\)一次的。

直接跳一个询问的复杂度显然是\(O(len/k)\)的

\(k>\sqrt n\)的时候直接跳，否则预处理即可。

---

P3604 美好的每一天

lxl出的题真妙妙妙妙妙啊。

考虑一个区间可以变成回文一定只有不大于1种字符的出现次数是奇数。

由于只考虑所有26种字符出现次数的奇偶性，我们可以状压后用异或和表示某一段区间。

所以我们可以用前缀和了。某一段区间用\(s_i\oplus s_{j-1}\)即可

再记录某种状态的前缀和有多少种，最后用莫队算法即可实现。

复杂度大概是\(O(n\sqrt n \log n)\)

---

codechef chef and churu

噫

先考虑一下函数l=r的时候。

直接随便怎么分块，或者用线段树啥的也都可以。
但是由于下面的方法限制，我们最好使用\(O(1)\)处理询问的还可以带修改的分块
记录整块前缀和 以及 块内前缀和。

然后再考虑其它情况：
由于询问的函数也是一段区间，可以考虑对函数进行分块。
记录每一块内有多少个地方的函数包含了\(A[i]\)这个数。
于是，块内修改就可以实现了。

询问的时候，不在整块里面的利用上述方法暴力更新即可。