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 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$

bzoj 3123
题意：小$Z$有一片森林，含有$N$个节点，每个节点上都有一个非负整数作为权值。初始的时候，森林中有$M$条边。
小Z希望执行$T$个操作，操作有两类：

1. Q x y k查询点$x$到点$y$路径上所有的权值中，第$k$小的权值是多少。此操作保证点$x$和点$y$连通，同时这两个节点的路径上至少有$k$个点。
2. L x y在点$x$和点$y$之间连接一条边。保证完成此操作后，仍然是一片森林。

这题查询$k$小值点，显然主席树。
考虑怎么处理合并两棵树。我们想到了LCT。但是这题我们完全可以启发式合并。
每次合并两个集合，然后对小的集合重新算倍增、深度等
注意本题是合并的时候再建链，而不是先建链再合并，否则会合并很多次，造成数据重复

知识点：
1、加边要加双向边

BZOJ 3997
题意： 给出一个网格图，其中某些格子有财宝，每次从左上角出发，只能向下或右走。问至少走多少次才能将财宝捡完。此对此问题变形，假设每个格子中有好多财宝，而每一次经过一个格子至多只能捡走一块财宝，至少走多少次才能把财宝全部捡完。

一开始觉得是上下界网络流。。范围太大了
这题是一个最小链覆盖问题，可以转化为最长反链覆盖。
考虑这里的反链，我们让$x$能到$y$看作偏序关系，然后对于$x,y$在同一反链当且仅当这两个点是右上、左下关系
那么设$dp(i,j)$为以$(i,j)$为左下角的矩形中的最长反链长。那么考虑转移
$$
dp(i,j)=\max(dp(i-1,j), dp(i,j+1), dp(i-1, j-1)+a_{i,j})
$$
前两个是继承关系，后一个是包含$(i,j)$的最长反链长，显然$(i,j)$和$(i-1, j-1)$在一个反链。

知识点
1、只向下/右：DP
2、二分图网络流问题：链、反链、最小点覆盖、最大独立集的转化