快到NOI了老年选手要开始复习了

大纲：来自PoPoQQQ的tag

（标记说明：1表示常用 0表示不太熟悉 -1表示不会或者很久没用）

图论：

1 网络流

1 Dijkstra

1 对偶图

1 树剖

1 LCA

1 Kruskal

1 Floyd

0 分层图

0 拓扑排序

0 匈牙利算法

0 费用流

-1 弦图

-1 SPFA

-1 Tarjan

-1 Prufer序列

-1 动点SPFA

-1 倍增Floyd

-1 Prim

-1 2-sat

算法&思想：

1 容斥

1 分块

1 递推

1 Hash

1 二分

1 记忆化搜索

1 莫队算法

1 整体二分

1 扫描线

0 模拟

0 博弈

0 Floodfill

0 贪心

0 差分

0 暴力

0 三分

0 朱刘算法

0 构造

0 IDA*

-1 高精度

-1 差分约束

-1 A*

-1 最小表示法

-1 随机增量法

字符串：

0 KMP

0 Trie

0 AC自动机

0 Manachar

0 SAM

-1 后缀数组

-1 回文自动机

（字符串弱得抠脚）

计算几何：

1 凸包

1 Simpson

-1 旋转卡壳

-1 半平面交

DP：

1 斜率优化

1 树形DP

0 数位DP

0 状压DP

0 期望DP

-1 插头DP

数据结构：

1 树状数组

1 替罪羊树

1 KDT

1 并查集

1 线段树

1 单调队列

1 堆

1 单调栈

1 Splay

1 Treap

0 点分治

0 可并堆

0 启发式合并

0 LCT

0 可持久化数据结构

-1 斯坦纳树

-1 动态树分治

-1 树套树

数学相关：

1 单纯形

1 线性筛

1 矩阵乘法

1 组合数学

1 Lucas定理

0 高斯消元

-1 群论

-1 BSGS

-1 莫比乌斯反演

-1 FFT

从1到-1依次复习，复习方法大概是80%口述思路+20%代码，0和-1的部分必须要打代码

7月11日

网络流：

BZOJ3630 物理费马小定理+最小点割集 一个点拆成两个点之后当成最小割做就行了

BZOJ1565 最大权闭合子图 模型很裸，但是有环，所有指向环的点都不能取 所以直接反向图拓扑排序一下找到能用的点就行了

BZOJ1459 网格图的模型 因为限制是至少而且要求最少不好做 所以直接反向考虑 假设放满然后考虑拿掉士兵 限制就变成了至多求的答案也变成最大 直接最大流就行了

BZOJ3438 最大权闭合子图 因为是两个集合所以考虑先都放在其中一个集合 然后考虑将其中一个元素放到另一个集合增加的收益看成点权 再将子集的限制条件拆成两个考虑就行了

BZOJ1834 先最大流 然后增加一个汇点将原来的汇点向新的汇点连一个容量为ans+k费用为0的边 再把每条边的扩容费用加上去跑一遍费用流就行了

BZOJ1305 先二分，然后考虑怎样建图判断合法 拆点，把一个人拆成‘和喜欢的人跳舞的人’和‘和不喜欢的人跳舞的人’，然后和喜欢的人就在两个第一种点间连边，否则就在两个第二种点间连边，每个人的两种点之间连流量为k的边，源点或汇点和第一种点之间连流量为二分出来的值的边，最大流验证是否满流就行了

BZOJ1324 一个有权值的棋盘，一个格子取了相邻的格子就不能取 于是把整个棋盘黑白染色 然后分别和源点和汇点连容量为权值的边 相邻格子连容量为INF的边 总权值-最小割就是答案

BZOJ1189 我给BZOJ加的数据 还能说啥呢 跳过

BZOJ2929 根据题意直接建边网络流

BZOJ3275 奇数不满足条件1 偶数不满足条件2 直接二分图最小割就行了

BZOJ1433 考虑把床位和人当成两边的点 直接二分图最大匹配就行

BZOJ2400 每一位分开考虑 如果点权确定那么根据是0还是1向S和T连边 然后原图中相邻点间连INF的边 跑最小割就行了 因为同时还要点权最小所以把边权扩大10000倍 再把所有不和S相连的未确定点连向S流量为1的边 这个时候的最小割/10000为最小边权 %10000位最小点权

BZOJ1266 先算出最短路找到最短路图 然后把代价加上去跑最小割就行了

