BZOJ 2006
题意：求序列区间和前$k$大的和。

我题意转化得不好。。我转化成求序列$k$个可重区间和的和，没有体现出本题的贪心思想
然后我们可以发现固定了区间的左端点，那么他的右端点是有固定取值集合的，即$[i+L-1, \min(i+R-1, n)], i+L-1 \leq n$
那么我们先把所有左端点的右端点取值集合弄出来，用ST表维护最大的右端点前缀和，那么这个区间就是最大值的候选答案，加到堆里
然后每次从堆中取出一个区间，加上和以后，删掉这个最优的右端点，继续放进堆作候选答案

当然也可以主席树来做，即每次更新就将那颗树的右端点位置赋值为无穷大，然后这个点不会再影响答案，线段树维护区间最大值即可。
或者直接查询$k$大

知识点
1、左端点的取值集合运用
2、区间和——前缀和

BZOJ 4552
题意：给出一个$1$到$n$的全排列，现在对这个全排列序列进行$m$次局部排序，排序分为两种：
$1:(0,l,r)$表示将区间$[l,r]$的数字升序排序
$2:(1,l,r)$表示将区间$[l,r]$的数字降序排序最后询问第$q$位置上的数字。

方法一
只有一个位置，我们可以二分这个上面的数是多少。
考虑将数的排序转化为二进制数$01$的排序。因为二进制数$01$的排序只需要升序将所有$0$放在$1$前，降序反之。
那么我们怎么将数转化成这个呢，我们考虑大于二分值的数赋值为$1$, 否则为$0$，对询问离线，线段树辅助$01$数排序，求出最后的结果，然后如果$q$上是$1$，说明当前二分值小了，否则大了。
线段树排序$01$数即查询区间$01$个数，再区间修改
本方法难想但是代码好写。

方法二
考虑直接模拟题目的过程，我们可以将原来的每个数变成孤立的每个点，那么每次排序都会合并一系列点，并且此时还可能需要分裂。我们考虑一个支持合并、按前$k$大分裂的权值线段树。用一个$\text{Set}(l,r,nd,op)$来维护区间合并情况，即记录$[l,r]$的根在$nd$, 是升序还是降序，然后分裂时二分找出来后处理即可。具体可以看代码实现。这里体现了数据结构互相辅助的优势。
本方法好想，但是代码难写。本题为了训练线段树分裂，我写了方法二的代码。

本文借鉴于 HEOI2016/TJOI2016 排序 解题报告（二分答案/线段树分裂合并+set） - 星星之火OIer - 博客园

知识点
1、将数的排序转化为二进制数$01$的排序的方法 (用于二分)。
2、数据结构互相辅助的优势。

BZOJ 4542
题意：给定一个数字串，询问一些区间组成的数(可含前导零)是否是给定$p​$的倍数。

显然前缀和取余来做。然后刚开始我是想莫队+map，即存前缀和，用公式算出个数，但是这非常麻烦。。
我们可以发现前缀和取余以后，前缀和余数相同，则之间的区间和是模数的倍数
那么我们直接维护前缀和序列的相同数对个数即可，莫队裸题。。
具体证明我们可以设$\text{sum}(i)$为后缀和($[i,n]$表示数)，那么数字即为$\frac{\text{sum}(i) - \text{sum}(j+1)}{10^{n-i}}$
设$[l,r]$表示的数为$\text{num}(l,r)≡\frac{\text{sum}(l)-\text{sum}(r+1)}{10^{r-l+1}}\pmod p$
区间能够被$p$整除当且仅当$\frac{\text{sum}(i) - \text{sum}(j+1)}{10^{n-i}} \equiv \text{num}(l,r)\pmod p $
即$\text{sum}(i) - \text{sum}(j+1) \equiv \text{num}(l,r) \cdot 10^{n-i}\pmod p $

显然$10^{n-i}$与$p$互质，那么这个当$\text{sum}(i)=\text{sum}(j+1)$时，可以确定他们同余

满足条件是$\gcd(p, 10)=1$，所以要特判$p=2,p=5$的情况，具体可以看代码的方法。

注意$r+1$取值为0，要把0加入离散化

知识点
1、前缀和余数相同，则之间的区间和是模数的倍数

BZOJ 4540
题意：$m$ 组询问区间$[L,R]$的所有子区间的最小值的和。

第一种思路是用莫队，考虑加入后加入位置对当前答案贡献
设$s_i$表示所有以$i$为右端点的答案
具体方法见其他题解

第二种方法就是考虑将一个位置$i$左边第一个小于$i$记为$L_i$，右边第一个小于$i$记为$R_i$
那么左端点在$[L_i+1,i]$，右端点在$[i, R_i-1]$的区间最小值都是$a_i$
我们将左端点右端点分别映射到二维平面的横坐标纵坐标，那么这个贡献就可以在矩形中加上贡献，询问同样，就是询问矩形的和
那么我们这里可以直接二维数据结构维护，但是常数大不能过
我们考虑离线扫描线降维，用一个树状数组维护差分序列即可。

知识点：
1、区间$[l,r]$看做二维平面上的点$(l,r)$，则方便用区间操作处理一下区间
2、记录左右离$i$最近的比$i$小的数，思路类似上一个颜色在哪

