Map1e
\(11111=\frac{10^{k}-1}9\)。先给 \(N\) 乘上 \(9\)，判 \(N\) 是不是 \(10^k-1\) 的倍数。
在模 \(10^k-1\) 下，\(10^{2k},10^k\) 位都等于 \(10^0\) 位，每 \(k\) 位分一段，将所有数加和，要求这个和要是 \(10^{k}-1\) 的倍数。
想要让复杂度是 \(O(n/k)\) 的。考虑每一段的数字都 \(<10^k\)，因此总和 \(<n/k10^k\)，判 \(10^{k}-1\) 的倍数判到 \(1...n/k\) 即可，用哈希判。
Marbles
建重构树。一个点覆盖的是一段上下的路径。
上下界流。有两种方法：
- 连一个内向树，再对每段路径连一条前向边。
- 连一个内向树，对每段路径，拆点后连两条边，分别连到路径的起点和终点。
Distance Optimizing Triangulation
答案为 \(2N-连通块个数\)。
每个连通块至少是 \(2M-1\)：把最短路上的边标出来，那么只看标出来的边也一定联通，因此至少有 \(2M-1\) 条边。
同时可以构造达到 \(2M-1\)，连成一个菊花即可。
圆上 \(N\) 条弦，两条相交的弦之间有一条边，求联通性。
先断环为链。
\(O(N\log N)\) 做法：线段树优化 DFS。
线性做法：xor哈希。如果两个位置（切点）哈希值相同，说明这两个点属于同一个连通块，就把在这之间的其他边从栈中弹出。
Binary Sequence and Queries
先固定左端点缩右端点，再固定右端点缩左端点。
Tsunami
任意时刻的 dp 数组满足 \(dp_i-dp_{i+1}\in [-c,c]\)。
加入一个点，松弛到的点是周围的一段区间。线段树维护左右端点处的 dp 值，区间覆盖等差数列。
区间加会产生若干个段。从左往右，使用 \(l-1\) 处的 dp 值来更新 \([l,r]\) 内的 dp 值。再从右往左做一遍同样的过程。注意要通过一些办法保证不要覆盖到不需要更新的点，比如这样限制只能更新当前这一段。
Wonderful Impostors
双指针。考虑能不能加入 \(r+1\)，如果可以就移动 \(r\)，如果不能就移动 \(l\)。（注意这里不是先加 \(r\)，再删 \(l\) 直到变为合法为止。）
因为 \([l,r]\) 肯定是合法的。加入一个 \(r+1\) 只需要看 \(r+1\) 是否会导致不合法。求出加入 \(r+1\) 后向左向右最多能延伸多远。再看这个区间内又没有包含一个区间。
Arctic Acquisition
枚举 \(2\)，那么能确定 \(1\)。考虑 \(235\) 张成的支配对。
结论：\(5\) 一定是 \(3\) 后面第一个比它大的。因为如果不是，可以把 \(3\) 换成这个位置，并且这样 \(3\) 只会越来越大。
TEST_107
选中的区间一定满足向左向右都无法再继续扩展。所以要么左右靠边，要么左右都是同一种没有出现的数，第二种情况只有 \(O(n)\) 个支配对。第一种情况，扫描线维护最后一次出现位置。、
堕天作战 TEST_98
用线段树去维护修改。如果区间最小值 \(<x\)，那么操作完最小值就变成负数了，一个数只会变成负数一次，所以可以直接递归。如果最小值 \(>x\) 整体标记。如果最小值 \(=x\)，且次小值 \(>2x\)，打上非最小值的标记返回。否则次小值操作完一定减半，继续递归。
类似的题：
维护修改：值域区间内的数整体减 \(x\)。平衡树，对于 \(x~2x\) 全部取出后重新插入，其余直接 split merge。也可以值域有交合并。复杂度都是 2log。
riapq
二维或更高维度的单点查询矩形修改这种树套树能做的东西，都可以分块平衡，可以做到 \(O(1)-O(\sqrt n)\)，并且这种并没有矩乘规约，复杂度可以任意 \(O(n^{1/k})\)，代价是另一边的常数 \(*k\)。
本质上是把树套树改多叉来平衡复杂度。
卡常技巧：给 DS 功能函数开 inline（先试试这个）;循环展开；调换数组两维
r2pspc
简单做法
回滚莫队。将左端点块内的数设为关键点。对每一段实际上只会影响低 \(\log\) 位，对 \(\log\) 位之后的影响要么是 \(0\) 要么 \(+1\)。在动右端点的过程中因为每次加 \(0\) 都在删 \(0\) 之前，维护每一块的 \(0\) 的链表，通过链表快速找第一个 \(0\)。
更强的做法
KDT
kdt 改 tb5
hlcpq
如果只是求联通性，就可以主席树优化建图：扫描线，扫到下端点时加入到下端点时删除，对线段树可持久化。
主席树肯定做不了修改，因为修改一个点会影响反向边能到的所有点。考虑 DFS，对每个主席树结点，维护子树内还有没有未访问的点。如果维护的值不对，说明都访问完了，这种情况只会发生一次。同时还需要求最小的 low。一种方法可以离线扫描线再求一遍（因为虽然不可差分，但有一维是单点，所以实际上可以不用树套树，1log）。也可以直接在主席树的结点上维护，因为一个点做完之后能到的所有点都被访问过，因此维护的值一定是正确的。实现时，只需要保证标记访问完的点，维护的 low 是对的即可。如果跑完左右儿子才发现一个点子树实际上都已经访问完了，就标记这个点，并更新 low。其他时候不用 pushup。
还有一个小细节：把 \(n\) 横 \(n\) 竖扩成 \(2n\) 条线，就没必要横竖分开做了。
Onion
卡常技巧：不要cc_hash_table，不要cc_hash_table，不要cc_hash_table！！！哈希表的速度是相同数据量sort的两倍甚至两倍以上！！！
减少多次计算 \(f(x)\) 取模带来的常数。
Shortest Path
如果一个点度数为 0/1，答案为 1/2。
如果一个点度数为 2，且非割点，那么答案为包含 \(u\) 的最小环长。且如果一条路径经过 \(u\) 但不是以 \(u\) 结尾，答案也不会优于包含 \(u\) 的最小环长（因为显然路径本来就应该是一个环）。那么只需要考虑只经过 \(\ge 3\) 度点的路径。
case1: 8字型
首先左右必须有。其次角上不能有。因为经过一个 \(\ge 3\) 的点经过的所有点都 \(\ge 3\)，所以可以假设上面的点度数 \(\ge 3\)，所以向上都有。那么在上面又得到了一个8字型。因为棋盘有限，所以可以按行号归纳。这种情况下的答案不超过 \(8\)。
case2: 风车型
边上的点度数 \(\ge 3\)，所以向下向右又会延伸出一个风车，考虑两个风车之间可以得到答案 \(\le 10\)。如果将这个棋盘都画出来，会得到一个很好看的密铺结构。
Three Hundred Queries
做法1
考虑问 \(0\) 知道 \(0\) 到所在的弧边缘的距离。再问 \(1\) 知方向。判掉 \(d_0=d_1,\min(d_0,d_1)\le 1\) 等撞大运事件。那么就求出来某个关键点。自然去问这个关键点，得到某一段弧的长度。（返回的结果一定是某一段弧长。）
考虑一次的结果一定是 \(a,b,c\) 中某两个的 \(\min\)，那么 \(a,b\) 都能问出来，且只能问出来 \(a,b\)。
问 \(100\) 轮。如果是 \(\{a\}\)，那么答案为 \(a a 10^9-2a\)。如果是 \(\{a,b\}\)，那么答案为 \(a,b,10^9-a-b\)。
再去分析正确率。\(0\) 落在最长弧上的概率至少是 \(1/3\)。问 \(\min(a,c),\min(b,c)\) 的概率都至少是 \(1/6\)。
做法2
（求最长弧）问 \(0,1\) 得到一个关键点，再问 \(x+1/6\) 左右，有常数概率恰好问到最长弧。
做法3
问 \(0\)，再问 \(d,10^9-d\)。那么一定会覆盖到某一段弧。其余的数被问到的概率都不会很大。
排除掉没有问到很多次的数。剩下的最小的一定是 \(a\)。还需要区分答案是 \(a\ a\ b\) 还是 \(a\ b\ c\)。注意到前者 \(a\) 一定被问到了至少 \(100\) 次。而后者约为 \(50\) 次。
做法4
结合做法3和做法2，\(50\) 次询问问出来 \(a,b\)，\(50\) 次询问问出来 \(c\)。那么就得到了弧长可重集。再分讨。
The Real Folk Blues
先搞出来充要条件。
热身赛
B
序列做法：点边容斥，值域区间合法 -> 黑白+白黑=1
（做法2：分治 做法3：扫描线，线段树维护mx-mn+1-(r-l+1)）
矩形：依旧点边容斥，黑的角个数=1
一个2x2会对一个矩形产生贡献，扫描线线段树。
C
使用线段树维护，对于区间 \([l,r]\)，将 \(r+1,r+2\) 设为主元。维护 \(l-1,l\) 关于 \(r+1,r+2\) 的线性表示。合并就是矩乘。
模拟赛
A
原问题等价于将 \(n\) 拆分为一些 \(2^k\) 的方案数。为什么？
B
做法1：长剖，线段树二分找分段的位置
做法2：长剖，考虑合并轻儿子，对于 \(\le sz_v\) 的部分暴力，其余使用线段树暴力找到发生进位的位置，树上打 tag。
C
写成 \(2n\) 个变量 \(2m\) 条限制的线性规划。转置后 \(2m\) 个变量 \(2n\) 条限制。每个变量的含义为一条边的流量，一条限制实际上限制了一个点的流出减流入不超过某个值。可以直接写成上下界费用流，但是可能会流负环（有负环不代表答案为 \(-\infty\)），因此需要消圈。实际上，可以限制流出减流入恰好是某个值，转为费用流，要求满流。证明：将两种不等式相加，左边为两倍的总流量，右边为 \(2S\)，则 \(\sum x\le S\)，又因为 \(\sum x\ge S\)，则 \(\sum x=S\)，只有当所有 \(x\) 都取满的时候才能取到。
构造方案：互补松弛定理/原始对偶（注意要从 \(T\) 到 \(S\) 跑）
6.18模拟赛
A
B
C
定义生成序列：\(x_{1...n/3},y_{1...n/3},z_{1...n/3}\)，表示三个人分别吃的位置。
引理1：\((a,b,c)\) 合法，当且仅当 \(x,y,z\) 单调，且 \(a_{x_i},b_{y_i},c_{z_i}\) 在 \(a_{1...x_i},b_{1...y_i},c_{1...z_i}\) 中只出现一次。
引理2：确定 \(a_{x_i},b_{y_i},c_{z_i}\) 后，有 \(\lambda=\frac{n!}{(n/3)!3^n}\) 种可能的 \(c\)，这个值只和 \(n\) 有关。证明：考虑 \(c\) 序列，先令 \(c=z\)，再依次插入 \(x_{n/3},y_{n/3},...,x_1,y_1\)。
当确定 \(x,y,z\) 后，填入 \(c_{z_i}\)，对于 \(z\) 序列，需要满足 \(c_{z_i}\) 在 \(a_{1...x_i},b_{1...y_i},c_{1...z_i-1}\) 中不能出现；且 \(a_{x_i},b_{y_i},c_{z_i}\) 互异。
斯特林反演
\(f_n\) 表示 \(n\) 个互不相同的行的方案数，\(g_n\) 表示 \(n\) 行的方案数。
\(g_n=\sum_m \{n,m\} f_m\)。
则 \(f_m=\sum_n \[n,m\] (-1)^{m}\)。
two-graph
\(C(x),H(x),T(x)\) 表示联通图，有根树，无根树的 EGF，则 \(F(x)=C(H(x))T(x)\)。
\(H(x):n^{n-1}frac{x^n}{n!},T(x):n^{n-2}\frac{x^n}{n!}\)
有根树 \(T=xe^T\)：把子树做 exp，再加入根 \(x^1/1!\)。
无根树: \(U=T-T^2/2\)。
得 \(H(x)=C(xe^{-x})-x+x^2\)。
\(C(xe^{-x})=\sum_{i=1} c_i\frac{(xe^{-x})^i}{i!}\)
\(h_n=\sum_{i=1} \frac{c_i}{i!}[x^n](x^ie^{-ix})\)
\(h_n=\sum_{i=1}^n \frac{c_i}{i!}[x^{n-i}](e^{-ix})\)
\(h_n=\sum_{i=1}^n \frac{c_i}{i!}[x^{n-i}](\sum_{j}\frac{x^j}{j!})\)
黄金三分
QOJ Stirling number
模拟赛
T1
T2
模板
实数的二进制逼近 考虑竖式
基环树上解方程
如何构造：考虑列出将所有的数加在一起的竖式，
T3
01trie +1 trick
进位trick：如果一个 bit 发生了进位，此时低位一定全 0（arc）
单 log 做询问所有 bit：求出最高进位，可持久化 trie
不妨假设每次询问的 \(t\) 都是最高位。
+1trick：如果一个 bit 发生了进位，此时这个位及更低的位均为 0。
第 \(p\) 位从 \(0->1\) 也叫做第 \(p\) 位的一次进位。
一次是否进位只和更低的位（不包括这个位）有关。
考虑一次第 \(p\) 位的进位实际上得到了什么信息：\(<p\) 的位都是 \(0\)，第 \(p\) 位可能 0 可能 1。设** \(f_{i,p}\) 表示若第 \(i\) 次操作后 \(p\) 发生了进位，下一次 \(p\) 进位的时间。**
考虑怎么回答询问，如果 \(t\) 没有发生进位，答案是好算的，否则需要找到 \(t\) 第一次发生进位的时间，再在 \(f\) 上倍增/树剖（树上链信息：倍增/树剖，树剖空间线性）。
如果第 \(p\) 位发生了进位，\(\le p\) 的位也一定发生了进位。
求出 \(g_{i,p}\) 表示若第 \(i\) 次操作后是一个恰好第 \(p\) 位的进位（\(100...\)）下一次第 \(p+1\) 位的进位。
因此从 \(0\) 的进位开始跳 \(g\)，\(p\to p+1\) 的时候只和第 \(p\) 位的值有关。跳完看是不是恰好是 \(p\) 的进位，如果还能进到 \(p+1\) 就 \(++p\)。
Phoenix and Bits
鸽子收费站
扫描线，插入回收
每个线段树结点维护一个平衡树
平衡树上维护到儿子结点的指针 (并察冀)
Optimal Ordered Problem Solver
操作过的点一定构成一个阶梯状。如果 \(x\) 在 \(y\) 的左上方，经过一次操作后仍然满足 \(x\) 在 \(y\) 的左上方。
注意你的数点实质是几维的。
wcirq
？？？
\(a,b\)序列互相修改/chkmax之类的都可以线段树维护
美好的每一天
题目要求构造莫队。回滚莫队，固定 \(l\) 在一个块内去动 \(r\)。因此普通的回滚莫队复杂度为 \(O(qB+n^2/B)\)，平衡得到和普通莫队一样的复杂度 \(O(n\sqrt q+q)\)。
问题是动 \(l\) 的时候代价会爆，因此想办法估计动 \(l\) 的代价 \(w_l\)，而这不超过从 \(n\) 到 \(1\) 加点的代价，因此 \(\sum w_l\) 不超过 \(n\log n\)。可以看作是 \(n\log n\) 的序列上回滚莫队，复杂度多一个 \(\log n\)