感觉要复习不完了加快一点吧

BZOJ2127 讨论一下两个人选的科目 然后建边最小割

BZOJ2039 讨论一下雇佣情况 建边最小割 注意边集很大要先把重边的流量合并

BZOJ2132 注意收益和代价的是同号的 所以需要黑白染色把其中一个颜色的ST反向 这样才能用最小割表示同号的收益代价

BZOJ3894 和3438很像的子集建模 讨论一下文理建边 然后最小割

BZOJ2095 二分最大边权 然后就是混合图欧拉回路存在性判定 给每个边定向然后流就看成边反向就行了

BZOJ1570 按照题意枚举天数边建图边跑最大流就行了 如果能到终点的超过T个人就输出答案

BZOJ3903 2400简化版 拆位最小割就行

BZOJ3931 按照题意Dijkstra+网络流就行了

BZOJ3993 二分+最小割裸模型

BZOJ3996 很妙的题 把矩阵拆开，A中每一个数是0还是1就表示是否选一个物品 B中的值就是同时选两个物品的收益 C中的值就是每个物品的代价 最小割即可

BZOJ3774 注意一个点的四周如果都被选择那么这个点就不用选了 拆点建图最小割即可

复习完毕

Dijkstra：

BZOJ3931 同上

BZOJ2007 平面图转对偶图 最小割变成最短路 直接跑就行了

BZOJ3040 直接系统push_heap pop_heap (听说就是用pairing_heap写的？)

BZOJ2725 先求出最短路和最短路径上的每一条边 然后枚举边用线段树更新一下最后扫一遍查询答案就行了

BZOJ2069 最短路可以分成1→和1相邻点a→和1相邻点b→1 就相当于把和1相邻的点看成关键点 然后要求这些关键点之间的最短路 直接二进制分组最短路就行咯

BZOJ2118 @WC2016 取一个a_i当模数 然后用模a_i的值当点 用其他a_i当边 从0开始跑最短路 然后用最短路的结果算出答案就行了 (感谢trz指点)

复习完毕

对偶图：

BZOJ2007 同上

BZOJ3007 先二分答案，然后每个点变成了圆，就相当于判断左上右下是否被圆接在一起，直接连边BFS就行

BZOJ2960 对偶图之后裸的朱刘算法

复习完毕

树链剖分：

BZOJ2243 树剖之后变成区间染色以及区间查询颜色数 线段树记一下区间颜色数以及左右端点颜色就行了

BZOJ3626 首先答案可以转换成 [l,r]中的每一个点，将他们到根的路径上的点权+1 然后查询z到根的路径点权和就是答案 那么可以把询问差分拆成[1,l)和[1,r]，离线用树剖统计答案即可

BZOJ3083 直接树剖不管换根 询问的时候讨论一下根和x的位置关系统计答案即可 注意要处理x就是根的情况

BZOJ2819 树剖之后直接维护异或和就行了 但是这个题要的是异或所以更简单 用糖果公园那种思想DFS序+树状数组就行啦 不要忘了还要处理一下LCA

BZOJ3631 裸树剖 当然其实没这么麻烦可以差分一下打个标记直接DFS就行啦

7月12日

BZOJ3589 求的是链的并集 所以容斥一下 答案=单链答案-两条链交集的答案+三条链交集的答案... 每一个部分直接树剖算就行了

BZOJ1984 边权的操作和询问 直接下放到点权树剖就行了

BZOJ3531 直接树剖 每个颜色建一个线段树 不要建满直接动态开点就行了

BZOJ2836 树剖裸题 (辣鸡p妈树剖居然不能1A，我今天模拟赛就1A了)

BZOJ2402 强行把数列上的题目放到树上 先二分答案，推推公式发现求的东西可以斜率优化 就用线段树维护一下凸包 然后在凸包上二分查询就行了 4个log你怕不怕

BZOJ4127 保证加的数非负 所以负数变成正数只有n次 线段树记一下区间最大负数就行啦

复习完毕

LCA：

BZOJ1977 严格次小生成树 在求LCA的时候记录一下严格次小边权就行啦

BZOJ3732 货车运输·改 直接Kruskal搞出最小生成树然后LCA记录个最大边权就好了

BZOJ2588 每个节点记录一个到根的可持久化线段树 然后用主席树的思想作差就行了 Tree_ans=Tree_x+Tree_y-Tree_lca-Tree_fa_lca

