分块大法好啊

分块，顾名思义，就是一种把序列分成若干个块的算法（数据结构）

前段时间的时候写的分块，调到怀疑人生，结果今天开始学主席树了发现我爱分块

分块的思想简称就是：大块维护，小块朴素

P3396 哈希冲突

我们先假设一下，如果说模数是小于等于 $\sqrt{n}$ 的时候，我们是不是可以预处理出来所有模数对应的答案（更改很容易的）

然后我们再想一下，如果说模数大于 $\sqrt{n}$ 的话，是不是也只有那么不到 $\sqrt{N}$ 的数会被记录到答案里

然后就没了

这个题转化一下就相当于是求区间之内一个数字的排名对吧（仔细想想就知道了）

那么我们可以分块维护所有的数字，大块维护，小块朴素，大块就维护一下加了多少的tag

我们把每一个块进行排序处理，就可以直接二分进行求解一个块里面有多少满足条件的数字

然后就没了

这个题就是上面的题的加强版

我们考虑这样一件事情：把所有的数字每个时间点所对应的状态写成一个矩阵一样的东西的话，一个区间修改操作就换变成一个矩阵修改操作，是在这个时间点为横坐标，两个端点为纵坐标，最后为横坐标的矩形进行操作

那么我们进行一遍扫描线

从上往下扫一遍

扫了一遍之后的序列就是这个数字在不同时间点对应的状态

就转化成了上面的那个题

我们发现，对于两个数交换的时候，逆序对的贡献变化只会在这两个数中间进行变化

那么我们分块维护一下，还是想上边一样的排序

就可以求出来逆序对数的增加减少

就完了

区间众数

lyd例题

首先离散化

我们考虑把序列分为T块的话

预处理出来枚举一个块的左端点作为区间的左端点，另一个块的右端点为区间的右端点的众数和所有数出现的次数

对于一个询问的区间来说，这个区间的众数要么是整块的众数，要么是小块出现过的数

那么就打擂台就好了