BZOJ 4827
题意：给定数列$a,b, b$可以循环移动，选择整数$c$，求
$$
\min\sum\limits_{i=1}^n(a_i-b_i+c)^2
$$

化简式子，可得
$$
\sum_{i=1}^na_i^2+\sum_{i=1}^nb_i^2-2\sum_{i=1}^na_ib_i+nc^2+2c\sum_{i=1}^n(a_i-b_i)
$$
前面两项是定值，后面两项可以看作一个关于$c$的二次函数，显然有最小值，求最近对称轴$\frac{\sum\limits_{i=1}^n (a_i - b_i)}{n}$的两个点的最小值加入答案。

现在问题变为求$\min\sum\limits_{i=1}^na_ib_i$

我们将环断为链，复制一份在后面
考虑平移的情况
$$
\min\sum\limits_{i=1}^na_{i}b_{i+k}
$$
我们可以转化一下，翻转$a$数组，得
$$
\sum\limits_{i=1}^na_{n-i+1}b_{i+k}
$$
那么两项下标为常数，是卷积的形式，FFT求卷积即可，最后扫描一遍求最大值，答案减去这个最大值。

知识点
1、FFT 套路：翻转数组形成卷积

BZOJ 1926
题意：见上
本题显然是两个题。
首先考虑$n,m \leq 200$的，二维前缀和记录矩形大于某数个数和和，二分查找即可
考虑$r=1$的，即用类似的方法，二分+主席树即可。

知识点
1、主席树节点数和操作次数有关，与值域无关
2、主席树边更新边合并和更新完合并两种写法不要写混

Codeforces 590E
题意：给定$n$个字符串，求出最大的集合使得没有任意两个字符串是包含关系。

第一题Div1E…

多模式串可以想到用AC自动机，然后包含关系可以看作一个偏序关系，那么题意就是求最长反链。
最长反链等于最小链覆盖，传递闭包后二分图匹配。注意输出方案，即为最小点覆盖取反，具体方法看算法竞赛进阶指南上。
AC自动机注意要沿着fail指针找子串否则不能找全，并且找到最近的即可，因为我们要传递闭包，找多个会TLE

知识点：
1、多模式串可以想到用AC自动机
2、包含关系、到达关系、大于等于关系都是偏序关系

Bzoj 2744
题意：见上。

本题本质上是求一个最大团。
分析A发现一个最大团中A最多有两个，否则是不合题意的
然后我们就可以枚举A有几个，然后将这几个A相连的B一起做一个最大团
我们发现B条件即为一个奇偶的二分图，在二分图上求最大团即可
然后这里最大团=总点数-补图最大独立集
要将奇数放在二分图左边，注意不清空数组的技巧

知识点
1、|不要打成||

BZOJ 3295
题意：给定一个排列，每次删一个数，求整个序列逆序对。

先求出原序列逆序对
维护一个数前面比他大的数的个数$a_1$, 后面比他小的数的个数$a_2$
本题删除一个数，那么当前答案减去$a_1[i-1], a_2[i+1]​$
但是考虑删掉的数不会贡献答案，用一个带修主席树维护被删的数的个数，在主席树上二分找比某数小某数大即可。

本题也可以CDQ分治，显然是个三维偏序

我们把删除反过来看作添加新数字，然后考虑$(T_i, x_i, y_i)$，$T_i$为插入时间，$x_i$为位置，$y_i$为值

将第一维排序，第二维 CDQ，第三维树状数组维护

BZOJ 2303
题意：有一个$n \times m$的矩阵，可以放入$0$或$1$，现在已经有$k$个格子放好了$0$或$1$，要把矩阵放满，要求是矩阵中每个$2 \times 2$的格子有奇数个$1$。输入$n、m$和已经放了的格子，求方案数。

根据异或性质$a \oplus b \oplus a = b$
考虑一个矩阵

ABCD
EFGH
IJKL

我们发现对于任意$2 \times 2$矩形异或和都是$1$，因为要符合题意

那么我们发现
$$
A \oplus B \oplus E \oplus F=1 \tag{1}
$$
$$
B \oplus C \oplus F \oplus G=1 \tag{2}
$$
$(1), (2)$异或，则得
$$
A \oplus E \oplus C \oplus G=0 \tag{3}
$$
又可以得到
$$
C \oplus G \oplus D \oplus H = 1 \tag{4}
$$
$(3), (4)$异或，则得
$$
A \oplus E \oplus D \oplus H = 1
$$
我们发现横向异或可以数学归纳法证明，$(1,1) \to (i, j)​$, 如果列数是偶数，则异或和为1，否则为0
对于列同理
那么我们发现只要行列都是偶数，那么异或和是1，否则是0

也可以直观上来看，对于$(1,1) \to (i, j)$这个矩形，考虑矩形包含$2 \times 2$矩形的个数。

根据数学归纳法，如果原方格内的第一行和第一列的格子被确定，那么整个方格即可被唯一确定。

我们可以发现$(1,1) \oplus (i,1) \oplus (1,j) \oplus (i,j)=0 / 1$ (取决于上述规则)

那么我们就可以枚举$(1,1)$填什么(如果没有限定，否则就只填一种)，然后维护异或关系。

显然可以用带权并查集来做。具体看代码实现。最后答案是除了$(1,1)$联通块的个数$k$, $2^k$