BZOJ3123 同上一题 只不过需要加一个启发式合并罢了

BZOJ1787 答案肯定是在其中两个点的LCA中选 所以枚举是哪两个点求个LCA就好了

BZOJ2791 定义一个点走到环上第一个点为根 那么如果两个点的根相同答案就是LCA 否则就是两个根之一 枚举一下算算就行

BZOJ4082 拆环倍增 把所有区间搞成两个 然后每个点向和自己相交右端点最远的区间连一条边 倍增求出最少几次能走完环更新答案即可 (辣鸡p妈这和LCA有个毛线关系)

复习完毕

Kruskal：

BZOJ1977 同上

BZOJ3732 同上

BZOJ1016 先Kruskal求出出现在最小生成树上的权值的出现次数 然后对于每种权值求出对答案的贡献乘到答案上 然后把这个权值连接的联通块缩点就行了

BZOJ3714 差分一下 每次查询得到的相当于是两个前缀之间的奇偶性关系 那么题目就相当于要在一个完全图中找一个最小生成树

BZOJ2594 反着做 先求出没有删掉的边的最小生成树然后就相当于维护动态加边的最小生成树 LCT就行了

BZOJ3551 Kruskal重构树 好神奇的东西(刚做过的某CC题也用到了这个东西来着) 在求最小生成树的时候不加边，而是加一个新点连向代表两个联通块的点 并用这个点带表新的联通块 然后在新的图中求出DFS序(只包含原来点) 那么某个点出发的经过的边边权小于某个值的联通块 就对应了一个DFS序区间 于是直接主席树就行了

BZOJ3732 辣鸡p妈居然靠高端算法混rank1= = 用重构树的思想 在求最小生成树的时候将两个并查集的端点按秩合并(相当于直接改变树的形态) 于是直接暴力往上爬就能算出答案了 (加了倍增就loglogn了)

BZOJ1196 二分答案 然后每次先看能不能连上k条一级边再看剩下的二级边能不能连通

BZOJ1821 答案就是最小生成树的第n-k+1条边的边权

BZOJ2654 给所有白边加一个权值 限制白边能选的个数范围 当白边能选的个数范围包含need的时候输出答案即可

复习完毕

Floyd：

BZOJ1266 同上

BZOJ1027 先去掉一维 然后抽象成一个点 一些点能合成的点在这些点的凸包内 那么题目就相当于选一些A中的点使得这些点的凸包包含所有B中的点 而且要选的最少 那么直接把能包含所有B的边记下来 然后Floyd求出最小环即可

BZOJ2788 差分约束建图 然后Floyd求出最短路判定是否无解 再把强连通分量缩一下 强连通分量之间相互独立 每个强连通分量的答案等于两两最短路的最大值+1

(剩下的倍增Floyd到后面再学)

复习完毕

复习不完了我要死了

容斥：

BZOJ3589 同上

BZOJ2005 设$f_i$表示gcd=i的数对个数 则$f_i=\lfloor\frac{n}{i}\rfloor\times\lfloor\frac{m}{i}\rfloor-\sum_{k=1}^{k\times i\leq min(n,m)}f[k\times i]$ 从后往前枚举计算答案就行了

BZOJ1042 很妙的容斥 首先如果不限定个数可以直接背包 限定的话就容斥一下 答案=不限定的方案数-1超出，其他不限定的方案数-2超出，其他不限定的方案数-... 但是超出的方案数怎么算呢？ 直接强制先把(限定个数+1)个硬币拿掉就相当于不限定了丫

7月13日

啊啊啊啊啊啊啊啊啊啊啊头好疼啊

BZOJ2393 好妙的题 首先找出所有由2和9构成的数 然后找出这个数集中不被其他在数集中的数整除的数 再直接容斥就行了 不用担心复杂度 LCM很快就会超过R所以有用的状态其实很少 1s之内就可以出解

BZOJ1853 同2393 因为R<=1e10 所以LCM可能会爆long long 那么计算LCM的时候用long double比较大概大小 如果比R小再用long long存就行了

BZOJ3198 恰好k个位置相同的对数=至少k个位置相同的对数*C(k,k)-至少k+1个位置相同的对数*C(k+1,k)+... 至少若干个位置相同的对数直接hash就行了

