窝记了70+条来着。。？窝决定搞完一个note发一个到这里！
欢迎大家催更 > <
当前进度 ：8.5/70
1.如果要找到二维矩形内所有点（k个），归并树（log^2n + k）比主席树(klogn。。线段树找到在哪些x坐标上有点，对每个x坐标开一个vector，然后在每个有点的vector里面二分一下)优。。
注意到我们不用在归并树产生的所有区间里面二分一次，因为所有点都是从root划分下去的，于是只需要在root二分一下，每个节点维护下它在它两个子树里的lower_bound，然后走到子树里的时候就可以根据这个直接得到子树里面的原本需要二分的lower_bound，这就是时代的眼泪划分树。
（解锁人生成就——强行脑补出划分树）
2.BIT上二分的技巧
每次确定一位，s[xxx1000]代表的范围是a[xxx0001..xxx1000]，于是每次确定每一位能不能是1
注意如果找的是第k大，那么需要注意应该找sum < k的最后一个，然后r+1，因为第k大的可能不止一个嘛
m是下标的位数，n是下标范围
//find kth
x = S = 0;
dep(i,m,0){
x ^= 1 << i;
if (x < N && S + s[x] < k) //x <= N! 一定要记得判一下！
S += s[x];
else
x ^= 1 << i;
}
x++;
3.三元链计数的经典做法：
找a->b->c的链个数，枚举b，找出a->b和b->c的个数，然后乘起来（利用偏序等a->b b->c个数可能可以预处理）
竞赛图有向三元环计数的经典做法：
考虑不合法情况，容斥，枚举一个点x，统计a->x，b->x的(a,b)数（C(d_x, 2)）
2*m的图三种颜色染色，相邻两个格子颜色不同的经典转化：
把每个列的两个格子变成没有出现的那个格子，然后就转化为了一个1*m的问题（zyh day2的t2）
4.对于线性规划问题，通过添加变量全部转化为等式之后，如果1在列上连续的话，我们就可以按行差分（Ax = b）注意不光A要差分，b也要差分，然后就每列就只有一个1和一个-1了。。于是把每行看做一个点，就可以每列作为一条边从-1那行流到1的那行了，然后如果b_i小于0，从S连-b_i的边，如果b_i大于0，连b_i得边到T，然后使用最小费用最大流即可（满流有解）
ext：如果在行上连续，那么
5.徐爷爷（bx2k）说过，bzoj3232圈地游戏有一个用找负环来解决的办法，思想是二分答案后，在列上用前缀和的办法把格子上的权值转移到边上，然后找一个封闭回路，使得权值和为负。。感觉这个转化好厉害啊。。
注意一个问题就是网格图上dfs版spfa找负环是指数级复杂度（所以正式比赛千万不要写dfs的spfa。。找负环快什么的都是骗人的），所以写bfs版spfa就好
6.bzoj4012可以可持久化点分，这样就是一个log的了。。
7.徐爷爷（bx2k）说过给你一个1..n的排列，求存不存在等差子序列。。
显然判下有没有长度为3的即可，然后我们枚举中间点a_i
a_i - k 和 a_i + k 如果一个在a_i前，一个在a_i后，那么就有解了
我们把每个数在a_i前还是后压一个01串，然后正着反着hash两下树状数组维护判一下即可
8.经典分块：整数拆分
9.Hall定理：左边任意k个点都要与右边至少k个点相邻，二分图才有完备匹配
暴力用这个判显然是2^k的。。所以往往利用题目的性质来做！
10.快速(O(N) 比传统高斯消元不知道高到哪里去了)解x_i = a_i x_{i - 1} + b_i x_{i + 1}
移一下项，得到x_{i - 1} = 1 / a_i x_i - b_i / a_i x_{i + 1}
然后x_{n-1}可以用x_n表示出来，于是可以用x_n表示出所有x_i，从而O(n)解出来
11.C(n,2)种约束（若干个不等），无法容斥，
『选出一个联通块都一样的，然后算这块的容斥总贡献（块内边数），再容斥就行了= =』？
似乎是dp一下找出n个点、j个联通块方案数对答案的贡献之类的。。。。？
2016年1月05日 02:42
感觉划分树好厉害>_<
其实窝一直想知道kdtree有什么剪枝黑科技...
UOJ二维数点那题我kdtree还没有暴力分...
2016年1月05日 21:51
@Recursion: 不知道诶。。
2016年1月06日 02:05
说话先更km的呢？%w爷爷！
2016年1月06日 22:03
@bx2k: 窝怂了。。
2016年1月19日 22:31
好像4012大家都写点分啊...明明树链剖分那么好写...还不需要度数小于3...
2016年1月20日 04:35
问一下可持久化点分是什么东西。。。窝不会。。。。@whx
2016年1月20日 21:26
@wyh2000: 大概就是点分每次只会修改log个点嘛，我们直接和持久化数据结构一样新建咯
2016年1月23日 19:08
@Recursion: Orz
就是树链剖分+可持久化线段树做。。？
2016年1月24日 00:20
@whx: 对
2016年2月25日 18:52
w爷爷竟然开始更了！我好兴奋啊！
2016年3月08日 03:38
%%%催更啊！