错误总结、套路集锦
常识
标准差是方差的算术平方根，所以说所谓方差是不需要开根的
cmp函数不能在结构体内部
注意！multiset的count复杂度和对应元素数量相关
注意！set等非随机访问结构的lower_bound，必须调用结构内部的，用stl的那个函数会一次O(n)但不会报错
在无c++11的时候，queue系列的swap是o(n)的
stable_sort在一些交互题中很好用（sort会在较小的地方用插入排序）
错误总结
不等式的移项 一定要分析正负性
stl的比较重载不能随便搞，一定要满足传递性和大小情况单一性（stl用<和>推导出=）。例如在cmp里写>=这种东西会re
fft得答案时要round
带取模计数，判无解不能用答案=0，因为答案可能是模数的倍数。特别是一些模数在输入给出的题，特别好构造
注意 s&bin[i] 和 (s&bin[i])>0 的不同（惯犯
用指针a[]表示数组的时候，sizeof a只会得到单位大小，而不是整个数组的大小
如果一个东西的插入复杂度是通过势能分析保证的（如sam、朴素pam、ac自动机），那么通常不能支持删除操作，因为可以多次进行再回撤高复杂度的操作
线段树如果值域int，求mid的时候可能爆int；另外区间范围涉及负数的时候，
mid=(l+r)/2会有取整方向问题，导致RE在CF的在线比赛时，任何自选模数的题都应该rand或者双模数，例如路径关键点、hash
我习惯定义的循环宏fo，注意循环变量是ll的情况
感觉自己经常在想题过程中把题意扭曲了……以后如果卡住了要再三检查前面的题意转化是否出问题
计数等题经常会出现等比数列，记得判公比为1的情况
经常写着写着忘记，点分治最外面那次也要找重心……
以后一些以为想清楚的不会发生/必定发生的情况，也要写个assert
做数论题的常用姿势
调和级数，$\sum_{i=1}^n n/i=O(n*ln(n))$，所以像$g(n)=\sum_{d\mid n}f(d)$这类较简单狄利克雷卷积无脑做是一个log的，但可以更快，类似高维前缀和的思想做。复杂度$=O( \sum \frac{n}{prm_i}=所有数的质因子个数和 )=O(n*log_2(log_2 n))$
1fo(i,1,prn) fo(j,1,N/prm[i]) f[j*prm[i]]+=f[j];关于约数，一个数num的约数可以$O(\sqrt{num})$枚举，可见约数个数上界为$2\sqrt{num}$；如果枚举一个数的倍数就是调和级数的复杂度，可见n内所有数的约数个数和上界为$O(n*ln(n))$；很多时候会分析一个数的不同质因子数量（通过$2*3*5…>num$），典型题目
phi小性质：「对于n>1，1~n中与n互质的数的和为$n \times \varphi(n)/2$ ，证明：$gcd(n,x)=gcd(n,n-x)$」、「深度为log级别。考虑n为偶数，则$\varphi(n)\le n/2$；若n为奇数，$\varphi(n)$一定是偶数」；一个显然正确的式子：$\varphi(ab)=\frac{\varphi(a)\varphi(b)d}{\varphi(d)}(d=gcd(a,b))$
关于整除：「$当x \le \sqrt n,\left \lfloor \frac{n}{\left \lfloor \frac{n}{x} \right \rfloor} \right \rfloor=x$」、「$\forall a,b,c\in\mathbb{Z},\left\lfloor\frac{a}{bc}\right\rfloor=\left\lfloor\frac{\left\lfloor\frac{a}{b}\right\rfloor}{c}\right\rfloor$」、「数论分块，将$\lfloor \frac{n}{i} \rfloor$相同的i合并起来计算，不同个数是$O(\sqrt n)$的，因为当值比根号大时，分母一定在根号内」
第二条的证明：
$$
\begin{split}
&\frac{a}{b}=\left\lfloor\frac{a}{b}\right\rfloor+r(0\leq r<1)\ \Rightarrow \ &\left\lfloor\frac{a}{bc}\right\rfloor =\left\lfloor\frac{a}{b}\cdot\frac{1}{c}\right\rfloor =\left\lfloor \frac{1}{c}\left(\left\lfloor\frac{a}{b}\right\rfloor+r\right)\right\rfloor =\left\lfloor \frac{\left\lfloor\frac{a}{b}\right\rfloor}{c} +\frac{r}{c}\right\rfloor =\left\lfloor \frac{\left\lfloor\frac{a}{b}\right\rfloor}{c}\right\rfloor\ \end{split}
$$
$\sum_{i=1}^n d(i)^2约为nlog^2n$（毫无数学依据）
x不断对「<x」的数取模，只会进行$O(logn)$ 次，因为每次做完的结果总是不超过x/2
对于$\prod_{\sum x_i=S} x_i或\prod_{\sum x_i=S} x_i^k$这样的东西，不管在树上还是序列上，可以考虑其组合意义：每个块内恰放k个球。于是可以边走边放，记录当前所在的块内有多少个球，然后在位置上看要不要放，在间隔看要不要放隔板。
$gcd(x_1,x_2…x_n)=gcd(x_1,x_2-x_1,….,x_n-x_{n-1})$，经典问题就是区间加法求区间gcd
有时候会碰到些奇怪的模数导致某数z没有逆元，如果答案一定是整数的话，可以考虑先所有数放大z倍（即先按这个算，而且模数也要放大z倍），最后模出来的结果一定是z的倍数，直接除掉
根据wolframalpha，$O(\sum_{i=1}^n \frac{1}{i^{1.5}})=O(1)$，
看起来很帅
数学
期望有个套路的转化，恰好到达的状态的概率*步数之和，等价于所有未到达的状态的概率之和，这个可以通过「把当前概率推到上面的步数个祖先上」理解
若$H*W且gcd(H,W)=1$的网格左下角射出$(0,0)\to(1,1)$的光线，碰到边框就反射，则$\forall x,y \in N,(x+y)\%2=0,(x,y)会被经过$，其中不在边框上的点会被经过多次，且上述结论是充要的
一个1到n的集合，选若干个不互质的数，要求和最大；bzoj3308
结论：选出的每个数最多两个不同的质因子，且一个在根号n内，一个在根号n外，并不会证明思维僵化如我，$O(n)$求n个数的逆元，类似递推求阶乘逆元一样，求出$\prod a_i$的逆元再还原出前缀逆元，配合前缀积求出单个逆元有些模型是n个中选k个且k给出，然后最优化一些东西；那么随机一个点作为答案中某点，复杂度中含有k时，我们有时间做n/k次，借助wolfram知错误率极限是$\frac{1}{e}$（其实就是k=1最坏然后用e的定义？），次数乘个5之类的，正确率就足以接受了
树形结构
点分的本质：点分树上点对的LCA一定也在原树两点路径上，可以从这个LCA统计这个路径的信息
然后点分有个小trick，如果处理一个块的复杂度通过根号分治达到$O(B\sqrt B)$，总复杂度为$n*\sum (n/2^i)^{1/2}=n \sqrt n*2\sum \frac{1}{2^i}=O(n\sqrt n)$
直径的性质（在一棵边权非负的树上）：「与该点最远的一定是直径的某个端点」、「直径的中心唯一」、
「每个点的最远点，都一定经过直径的中心」、「改一条边，端点最多变化一个」重心和直径有个类似的结论：在一个点权为0/1的树上考虑带权直径、带权重心，「记下两个不重点集各自的任意一条直径端点，点集并的直径的端点一定能在这四个点中产生」，「记下两个不重点集各自的任意一个重心，点集并的所有重心一定都在这两个重心的路径上」
树上点集的连通块个数=点-边，极度常用；另外将点集搞起来的最小虚树边数=「dfs序排序后成环，相邻两个求路径长度」/2，每条边会被覆盖两次所以一定会整除
很多模型能转化为树形：
A: 互不重叠只包含的区间（最近一个包含作为fa），例如析合树、一些性质题
B: 某个变量只有单一指向（作为fa），这个其实是最常见的，举例：跳跳棋
C: 入栈出栈序列也是可以表示为树形结构的，节点x的子树大小为k，则表示x先入栈，然后子树内的元素为$[x,x+k-1]$ 且都更晚入栈更早出栈，举例：HDU5181 numbers
虚树上（或者给定点集）找到原树某个点的祖先中第一个在虚树上的：第一个祖先肯定是第一个dfs序能包含的节点，且所有祖先的dfs序区间是包含的，等价于找到$dfn_y \leq dfn_x$的y中$dfn_y+siz_y-1$最小的那个，如果能离线最简单的写法是按照dfs序从小到大回答询问，用个int维护合法y中最小右端点来自哪里，这样是线性的；如果强制在线可以线段树上询问$[1,dfn_x]$上最小右端点来自哪里
多个点的lca=dfs序最小和最大点的lca
用可重路径覆盖一棵树的每条边，最小数量为度为1的点数量，向上取整地除2。根据下面经典问题2，那么就是要找到一个点作为根，各个子树叶子数$mx*2 \le sum$，这就是个带权重心；要构造的话，直接用堆模拟没毛病，如果多出来一个，那货随便连一个点就是对的；例题:「BalticOI 2015」网络
用路径交可以判断是否存在一条路径包含某节点：路径$(a,b)与(c,d)$如果有交，一定是$lca(a,c),lca(a,d),lca(b,c),lca(b,d)$中深度最大的两个点间路径
给定一棵树结构，每个点标号成排列，要求每个点的编号比子树其他点小，合法方案个数=$\frac{n!}{\prod siz_i}$，因为某个子树成立的概率是独立的
随机序列的笛卡尔树深度为log（每次期望为分成两半），即上升序列长度为log；笛卡尔树的期望子树大小也是log级别的
树上高斯消元可以线性：将每个方程写成$f(x)=k_x*f(fa)+b_x$的形式，这个从叶子开始就能搞出来，最后$f(rt)=b_{rt}$
bfs序递增加入树上点的话，设$dfn_i,dfn_j<dfn_x$，$若dis_{i,x} \le K,dis_{j,x} \le K则dis_{i,j} \le K$
证明考虑$path_{x,i}和path_{x,j}$的第一个分叉点w且i在w子树内，则$dis_{i,j} \le dis_{x,j} \le K$
图论-其他
对于无向图，一个点双内如果有奇环，那么内部每条边都至少在一个奇环中；
点双内有奇环的充要条件是在dfs搜索树上存在一个「一条非树边+若干树边」组成的奇环；
一个图如果只有奇环，那么只会有简单环，因为两个奇环相交会产生偶环
让拓扑序的逆字典序最小，应建反向边跑大根堆，在AGC001F中用过
无向图的dfs树不会有横叉边，这种边很恶心所以一般随便找个生成树的时候都会优先选择dfs（但是注意，可能会有向下的边，即在返祖边的上面访问这条边）
基环内向树森林修改出边得到一个环的最小步数为孤立环+叶子；策略的话先说一棵基环树，就是将环上每个点a挂的树内所有叶子向下个叶子连接，然后a的上一个点连向a的树得到的叶子链的首部。加入其它孤立环的话，从某个a那里拆就只会增加一次操作。例题：projecteuler522 Hilbert’s Blackout
众所周知森林有$联通块=点-边$，同理仙人掌有$联通块=点-(边-环)$
字符串
如果一个串是双回文串（两个回文串的拼接），一定存在一种分割，满足前面是最长回文前缀或者后面是最长回文后缀
同一个串重复无限次得到串的最长回文子串，如果不是无限长，则最多用两个也能拼起来（三个以上的话，随便画一画就会发现，必须满足自己是个双回文串，一定无限）
决策算法
找前k优的区间，固定一个点后，左边的优秀情况是极值问题。可以用堆维护左边，取出一个位置后把左边区间拆成两半放回去，举例：超级钢琴、树上的路径
对于一些求大小为k最优集合的题目，不妨尝试猜测k一定为k-1的增量，感觉一般都不太好证明，不过可以画一画感受一下有没有反例:D
数据结构
其实k维偏序在k较大时可以考虑bitset做，时间都是$O(kn^2/w)$
做法一：对每个询问维护哪些点在前面所有维都满足条件，考虑这一维时把询问和点排序，递增处理询问，空间是$O(n^2/w)$，时空常数为1。如果空间被gank了但时间充裕，把被询问点分成B次做，这样时间乘B，空间除B
做法二：先预处理出$(i,s)=第i维 \le s的集合$（必须将值离散化成n的排列），然后枚举每个询问做并，这样时空是常数2的$O(kn^2/w)$；优化空间的话，把前面第二维分块，设块大小为T，时间$O(k*\frac{n}{T}*(n/w+T)+qk(n/w+T))$，空间$O(k*\frac{n}{T}*n/w)$。在不太影响时间时取$T=n/w,空间为O(kn)$
所以在卡空间时方法二更优越，方法一的优势大概是好写？
一些突破口
目前碰到处理棘手的删除问题的方法主要有两个，基本都需要离线
一个是倒着做，这个对题目的要求较高；另一个是贪心，离线后按出现时间处理，然后按结束时间贪心
举例：「bzoj4644」经典傻逼题「集训队互测2015」最大异或和、「bzoj5040」航线规划「bzoj4229」选择如果一个式子出现k次方，可能是直接斯特林数或二项式定理处理，如果是建图相关可以差分成2x+1（如WC2007石头剪刀布、学习小组），也可能是考虑组合意义：如果是$某整数变量^k$可以看做在其中恰好放k个球（如蔬菜），如果是类似于$\sum_i (x=i的情况数)=S,求\sum_i (x=i的情况数)^2$，可以看做$\sum_i (\sum_{情况} [x=i])^2=\sum_{情况1} \sum_{情况2} [x_1=x_2]$，这样就跟具体是什么无关了（如NOI2009管道取珠）
很多计数问题要求排列，可以时刻保证排列性，然后插入一个数，将比它大的数+1
举例：51nod1296 有限制的排列、以及一些比较经典的树上dp跟极值有关的区间问题，考虑一下已知存在某个极值贴着区间外所带来的影响（笛卡尔树dp之类的）
举例：HNOI2016序列、HNOI2017影魔、IOI2018会议、noi2019机器人的50分部分分（都有题解）问从状态A操作到B，可以考虑倒着操作，适用于做某种操作可达性、构造
表格图上行和列两侧成二分图，$(i,j)有棋子则i到n+j连边$
求只包含一点、只不包含一点的信息的一类问题
套路大概是分治，大概没法直接说懂，给出两道题，选一道题看，然后大概就能理解并做出另一道题了
假如在序列上有很多区间，但这些区间长度都是L，那么可以对序列按L分块，于是每个区间一定是「某个块一段后缀」+「某个块一段前缀」组成，举例：「LR11」Misaka Network 与 Accelerator
类似地，如果区间长度不定，枚举每种区间长度L做（毕竟块数满足调和级数，只要能把复杂度搞得只与块数有关就好了），例如每个区间都会经过恰好一个关键点，枚举枚举关键点算贡献（计数啥的），举例：「NOI2016」优秀的拆分、股市的预测、poj3693 Maximum repetition substring然后每个串会经过一个关键点，
举例：「NOI2016」优秀的拆分、股市的预测、poj3693 Maximum repetition substring有的问题如果确定一部分，另一部分的限制会很强，可以考虑meet in middle，如CF1257F
很多单点修改维护整体答案的题目，可以考虑转化题意为可并信息（无脑的就是矩乘，有脑的就是自己定义两个结构体的运算），然后用线段树维护
对于n不大或随机算法的题，多多注意能否将大小<i的东西去掉，使得n/=i，优化指数级算法，或者正确概率乘以i
技巧
取模题对拍时，如果暴力能做范围很小，可以改小模数检验
对于比较陌生的题目操作形式，可以多造几组数据来模拟，找到一些性质，用这些性质转化题目
分治的时候判掉l=1可以让$2l>r$，这是一些自己搞自己的分治算法需要考虑、可以加以利用的，如一些分治NTT（例如链式反应）
经典问题
物品权值总和为S的背包，可以$O(S \sqrt S)$完成：只有根号级别的不同权值，每种权值单调队列优化多组背包即可；
另外集合${1,2,..n}的01背包也可以O(wt^{1.5})$完成（整数拆分），就是多加根号wt级别的一维记录使用的数字个数
然后$dp(S,m)$可以从$dp(S-m,m)$整体加1得到，也可以从$dp(S-m,m-1)$即第一个是1
但要注意不能得出比n大的数，综上$dp(S,m)=dp(S-m,m-1)+dp(S-m,m)-dp(S-(n+1),m-1)$若干个不同的集合，要求选最多对数满足来自不同的集合
当$mx>sum-mx$，显然答案为$sum-mx$；
否则只要每次在最大集合中取一个，在其他地方取一个，就能始终保证满足$2mx \le sum$，答案为$\lfloor \frac{sum}{2} \rfloor$；如果每次要k元组，那应该只能用堆模拟了（每次取前k大）？不过有一个不错的式子，反过来对于一个答案W，有哪些k可以至少取到W：$kW \le \sum min(count_{num},W)$，这个的必要性显然，构造证明式子是紧的：先把大于W的那些给W组都丢一个，小的那些选最少的若干个丢一个进去，肯定能搞出W个（其实这样构造的话组的大小只会有A和A+1两种，找A的那些放即可）
最大化长度为n排列的首尾相接时相邻差；最小化这个，可以递增奇数+递减偶数，正确性是显然的。然而值得一提的是，最小化相邻差的平方和（根据$(a-b)^2=a^2+b^2-2ab$，等价于最大化相邻乘积的和）也是这样放（而且能拓展到任意实数序列），证明见[NOI Online 提高组]最小环中EI写的题解，类似的题是loj520「LibreOJ β Round #3」绯色 IOI（开端）
两个凸函数f和g，做$(max,+)卷积，即h_{i+j}=max\ f_i+g_j$，得到的h也是凸函数，证明很简单：$h_{i+j+1}的(i,j)构成，与h_{i+j}的(i,j)构成$，一定能只改变一个，于是可以双指针线性合并
01分数规划，例如最大化平均数，二分判断是否存在$sum-cnt*T>=0$即$\sum (val-T)>=0$
一个数的所有约数的哈斯图的最长反链（定义一个数被另一个数整除时可比）
首先肯定是Dilworth去转成最小链覆盖，然后观察这个图的特性发现这其实每个点$\prod p_i^{k_i}可以看做(k_1,k_2..k_{cnt})$，然后发现是可以按$\sum k_i$分层的，而分层dag的最小链覆盖显然是最大的那个层的大小，对于本问题就是$\prod_i (\sum_{j=0}^{mx_i} z^j)$的最大系数，可以分治NTT做。事实上一个结论是这东西的系数是先递增再递减的，且其最高点为$[z^{\lfloor (\sum mx)/2 \rfloor}]$，相关资料可见此OEIS。例题：CF1257G Divisor Set麻将题，「CF1110D」Jongmah
$\frac{x}{y} \in (\frac{a}{b},\frac{c}{d})$要最小化x或y：为了方便说明，假定$\frac{x}{0} \to \infty$：
先$\frac{x}{y} \in (\frac{a}{b},\frac{c}{d}) \rightarrow \frac{y}{x} \in (\frac{d}{c},\frac{b}{a})$，这样就是最小化分母
设$solve(\frac{a}{b},\frac{c}{d})$找到最小的y满足$\frac{x}{y} \in (\frac{a}{b},\frac{c}{d})$
$\frac{a}{b} \ge 1$，$t=\lfloor \frac{a}{b} \rfloor,solve(\frac{a\%b}{b},\frac{c}{d}-t,\frac{x}{y}-t)$，因为分母不会变
$\frac{a}{b}<1,\frac{c}{d}>1,x=y=1$
$\frac{a}{b}<\frac{c}{d} \le 1,将分数倒置，\frac{x}{y} \in (\frac{a}{b},\frac{c}{d}) \rightarrow \frac{y}{x} \in (\frac{d}{c},\frac{b}{a})，但此时问题是最小化分子$
然后就懵逼了很久，感性上说分数这种jb玩意的大小关系是个整体，但这次真的不太想感性了
其实理性的话就一句：$\frac{c}{d}有最小分子，\frac{a}{b}有最小分母，则\frac{c}{d} \le \frac{c}{b} \le \frac{a}{b}$，而$\frac{c}{b}$
作为大人不想做选择接着分析复杂度，注意到每次是把左边界搞个辗转相除，然后交换左右边界，因此复杂度为$O(2log)$
例题如Codejam2019Round2 New Elements Part 2、2019多校hdu6624 fraction
其他
设cnt(x)为x二进制下1的数量，$cnt(a \oplus b)$ 为奇，当且仅当一个cnt为奇，另一个是偶
因为两个1在一起是偶，不在一起也是偶二进制数相减，不要考虑借位，而是允许-1存在，加法类似
所有n的排列中，奇排列数p=偶排列数q，因为交换任意两个元素必定使逆序对奇偶性变化，对所有p交换某两个位置，$p \ge q，同理q \ge p$
对于$D=x^2+y^2$，对x和y奇偶性讨论可知：$D\%4=0 \leftrightarrow xy都是偶$；$D\%4=2 \leftrightarrow xy都是奇$；$D\%2=1 \leftrightarrow 一奇一偶$。可能构造题会比较常见，例如CF1270E Divide Points、AGC025D Choosing Points
m次操作，第i次操作为将区间染色成i，始终保持连续相同的颜色缩起来成块，则每次区间操作覆盖的块数之和总和为$O(n)$。可以简单势能分析，每次块数约为删除块数，而新建块数只有1