BZOJ3622 考虑直接DP 首先把所有a,b排序 f[i][j]表示前i个位置有j个a比b大的方案数 那么先求出mx[i]表示最多有多少个b比a[i]小 则f[i][j]=f[i-1][j]+f[i-1][j-1]*(mx[i]-j+1) 但是这样做是有问题的 因为f数组没有考虑到剩下的位置 所以容斥一下把重复的减掉就可以啦 g[i]表示恰好有i个a比b大的答案 则$g_i=f_{n,i}\times(n-i)!-\sum_{j=i+1}^{n}g_j\times C_{j}^{i}$

BZOJ2839 考虑容斥 那么就只需要算出交集至少为i的集合的集合有多少个 首先选出i个元素 然后剩下的$2^{n-i}$种集合可选可不选 则答案为$\sum_{i=k}^{n}(-1)^{i-k}\times C_{i}^{k}\times C_{n}^{i}\times(2^{2^{n-i}}-1)$

BZOJ2024 同3622 多一个高精度而已

BZOJ2669 首先最多只有8个局部最小值 所以可以状压DP 考虑把数字从小到大填进去 用$g_i$表示局部最小值填充状态为i的情况下 剩下有多少个位置可以填 设$f_{i,j}$为填了前i个数字局部最小值填充状态为j的方案数 则$f_{i,j}=f_{i-1,j}\times(g_j-i+1)+\sum_{k\in j}f_{i-1,j-\{k\}}$ 但是这样做会让一些不该是局部最小值的点成为局部最小值 所以枚举一下成为新的局部最小值的点容斥一下就行了

复习完毕

分块：

BZOJ2741 考虑求出前缀异或和 则题目转换为区间内两个数的异或最大值 那么可以分块并对每一块的块首求出到后面每一个位置的答案 这样的话对于每一个询问只需要求出左端点到第一个块首的答案就行了 这个直接可持久化Trie树就行咯

BZOJ2002 直接对弹簧分块 每个弹簧求出弹出自己的块需要的次数以及落点 询问直接询问到弹出去就行 修改只用改从块首改到自己的位置就行了

BZOJ2821 分块 然后预处理出第i到j个整块的答案以及每个块中每个数出现次数的前缀和 询问先记下整块答案 再用两边多出来的东西调整答案就行了

BZOJ2141 先离散化 然后分块每个块维护一个树状数组 交换两个数之后讨论一下块内树状数组查询块外暴力就行了

BZOJ3343 修改的时候中间块打标记 两边暴力修改之后重建 查询的时候中间块二分 两边暴力查询 当然这题还有黑科技的做法 因为q<=3000所以直接把整个序列离散化 离散化成2q个段之后每次暴力二分询问每一段就行了

BZOJ2038 这题我是大视野第一啊 不用说了 跳过

BZOJ3289 莫队 树状数组维护一下 没了= = 莫队大师QwX

BZOJ3744 分块 算出每一个块首到后面每一个点的逆序对总数 询问的时候左端点到下一个块首直接可持久化线段树求 加上预处理的答案就行了

BZOJ2738 很妙的分块 把n*n个数分n次插入 每次插完后查询剩下的询问 如果询问的矩形中已经超过k个数那么答案在这n个数中 直接暴力查找就行了

BZOJ3720 树分块 分完之后相当于块之间的关系从链变成了树 直接做就行了

BZOJ3731 同3720 加了一个块的分裂操作而已

BZOJ3758 分块打表 分成1000个块每个块算一个答案 剩下1e6的零散部分暴力就行了

BZOJ3798 同3758 分成3000块每个块算个答案 剩下的暴力

BZOJ3787 3744加上一个修改操作 分块并预处理出块与块之间的答案 以及前i块等于j的个数和前i块小于j的个数 修改的时候把这三个都改改就行 查询到时候整块和整块的答案直接用预处理 零散和整块的部分枚举零散的部分用预处理算出答案 零散和零散的部分直接放在一起用树状数组做一遍就行了

BZOJ2957 首先求出到原点的斜率 就相当于求一个从原点出发一直上升的序列 分块然后每个块维护一个从第一个位置出发的单调上升子序列 修改的时候直接重建所在块 查询的时候每一个块二分第一个大于当前最大值的位置 然后更新一下当前最大值一直扫下去就行了

BZOJ3809 考虑莫队 如果用树状数组维护 修改和查询都是1个log的 显然过不了 所以考虑直接用分块维护 这样虽然查询变成根号的 但是修改是O(1) 那么总复杂度就变成O(msqrt(n))啦

