还没更完，，只是上课时的笔记，很多东西很多很杂。。得慢慢吸收吧。。
CDQ 分治
本质上是考虑左边对右边的影响，问题变成了先加入再查询的问题
离线算法
处理 D 维数点时间是 $ O(nlog^{D-1}n) $
D 维数点用KDTree：$ O(n^{\frac{D-1}{D}}) $
D 维数点用Bitset：$ O(\frac{Dn^2}w) $ *
应用：
加点，给定 $ a , b $ 查询最大的 $ ax+by $
本质上是维护动态凸壳 *
直接set维护
记录全局变量，做插入的时候按照 x 比较，做询问按照斜率比较
因为set里面x递增，斜率也递增
CDQ 分治
solve( l , r ) ，先 solve( l , m ) solve( m + 1 , r )
然后就变成了静态问题，左边点加进去，右边的询问。
静态凸壳！
右边斜率排序，然后类似归排扫一遍就好了。
CF 848C
维护每个数字的位置和上一次出现的位置，价值是 i - pre i
一段区间的价值就是 $ \displaystyle\sum_{l\leq i \leq r , pre[i] \geq l} i - pre[i] $
本质上类似差分
修改本质上只会修改 pre 指向这个点的，这个点，还有它的prev，只会改变三个值。
带修改的二维数点本质上是三维数点，时间是一维。 $ O(nlog^2n) $
可以写一下
uoj 50
求解微分方程 $ f‘(x) = f^2(x) p(x) + 1 $
算出来的式子是 $ \displaystyle \frac{1}{n} \sum_{0\leq i+j\leq n-1} f_if_jp_{n-1-i-j} $
分治吧，貌似就是分治fft套路
先solve( l , m )
然后考虑新求出的左边的值对右边的贡献
然后就要用 $ f_{l...mid} f_{0...r-l} p_{0...r-1} $ 卷起来
然后就把 $ m+1...r $ 更新进 $ f_{m+1...r} $
式子可能有点小锅，需要再推一下。。
线段树分治（暑假讲的叫时间分治）
离线动态图连通性
把每条边的存活时间放到序列上，然后就可以在线段树上dfs，撤销并查集解决问题
这里要按大小合并，才可以让撤销的量很少
可以LCT维护删除时间的最大生成树，也是离线
对每个物品，求不包含它的背包 方案数
线段树分治
solve( l , r , f ) f 表示 把 $ l , r $ 外面的物品加入的数组
f_1 表示 f 加入 mid + 1 ... r 的物品
f_2 表示 f 加入 l ... mid
然后递归下去 $ O(nwlogn) $ 一个物品会被加入 $ logn $ 次
城市建设
修改边权，求MST和
还是可以对时间建立线段树，求出每个边存活时间
LCT 一个 log，线段树分治一个 log，很慢，不需要动脑子
修改一条边边权实际上只会影响MST一条边
随着修改MST变化是很少的
$ solve(l,r) $ 表示 $ l , r $ 的修改
整个MST只会改 $ O(r-l) $ 边，其他大多数边是不变的
能不能把会变的边拿出来跑MST？
假设边集（l...r修改的边）是 $ S $ ，先把其中边设置为 +inf
把这些边和剩余的边跑MST，然后现在不在MST中的边就可以删除了。
因为这些边只会变小，只会把MST的边给拖出来
现在边数边成了 $ O(n + |S|) $
然后再设置成 -inf，再跑一次MST，现在在MST中的边一定最后也在MST中
点数变成了 $ O(|S|) $，因为这些边已经可以用并查集并起来了。
而 $ n $ 其实是上一层的点数，也就是 $ O(2(r-l)) $
所以这一层的复杂度也是 $ O(r-l) $ 的
$ T(n) = 2T(\frac{n}{2}) + O(nlogn) $
$ O(nlog^2n) $ 这里的 log 是排序
有点难写吧（可以写一下
核心思想：修改影响的边数量很少
二进制分组
二项堆
一种可并堆。
T_k 表示的堆是 $ T_{k-1} $ 再挂了个 $ T_{k-1} $ ，然后节点数量就是 $ 2^{k-1} $
11个数字的二项堆就是一个 8+2+1的森林
合并两个二项堆就是类似二进制+法。
合并是 $ log $ 的
删除元素，其实也是合并，比如从16的堆删除就是 1,2,4,8, 的堆和剩下的堆合并。
维护向量序列，支持末尾加入元素，末尾删除元素，求 $ l,r $ 和 $ (x,y) $ 的最大点积
二进制分组解决的问题往往是，重构很简单，插入删除很麻烦的东西。比如凸壳这种东西，重构直接做，但是插入删除很难。
如果只有增加的话，加入当前有21个元素，我们记做三组 16 + 4 + 1
每组都建一个数据结构，支持区间查询，并且重构很快（线性就很优秀），插入删除很慢。
你往后面加入一个元素，就和前面一步一步合并（重构）过去，比如刚刚那个21的例子，加入一个元素就是 16 + 4 + 2
这样的结构数量必然是 $ log $ ，如果在某个结构查询复杂度是$ Q(n) $ 那么查询复杂度就是$ Q(n)logn $
重构的复杂度假如是 $ n $ 那么每一个元素最多会被重构 $ logn $ 次，所以，总复杂度是 $ nlogn $
重构是均摊 $ logn $ 的
既然支持区间操作，可以对每个区间建个线段树，暴力build线段树也是 $ nlogn $
复杂度是 $ nlog^2n $ 的
其实也可以看作建了一棵大的，点数是2的次幂的线段树，当一个点下面的所有叶子都被填了值才把它建出来。本质上是一样的。
二进制分组怎么删除呢？其实整个序列如果画成一棵树的样子（大概就是版本树之类的？）删除就是往父亲跳，加入就是新加儿子。所以问题本质上就是给你棵树，求某个点到根上的一段的点积的最大值。
树剖是 $ O(nlog^3n) $ 对询问排序可以去一个log，反正好像不优秀
题解做法好像是点分
直接线段树强行搞是不行的，你删除一个插入一个....在一个块的左右反复横跳就挂了
其实可以搞成随机的，每个点随机一个权值如果比上一个小就合并。
对于一个块被建出来，如果这个块有东西被删除了，就记个标记表示这个块是坏的。
查询如果查到一个坏的块（节点）就到左右递归继续查。
我们希望保证每层只有一个坏的块
如果结尾一直在最后那个坏块动来动去没啥问题
但是如果你的结尾移到了前一个块，那么意味着最后面那块被删光了，那么还是只有一个坏块
但是如果结尾移到了后一个位置，下一个块被建了，那么我们可以直接重构前一个块。
还不是很明白，想清楚了再继续写吧。。
整体二分
子矩阵查询 kth n 500 q 50000
直接二分的话，需要查询子矩阵比某个数大的个数
整体二分，就是拿所有询问一起二分
我们需要看哪些询问权值是大于 $ \frac{w}{2} $ 的，哪些是小于等于 $ \frac{w}{2} $ 的
这个比较简单的方法是把小于等于 $ mid $ 的标1，然后前缀和
然后我们就把询问分成了 $ 0...\frac w 2 $ , $ \frac w 2 + 1 $
就这样分治下去
但是每一次分治 $ n^2 $ 肯定是不行的，必须做到每层 $ n^2 $
每次分治其实我们只需要把 $ l...mid $ 加进去然后做查询
对于每个询问就是二维数点的问题。
其实貌似顺次递归来做，就直接是对的了吧。。
所以对于分治到 $ l,r $ 复杂度就是 $ O(|A|+|Q|logn) $ $ A $ 为这里的点集
复杂度是 $ (n^2+Q) log^2(n^2) $
单点修改区间 kth
二分到 $ l,r $ 把一个数字从 $ a $ 到 $ b $ 就是 $ x $ 这个位置 少 $ a $ 多 $ b $
可以看自己以前的代码吧 $ nlog^2n $的
ZOJ2112 这题由于空间限制只能整体二分
给 $ l , r $ 的vector 放进去个 k 求 l , r kth
整体二分就变成区间+了 貌似就是那个 任务查询系统 以前挂了好久的题
CF 102354 B
给定 a , b 两个1...n 排列，求 $ c[k] = MAX_{(i,j)=k}|a_i-b_j| $
$ c[k] = MAX_{(i.j)=1}|a_{ik}-b_{jk}| $
其实我们只要求了 $ c[1] $ 问题就解决了
因为 $ c[k] $ 本质 就是 $ a_k,a_{2k},...,a_{\lfloor\frac n k \rfloor} $ 和 $ b_k,b_{2k},...,b_{\lfloor\frac n k \rfloor} $ 来跑 $ c[1]$
枚举 $ i $ 就要求最大的 $ b_j , (i,j) = 1 $，因为最大最小是对称的我们求最大的就好了。
整体二分，分治到 $ (l,r) $，就是知道 $ a_i $ 的最大的值在 l,r 间。
我们按照 值在 $ mid + 1...r $ 的下标是否存在与当前 $ a $ 互质的把 $ a $ 分成两份分别跑二分下去。
然后问题就是，统计值在 $ mid + 1 ... r $ 的下表 $ j_t $ 是否存在与某个下标互质。
对于 $ a_i $ 下标 $ i $，需要统计
$ \displaystyle\sum_{j\in A}[(i,j)=1] $
莫反一下
$ \displaystyle \sum_{j\in A} \sum_{d|(i,j)} \mu(d) $
然后我们可以枚举 $ d $ ，给每个 $ d $ 统计一下在 $ A $ 里面的倍数个数，并且把 $ \mu(d) \times cnt $ 放到作为它倍数的 $ i $ 里面。
决策单调性
就是存在最优的方案决策单调。一般都是打表找的规律。
首先，四边形不等式 $ w(a,d) + w(b,c) \geq w(a,b) + w(c,d) $
假设有 $ i , k , l , j $ ， 如果决策不单调意味着 $ i $ 转移到了 $ j $ 而 $ k $ 转移到了 $ l $
如果满足了上面那个式子，相交的两条边优于了包含的边，所以就满足了决策单调性。这大概就是实质了吧？
CF 321 E & 诗人小G
下面是几种搞决策单调性的方法
这里可能还需要再听一下
$ solve( l , r , p , q ) $ 表示 i 再 $ l , r $ 最优决策是 $ p , q $ 之间
我们可以先算 $ mid $ 位置的决策点 op 然后，就可以
$ solve(l,mid,p,op) , solve(mid+1,r,op,q) $
这样复杂度是 $ O(knlog_2n) $ 这样不容易挂。
其实也可以二分单调栈。考虑我们如果求出了 $ dp[1] $ 那么后面最优都是从 1 转移过来
现在求出了 2 ， 从 2 转移最优的构成了一个后缀。于是我们可以用单调栈维护每个点可以决定的区间。先从后往前找看能不能整个替代，到达具体区间后再二分。复杂度也是一个 $ log $ 但但是不如前一个好写。
其实是可以 $ O(nk) $ 的，然而我看不懂 SMAWK
四边形不等式
满足四边形不等式后，假设 $ dp[l][r] $ 决策点是 $ p[l][r] $，那么
$ p[l][r-1]\leq p[l][r] \leq p[l+1][r] $
其实本质就是交错的路径优秀于包含的路径
CF 868 F
暴力分治，$ solve( l , r , p , q ) $
分治下去的时候端点的移动总量是 $ O(r-l+q-p) $ 级别的。
把指针从 $ p $ 移动到 $ mid $ 并且不断更新每个数字的出现个数，同时不断算 答案并且更新。
建议看这个学一下再
IOI 2013 wombats
假设是朝右朝下吧，不是很影响
对于 R 这一维建立线段树
决策是具有单调性的，路径有交叉可以通过调整变短
如果结束点从上往下走，那么中转点必然也是从上往下走的
复杂度是 $ O(c^2logclogr) $
IOI 2014 holiday
首先，肯定不会反复横跳
然后，结论就是 $ r $ 关于 $ l $ 是决策单调的。
不太会证，这里引用下钟神的证明：
设某个区间\([l,r]\)的答案为\(w(l,r)\)。
考虑反证，设\(l\)的最优右端点为\(r\)，\(l+1\)的最优右端点为\(r'\)，且\(r' < r\)。
那么我们有：
\[
w(l,r) >w(l,r')\\w(l+1,r') > w(l+1,r)
\]
两式相加得到
\[
w(l,r) + w(l+1,r') > w(l,r') + w(l+1,r)
\]
即
\[
w(l,r) - w(l,r') > w(l+1,r) - w(l+1,r')
\]
显然是不成立的，因为上述式子的意义实际上是将\((r',r]\)的元素加入\([l,r']\)或者\([l+1,r']\)，带来的额外的贡献。由于加入的元素是相同的，而\([l,r']\)它可以去玩的天数更少，所以
\[
w(l,r) - w(l,r') \le w(l+1,r) - w(l+1,r')
\]
WQS 二分
凸优化
Tree
我们考虑给所有白色边加权，通过调权值可以让最优策略的白色边个数变化。
通过二分调整权值使得最优策略正好需要need个白边
什么情况这样二分正确呢？如果代价关于个数的图像是凸的
若 $ f(x) $ 表示选择 $ x $ 个白边（上一个题）的代价
条件就是 $ f(x+1) - f(x) \geq f(x) - f(x-1) $
咋证明，我也不会，只会感性理解QAQ
邮局
如果权值满足四边形不等式，那 f 一定是凸的。
所以二分权值，然后用那个单调栈的方法dp一下
复杂度是 $ O(nlognlogv) $
--- 开始掉线 ---
Rikka with K-Match
没看太懂，后来再康康吧。。。wsl
林克卡特树
二分，搞个额外代价，虽然不会证明，但是它确实是凸的
一个经典题
操作A串（添加，删除，修改）使得AB循环同构
不循环重构
就是个 $ O(n^2) $ dp
$ dp[i][j] $ 可以由 $ dp[i-1][j-1] + c_M$ , $ dp[i-1][j] + c_A $ , $ dp[i][j-1]+c_d $ 转移得到
这个可以看成是平面图上的最段路
路径上的每个点当成决策点，对起点分治，找 $ 0,\frac m 2 $ 到 $ n , \frac m 2 $ 的路径。
这个路径上半部分的点只对上面的起点有用，下半部分的点只对下半部分的起点有用
然后就可以分治下去做
这大概就是广义的决策单调性 ， 不仅可以用于dp
（有点迷糊。。）
循环同构复杂度是 $ n^2logn $ 的
给定一个凸包，要选择 $ k $ 个点，使得围成面积最大
原文：https://www.cnblogs.com/yijan/p/12248974.html