BZOJ1086 树分块入门题 直接打一个树分块就行啦~

BZOJ3585 同3809 修改O(1) 查询的时候扫到第一个没有被完全覆盖的块，再在块里面找到第一个没有标记的数就行了O(sqrt(n))

BZOJ4129 啊这个题我也是大视野第一啊 和糖果公园以及mex一样 搞成链然后看成三个维度的莫队搞搞就行啦

复习完毕

7月14日

递推：

BZOJ1002 递推个头啊 直接基尔霍夫矩阵+高精度就行啦

BZOJ1011 因为精度误差要求不严所以可以先暴力算出靠近的一部分 剩下的用前面一段的结果来近似一下就行了

BZOJ2431 考虑把所有数从1到n插进去 f[i][j]表示前i个数有j个逆序对的方案数 则第i个数可以造成0~i-1个逆序对 即$f_{i,j}=\sum_{k=j-i+1}^{j}f_{i-1,k}$ 维护一下前缀和就行了

复习不完了要加速了

BZOJ1801 题目等价于每一行每一列有最多只有两个炮 f[i][j][k]表示前i行有j列有一个炮k列有两个炮 分类讨论转移就行了

BZOJ3823 f[i][j]表示i维立方体j维元素的个数 推推公式可以发现f[i][j]=2^(i-j)*C(i,j) 于是f[n][i]=f[n][i+1]*2*(i+1)/(n-i) 直接递推即可

BZOJ1197 f[i][j]表示i维空间j个球最多分成几份 则f[i][0]=1 f[0][i]=2(i!=0) f[i][j]=f[i][j-1]+f[i-1][j-1] 直接递推

BZOJ3612 f[i][j]表示i分成j个不同的数且最大的不超过k的方案数 则f[i][j]=f[i-j][j]+f[i-j][j-1]-f[i-k-1][j-1] 然后枚举一下是否取中点 再枚举左右力矩和以及拿走的点数直接算就行了

BZOJ2786 f[i][j]表示i个数划分成j个有序集合的方案数 讨论一下划分方法 则f[i][j]=(f[i-1][j-1]+f[i-1][j])*j

POJ1737 枚举1号节点联通块大小容斥一下 $f_i=2^{\frac{i(i-1)}{2}}-\sum_{j=1}^{i-1}C_{i-1}^{j-1}\times f_j\times2^{\frac{(i-j)(i-j-1)}{2}}$

复习完毕

Hash：

BZOJ3198 同上

BZOJ3555 枚举不同的位置 直接Hash

BZOJ3207 Hash之后变成区间找有没有一个数的问题 直接主席树即可

BZOJ1014 平衡树维护一下区间Hash值即可

BZOJ1567 二分答案 然后把其中一个矩阵的子正方形Hash 用另一个矩阵的子正方形Hash值去找有没有相等的即可

BZOJ1414 先把矩形扩大一倍 然后从四个方向Hash 对于每个点二分答案用四个值验证即可

BZOJ2351 同1567 直接二维Hash就行了

BZOJ1170 同2351 二维Hash然后排序统计答案即可

BZOJ3790 Hash+二分(其实应该Manachar)搞出所有回文串 然后就相当给一些区间要最少的区间覆盖整个串 排序之后直接树状数组即可

BZOJ2795 循环节一定是串长以及所有字符出现次数的约数 所以求个gcd然后枚举gcd的约数 Hash验证一下就行了

BZOJ2258 同1014 平衡树维护Hash值即可

BZOJ1090 区间DP 然后循环节用Hash判断一下即可

BZOJ3162 直接DP 然后DP的时候树Hash判掉相同子树就行了

BZOJ3197 首先还是树Hash的思想 然后枚举深度和Hash值相同的点转移 转移的时候用KM优化一下就行了

BZOJ2565 Hash+二分搞出所有回文串 然后枚举第二个回文串中间点维护一下后缀min求出最左边的回文串中间点就行了

BZOJ2081 直接枚举k然后Hash判断就好了 翻转同构就乘上反串Hash值就行了

BZOJ1125 先Hash然后就是千山鸟飞绝 Treap即可

BZOJ1142 求出整个矩阵的按序Hash值然后判断一下就行啦

BZOJ3899 仙人掌同构 大概就是在树同构的基础上加个KMP判断

复习完毕

二分：

BZOJ3790 同上

BZOJ1012 单调栈+二分 其实还可以用并查集实现 这样复杂度只有O(n*alpha(n))

7月15日

BZOJ1014 同上

BZOJ1567 同上

BZOJ1414 同上

BZOJ1305 同上

BZOJ1196 同上

BZOJ2654 同上

BZOJ2402 同上

BZOJ3007 同上

BZOJ2095 同上

BZOJ2565 同上

BZOJ1189 同上

BZOJ3993 同上

BZOJ2876 用拉格朗日乘数法搞一搞就发现是可以二分的 然后二分方程的答案判定就行了

BZOJ1213 二分答案 然后高精度验证

BZOJ3885 先悬线法搞出最大子矩形 然后二分一下消掉每个最大子矩形周围没有点的部分

BZOJ3695 每次用相邻点的位置二分确定自己的位置 然后多次迭代就可以拟合出最佳位置了

BZOJ4282 很明显所有N都能在最优解中 那么把每个K拎出来 减去前面N的个数 用二分求个LIS加上总共N的个数就是答案

POJ3208 二分答案 然后问题就相当于一个数位DP 预处理一下每一位的情况直接搞就行

BZOJ2097 二分答案 验证的时候删掉会让结果超过答案的边 最后看有没有删超过k条就行了

BZOJ2653 二分答案 然后把序列中大于二分的值的看成1 否则看成-1 如果区间和大于等于0则可行 因为要的是大于某个权值的状态所以用可持久化线段树就行啦

BZOJ1052 先二分正方形边长 然后注意到正方形一定摆在最小覆盖所有点的矩形的四个角落之一 所以O(4^3)暴搜枚举一下就行了(其实是O(4^2))

BZOJ1044 第一问直接二分 第二问DP然后用前缀和+指针优化一下就行了

BZOJ1758 先二分答案然后把边权减掉二分的值 就相当于给一棵树求长度在某个区间内的大于0的路径是否存在 直接点分就行了 求答案用单调队列即可

BZOJ1486 二分答案之后从权值里减掉二分的值 题目转化为求是否存在负权环 从每个点出发直接DFS即可

BZOJ3316 先把环倍长 二分答案然后用单调队列验证 因为长度要是偶数所以奇偶分开用两个单调队列维护即可

BZOJ3613 二分答案之后 如果当前数字小于右边的数字 就向上调整到极限 否则向下调整到极限 如果到了极限都满足不了就说明答案不合法 然而答案就等于最大的逆序对差值 直接扫一遍就行了

BZOJ2525 二分答案然后直接树形贪心验证就行了

BZOJ4077 二分答案然后让B先走二分的值 最后看A和B全程的最短距离差是否小于等于二分的值就行了

BZOJ2280 卡OJ神题！ 二分答案然后用随机增量法判断就行了

BZOJ2782 二分答案之后先把相邻的差都缩小到二分的值以内 然后枚举哪个位置变成0 边枚举边维护要改的区间就行了

复习完毕

记忆化搜索：

BZOJ1415 首先SPFA求出可可在每个位置的时候聪聪会怎么走 然后记忆化搜索枚举一下可可走的方法就行了

BZOJ3628 直接记一下状态记忆化搜索就行了

BZOJ3769 记一下点数和深度记忆化搜索即可

BZOJ2656 高精度+记忆化搜索即可

BZOJ3208 记一下位置直接搜就行了

BZOJ3895 记一下大小为1的堆的个数以及剩下堆的操作数即可

复习完毕

莫队算法：

BZOJ3585 同上

BZOJ4129 同上

BZOJ3809 同上

BZOJ3289 同上

BZOJ2038 同上

BZOJ3052 分块把树变成序列然后直接莫队就行了 修改和询问都是O(1)的 注意处理一下LCA就行了

BZOJ3757 同3052 我都不知道该怎么讲了

BZOJ1878 搞个扫描线 然后树状数组维护扫描线右边每个数出现的第一个位置就行了 当然直接莫队也是可以的

BZOJ3781 莫队然后。。。。暴力维护一下？ 真心不知道莫队怎么讲

BZOJ2589 强制在线莫队啊 大概就是把整个序列划分成若干块 然后预处理出两个整块之间的莫队状态 然后查询用最近的一个整块爬到当前的左右端点就行了

复习完毕

整体二分：

BZOJ2738 每层算出小于等于某个值的点在每个询问中出现多少次 然后分治到下一层算就行了

BZOJ2527 每层算出当前操作数每个国家的答案 然后根据答案和需要值来分支到下一层就行了

复习完毕

扫描线：

BZOJ1845 按照所有出现过的x坐标把整个图形分成若干份 每一份都是梯形取个中位线算算长度就行了

BZOJ4059 每个元素的贡献是一个矩形 要求的是所有矩形的并是否覆盖整个大矩形 那么直接扫描线+线段树即可

复习完毕

7月16日

开启高速复习模式

凸包：

BZOJ2402 同上

BZOJ3675 斜率优化 插入的点单调 查询单调所以直接单调队列维护凸包即可

BZOJ1492 斜率优化 平衡树维护凸包即可 当然也可以用CDQ合并凸包做

BZOJ3672 先点分 然后斜率优化 插入单调询问无序所以在凸包上二分即可

BZOJ2300 直接平衡树维护凸包 (p妈你怎么凸包都是捎上平衡树的啊这么可怕)

BZOJ2823 数据随机所以凸包上没几个点 求出凸包直接暴力最小圆覆盖即可

BZOJ2961 CDQ分治维护凸包即可

啊受不了了直接写题号好了

BZOJ2146 直接拆分暴力枚举 BZOJ3203 凸包上三分 BZOJ3533 二进制分组然后凸包上三分

复习完毕(强行)

Simpson：

BZOJ2178 求出圆截取区间并然后Simpson BZOJ1502 求出圆和公切线组成的多边形的截取区间Simpson

复习完毕

斜率优化：

BZOJ1492 BZOJ3672 BZOJ3675 BZOJ2402 同上

BZOJ1096 插入递增询问递增直接单调队列 BZOJ4073 连续贪心离散斜率优化插入递增询问无序单调栈+二分

复习完毕(好快啊)

树形DP：

BZOJ2097 BZOJ3162 BZOJ2525 同上

BZOJ1040 分类讨论然后在基环森林上DP BZOJ3037 同1040 BZOJ1131 边DFS边DP更新答案 BZOJ2657 转对偶图然后求直径 其实可以直接两遍BFS

BZOJ3727 DP一下然后可以列出方程 求出方程系数直接解就行了 BZOJ2152 可以直接点分统计 也可以直接记一下距离直接DP BZOJ1060 直接把每个节点连下去的边补齐即可

BZOJ1023 缩个点双然后DP 用单调队列处理一下环即可 BZOJ3566 分类讨论然后期望DP BZOJ2314 最小支配集 DP然后统计一下方案数

BZOJ1907 最小路径覆盖 分类讨论一下路径情况然后DP BZOJ2500 第一问直接两遍DP然后记一个次小值去重 第二问直接单调队列 BZOJ3829 贪心决定走哪一条边然后DP即可

BZOJ1123 求点双然后变成一棵树直接DP BZOJ4013 用组合数算一算然后DP统计答案即可 BZOJ4316 先建新点去掉环 然后处理出环外情况 剩下的同1040

BZOJ4027 直接贪心(mdzz贪心为啥扔个DP的tag啊辣鸡p妈) BZOJ3004 如果k满足条件那么至少有n/k个节点满足子树大小是k的倍数 所以直接DP出size然后枚举k验证

BZOJ4033 枚举一下每个节点有多少个黑色点然后直接DP就行了

复习完毕

树状数组：

BZOJ2819 BZOJ3289 BZOJ2141 BZOJ3744 BZOJ3787 BZOJ3790 BZOJ1878 BZOJ2738 同上

BZOJ3295 CDQ分治然后每一层用树状数组求 BZOJ3262 三维偏序CDQ掉一维剩下两维枚举一维树状数组一维即可 BZOJ1176 带修改矩形和CDQ掉一维枚举一维树状数组一维同3262

BZOJ1264 记录下每个数出现的位置然后树状数组优化DP BZOJ3211 一个数最多开根loglog次所以用并查集维护一下当前能用的然后树状数组维护数列和即可 BZOJ3038 同3211

BZOJ1901 用树状数组维护可持久化线段树 然后询问的时候拉出log颗树直接作差即可 BZOJ3333 树状数组统计逆序对线段树维护区间最小值即可 BZOJ2743 扫描线+树状数组

BZOJ2762 转换一下相当于区间加值单点查询 树状数组维护即可 BZOJ1935 询问拆成四个 然后扫描线+树状数组 BZOJ2683 同1176 BZOJ3881 同2762 注意要求LCA

BZOJ2434 建AC自动机搞出fail树的DFS序 问题转化为查询区间内一类数的计数 直接树状数组即可 BZOJ3173 平衡树搞出插入后的数列然后树状数组求出LIS

BZOJ2789 树状数组求出逆序对即可 BZOJ1109 看起来像是三维偏序 其实有一维是另两维可以推出来的所以变成二维偏序树状数组求即可 BZOJ3594 三维偏序二维树状数组即可

BZOJ1818 离线下来然后横着看插入竖着看成查询直接扫描线+树状数组即可 BZOJ1107 转成LIS树状数组即可 BZOJ2244 第一问CDQ 第二问分层DP 每一层用CDQ算算就行了

BZOJ4009 首先枚举一下DFS序的情况然后转化成二维矩形内k大点 然后直接整体二分即可 当然也可以树套树做 还可以分类讨论主席树+KDT做

复习完毕

替罪羊树：

BZOJ3065 替罪羊套Treap BZOJ3217 替罪羊套Trie BZOJ3435 替罪羊思想+动态点分治再套个平衡树

复习完毕(简单粗暴)

KDT：

BZOJ1941 裸KDT求曼哈顿最小最大距离 BZOJ2648 同1941直接KDT

复习完毕

并查集：

BZOJ3211 BZOJ3038 同上

BZOJ3362 带权并查集维护曼哈顿距离 BZOJ1015 离线倒叙直接并查集 BZOJ1854 并查集维护一下当前联通块有没有环即可 BZOJ3565 神TM强制在线直接倒推最后并查集即可

BZOJ1202 并查集维护一下边权 BZOJ1370 拆点并查集判断 BZOJ2079 并查集维护联通块大小 BZOJ3454 用并查集来代替暴力枚举维护权值和 BZOJ1116 同1854

7月17日

BZOJ3562 把不会删的边用并查集缩起来然后暴力 BZOJ1098 直接在反图上DFS然后用并查集优化DFS过程即可 BZOJ2054 反着做每个点第一次被染色才是有用的同3211

BZOJ3319 每个点记自己第一个黑色祖先的深度，每个点染黑用线段树区间取max即可 然后用并查集加快一下找白点过程 BZOJ1104 枚举高度然后用并查集维护当前是否有水泵

BZOJ4025 分治 然后如果边恰好在当前时间段就加入并查集 如果出现奇环则这一段时间都不存在二分图 否则讨论和mid的关系传下去继续做 回溯还原操作即可(不能路径压缩)

BZOJ1529 答案等于联通块个数所以直接并查集维护即可 BZOJ4320 对模数分块 小的用数组直接存 大的反过来用3211的方法维护即可

BZOJ2503 并查集维护一下联通块度数的奇偶性然后分类讨论 BZOJ2959 考虑静态的情况下 就是缩边双然后求路径和 既然是动态那么LCT维护连通并查集维护边双即可

复习完毕

线段树：

BZOJ1012 BZOJ1901 BZOJ3333 BZOJ3065 BZOJ3319 BZOJ3533 同上

BZOJ1858 裸线段树 BZOJ3196 线段树套Treap BZOJ1798 裸线段树 BZOJ3685 裸线段树 BZOJ3747 扫描线+线段树 BZOJ3489 mex树套树或莫队或扫描线+线段树都可以

BZOJ3813 线段树+bitset维护欧拉函数 BZOJ2877 对中间差分然后分类讨论直接上二维线段树 BZOJ3165 超哥线段树维护一下凸包即可 BZOJ2962 直接线段树维护20个值即可

BZOJ3878 把所有询问排序用一个线段树一起做即可 BZOJ1018 线段树维护一下两行之间连通性即可 然后最开始先走到能走到的最左边和最右边这样要用的边就在中间了

BZOJ3904 DP然后线段树优化一下即可

计划要打的题

BZOJ3551

突然发现不会的东西

BZOJ2229 最小割树不怎么会

BZOJ2502 最小流也不会

BZOJ2286&3611 好神的模拟DFS (怎么感觉这玩意儿这么像虚树啊日这TM就是虚树)

BZOJ2038 啊这个题我不是全大视野最快嘛MMST不会

BZOJ3812 看了不知道多少遍都没有看懂的题

BZOJ2803 不太看得懂题解QAQ 好像是类似Manachar的东西

BZOJ1563 四边形不等式不会