标题五个字/cf
spoj CARD - Cardsharper
来自fajne zadania。
考虑每个元素会如何移动。在$a$上沿着一个环走，在$b$上同样沿着一个环走。
我们想起来一个经典问题，好像来自atc，说的是如果你能够转整个序列，或者转前三个元素，就可以排序。显然还有很多类似的东西。猜测我们总是可以生成绝大多数的排列。
事实证明确实是这样，在几乎所有情况下我们可以生成所有排列。但是我没有证明，并打算咕咕。
据说大力随机然后schreier-sims就好啦!
cf1578l
这个题是牛逼老哥给我看的啊。
跑个mst先。二分答案先。
时间倒流。然后在kru重构树上往上走即可。
于是也不需要二分答案了。
agc061a
先打表。观察小的感觉偶数的形式很好，这里给出16~30的偶数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
16
2 1 4 3 6 5 8 7 10 9 12 11 14 13 16 15
18
2 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 17
20
2 1(4 3)5 6 7 8 9 10 11 12 13 14 15 16 18 17 20 19
22
2 1 3 4(6 5)7 8 9 10 11 12 13 14 15 16 18 17 19 20 22 21
24
2 1(4 3)(6 5)(8 7)9 10 11 12 13 14 15 16 18 17 20 19 22 21 24 23
26
2 1 3 4 5 6 7 8(10 9)11 12 13 14 15 16 18 17 19 20 21 22 23 24 26 25
28
2 1(4 3)5 6 7 8(10 9)(12 11)13 14 15 16 18 17 20 19 21 22 23 24 26 25 28 27
30
2 1 3 4(6 5)7 8(10 9)11 12(14 13)15 16 18 17 19 20 22 21 23 24 26 25 27 28 30 29
可以注意到只可能是每对$2i-1,2i$交换，这是因为$\mathrm{shuffle}(1,n)=\mathrm{shuffle}(1,n-2),\mathrm{shuffle}(2,n-1),\mathrm{shuffle}(2,n-1),\mathrm{shuffle}(3,n)$，中间抵消了，然后归纳即可。括号标记的是除$n=16$之外，左半边非两头的交换了的位置。
$\mathrm{shuffle}(1,n-2),\mathrm{shuffle}(3,n)$，实际上就是把自己和自己平移一位之后每两个内部是否交换的状态$\operatorname{xor}$一下。于是我们看看$x\leftarrow x\operatorname{xor}(x\operatorname{shift}1)$是什么，把$\operatorname{xor}$看成加法膜$2$我们知道它是$F\leftarrow (1+z)F$，于是当我们想要一个位置的时候，提取出来是一个二项式系数膜$2$，可以用lucas定理算出它那里换没换。如果$n$是偶数那么做完了，如果$n$是奇数那么递归一层即可。
cf717a
求$\sum\limits_{i=l}^r\binom{f_i}{k}$，其中$f$是fib数。
看起来很是不好做。考虑下降幂转普通幂，我们算$\sum\limits_{i=l}^rf_i^k$。尝试塞通项$c(a^n+b^n)$然后二项式定理，它就是$\sum\limits_{j=0}^k\binom{k}{j}\sum\limits_{i=l}^r(a^jb^{k-j})^i=\sum\limits_{j=0}^k\binom{k}{j}\frac{(a^jb^{k-j})^l-(a^jb^{k-j})^{r+1}}{1-a^jb^{k-j}}$，这里需要特判$a^jb^{k-j}=1$的情况。复杂度$O(k^2\log v)$，可以预处理一些东西然后线性求逆做到$O(k^2)$。
洛谷讨论区的题
$f$是$a,b$-fib数，也就是$f_i=af_{i-1}+bf_{i-2}$。
那么问题就是怎么求通项了。$F=azF+bz^2F+f_0+z(f_1-f_0)$，设后面是$p+zq$，那么$F=\frac{p+zq}{1-az-bz^2}$。那么我们知道上面的$a,b$这里就是$1-az-bz^2$的两个根，剩下的东西就乱算一通!
cco2020 Shopping Plans
从xxiii poi stage 1 korale过来的。
首先每种买上最小的$x_j$个。然后第$k$小的钱数$d$，尝试搜出所有方案，我们要调整当前这个颜色到任意一个方案，可以通过在最右一个右边加入一个，或者把一个连续的后缀右移一位。
那么需要保证不能有重复的方案。为了做到这一点，考虑我们依次处理每个种类，也就是可以选择这个颜色的两种操作，或者移动到下一个颜色。我们需要保证移动到下一个颜色时能操作，所以按$2$和$1$位的差从大到小排，二分出可以到哪个后缀去。复杂度$O(n\log^2 n)$。
然后这东西也适用于那个扩展的想法，并且这样我们只需要二分$k$次。复杂度$O(n\log n)$。
loj6500 雅礼集训18 D2 操作
牛逼群友给我看的。
考虑最左边那个数，它确定了最左边的区间是不是需要操作，如此往右递推就是$O(nm)$。
注意到如果我们操作了$[l,l+k)$之后其中还有$1$，必然继续操作下去，但是这个复合有点困难。
还是考虑差分吧!那么操作就是把$s_i,s_{i+k}$同时$\operatorname{xor}$上$1$。于是每个膜$k$等价类中的$1$需要两两配对，答案就是这个距离和，那么处理每个等价类中奇数位置和偶数位置的前缀和，查询的时候差分一下扫描线扫过去就好了。还需要判断是否可行，也就是两边在各等价类状态的奇偶性是否相同，hash一下即可。
loj6736 最小连通块
这个题有一个牛逼做法啊。考虑我们可以$O(c(1+\log\frac{n}{c}))$地在$n$个点的树中找到一棵大小为$c$的子树中的所有点，然后我们还知道随机一个根和一个点，得到的子树大小期望是$<\frac{n}{2}$的，所以就$O(n\log n)$了。
tjoi2017 城市
有趣题。首先我们必然断直径上的一条边，然后我们会连两边的直径中点，那么问题是怎么求两边的直径中点，随便取一个直径端点为根做一边的，考虑直径中点总是在到任何一个点距离最大的点上，那么dp求出直径长度，长链剖分，从重儿子到父亲直径端点会沿长链向上shift若干步，总移动量是线性。
cf1776G
虽然反对出这种题，但是还是很厉害!
An Optimal Algorithm for Calculating the Profit in the Coins in a Row Game
pa2010 Termites/hnoi2010 取石头游戏
题意是若干个序列，每个序列可能有一端是锚定的或者没有。两个人每次选一个序列，取走一端，如果是锚定的则只能最后取走，都希望自己获得的总和尽可能大。求最终A获得的减去B获得的。
或者说锚定一端的是栈，没有的是deque。
显然每个人选的个数是确定的。
翻译一下论文。
定义一个策略是状态到选择的映射。定义$\operatorname{val}(a,b)$是A采用策略$a$，B采用策略$b$得到的结果。
如果A固定使用策略$a$，那么结果就是$\min\limits_b\operatorname{val}(a,b)$。为了证明$a_1$不比$a_2$优，我们可以对于每个$b_2$，找到一个$b_1$使得结果不会更大。这里$a_2,b_1$都是我们自己选择的。也就是说我们把证明一个策略不优转化成了一个博弈问题。阅读定理1获得更好的体验。
设最大值是$m$。
定理1 如果某个$m$可以选，那么必然选它。
证明 使用上面那个方法，我们同时进行两个博弈，不妨称为$M_A$和$M_B$。在$M_B$中我们操纵B，而A先手选择了某个序列的某端$t$上的数$x_t$。在$M_A$中我们操纵A，我们让A先手选择一个$m$。根据上面的结论，我们就是要找到一个策略，使得$M_A$的结果总是不比$M_B$小。
首先操纵B在$M_B$中选择$m$。这也是为什么命名为$M$。
接下来进行若干轮，保持$M_B$比$M_A$多进行一步。每轮让对手在两个游戏中各走一步，然后我们反过来走，也就是说如果对手操纵B在$M_A$中选一个数，我们就操纵B在$M_B$中选同一个这样的。
对手选择了$t$的时候我们没法模仿了，因为两个博弈在$t$这里是不同的。不过可以修补一下 :
-
如果对手在$M_B$中操纵A选择$t$。我们也在$M_A$中操纵A选择$t$，尽管这两个元素不同。这样两个博弈在$t$上总是只差一个元素。
-
如果对手在$M_A$中操纵B选择$t$(只考虑$t$上这个元素被选，而不一定是在$t$这一端选，也就是这个元素的另一端空了而选到它也算)。此时两个游戏的状态就相同了。那么算一算发现两个游戏的差距在于$M_A$中你选了$m$丢了$t$上最后一个元素。那么由于$m$最大，$M_A$是不劣的。
第二个case总会出现，否则$t$所在的序列永远不会选完。这就结束了。
引理2 如果$m$不能选，它的两边分别是$x,y$，那么如果一个人，不妨设为A，选了$x$，根据定理1，B必然选$m$，引理2断言接下来A必然选$y$。
证明 如法炮制。现在博弈$M_B$中A选择了$x$，我们操纵B选择了$m$。
和上面一样进行若干轮模仿。还是考虑何时不能模仿了。
-
如果对手在$M_A$中操纵B选择$x$。那么我们操纵A选择$m$。由于$m$是最大的，$M_A$不劣。
-
如果对手在$M_A$中操纵B选择$m$。这说明之前某个时刻有人在$M_A$中选择了$y$。那么我们考虑有人在$M_A$中选择$y$的时候应该怎么办。
-
如果对手在$M_B$中操纵A选择了$y$(如果一直模仿，我们会模仿他在$M_A$中选择$y$)。如果$x$还没有被选，我们在$M_A$中操纵A选择$x$，那么对手必然跟着选$m$。不管$x$有没有被选，此时我们选择$y$。此时两个游戏完全一样了。
-
如果对手在$M_A$中操纵B选择了$y$(此时$x$没被选，否则是case 1)。我们在$M_A$中选择$m$。归纳，那么对手必然在$M_A$中选择$x$。于是我们在$M_B$中选择$x$。此时两个游戏又完全一样了。
-
于是我们知道如果最大值是$m$且不能选，可以把它和两边的$x,y$合并成$x+y-m$。
那么现在我们已经可以解决没有锚定的情况了，也就是每次找到最大值做这样的。
引理3 如果$m$两侧是$x,y$，且$x,y$中某一个锚定，可以把它们合并成锚定的$x+y-m$。
证明 在引理2的证明中去掉case 2。
引理4 如果$m$是锚定的，它和$x$相邻，并且目前还剩$n$个数，可以把它们合并成锚定的$(-1)^n(x-m)$。
证明留作练习。
那么现在我们已经完全会做啦!开个堆就是$O(n\log n)$了。
考虑一些更强力的结论。
定理2 现在$m$不一定是$\max$。如果$m$没有锚定，左右是$x,y$，且$m>x,y$，那么可以把$x,m,y$合并成$x+y-m$，它锚定当且仅当$x,y$中有一个锚定。如果$m$锚定了，一侧是$x$，且$m>x$，那么可以把$x,m$合并成锚定的$(-1)^n(x-m)$。
证明 没太看懂。懒了。
所以我们只需要开个栈，每次拿出前三个看看能不能这么合并，然后就会把每个栈变成单调的，每个deque变成双调的。然后排序即可。
cf1461f
空跌给的。
感觉让人比较智障。
只有一种符号显然。$+,-$全填$+$。$\times,-$填$\times$直到第一个$0$，在这里填一个$-$，后面的全填$\times$。
$\times,+$。$0$两侧必然是$+$。考虑如果一些数的乘积$>nv$，这里$v$是$9$，那么我们必然是乘起来，不过如果两边有$1$我们会改成$+$。否则容易想到一个dp，求出前缀积然后李超树优化，但是这里斜率居然只有$\log(nv)$种，所以直接每个斜率维护最大的截距即可。复杂度$O(n\log(nv))$。
thupc2021 鬼街
据说很经典!
感觉比较厉害啊。根据第一篇题解，考虑如果是有一个$>y$就触发，那就直接每个素数开个堆维护$y$最小的监控器。但是是和$>y$才触发，我们每个素数开个堆维护$\lceil\frac{y}{\omega(x)}\rceil$最小的监控器，那么一个监控器每弹一次，二分一下求出它是不是真的触发了，如果没触发，$y$必然已经减小到原来的$\frac{\omega(x)-1}{\omega(x)}$以下了，此时我们直接remake一下它。复杂度$n\omega(n)\log_{\frac{\omega(n)}{\omega(n)-1}}n\log n$。这里$\omega(n)=6$。
icpc19~20 hong kong I. Incoming Asteroids
一样的trick捏。
xxii open cup gp of Yuquan G. Dynamic Reachability
时间分治。然后发现bitset的时候好像会影响很多点啊。
时间分块。每$K$个分一块，但是一个问题是怎么做到$qK$啊。发现我们好像不是很容易做到。考虑$\frac{qK^2}{w}$是简单的，我们只需要找到所有端点然后把它们之间的连通块拿出来跑一个bitset优化的bfs就好了。复杂度$O(\frac{n^\frac{4}{3}m}{w})$，这里认为$m,q$同阶。算量2e9，不多不少。
ccpc2021 Weihai L. shake hands
考虑这个图有啥性质。发现如果$i,j$有边，$(i,j)$中每个点到$i,j$之一都有边。并且如果其中$k$到$i$有边，$l$到$j$有边，$i<j,k>l$，那么$k,l$必然有边。之类的东西。
这个东西好像没见过。考虑它的补有啥性质。如果原图中$i<j<k$，$i,j$没有边，$j,k$没有边，那么$i,k$也没有边。也就是说这个补是一个可比图。
可比图的最大独立集也就是最长反链。考虑经典的网络流建图，每个点拆成入点和出点跑最大匹配，那么这里只有$O(m)$条边不存在。这就没法用经典网络流算法了。不过有牛逼做法，考虑如果这个图很满我们就必然有完美匹配了，看看它需要有多满，hall定理，如果有$n$个点，我们选了一个大小为$k$的集合，那么每个点要删至少$n-k+1$条邻边，那取$k=n$就爆炸啦。注意到此时对面必然有一个度数非常大的点。考虑我们把删的度数$>K$的点都特殊处理，现在所有点删的度数$\leq K$，那么我们选大小$>K$的集合，邻接的必然是另一部所有点。此时每个点还是至少要删$n-K+1$条邻边，也就是说$K<n-K+1$就赢啦。
那么我们就把两边一起按删的度数从大到小排序，设为$d$，找到第一个$i$满足$d_i<n-i-d_i+1$。显然当$n$足够大，比如$n>\Theta(\sqrt{m})$，这样的点在$O(\frac{m}{n})$处就出现了；否则我们爆力dinic就是$O(n^\frac{5}{2})$。取根号分治的阈值为$\Theta(m^\frac{4}{7})$，对$i$和前面的这些点进行爆力匈牙利，每个点是$O(m)$的，复杂度$O(m^\frac{10}{7})$。现在左右都剩下至少$n-i$个点，而每个点删的度数都满足$d<n-i-d+1$，于是必然存在完美匹配。
如果要构造方案，好像我们还不会快速找到这个完美匹配。
引理1 如果每个点的度数$\geq\frac{n}{2}$，且现在不是完美匹配，则必然存在一条长$\leq 3$的增广路。
证明 考虑现在左部点$u$和右部点$v$还没匹配。如果有边$u\leftrightarrow v$，那就赢了。
如果到处都没有这么一条边。那么$u$的所有邻接点都匹配了，$v$的所有邻接点都匹配了。由于每个点的度数足够大，必然存在一个$u$的邻接点$x$和一个$v$的邻接点$y$匹配。这就找到了长$3$的增广路。
上面那个条件$d<n-d+1$就等价于每个点删剩下的度数$\geq\frac{n}{2}$。考虑如何利用这东西。先处理所有长$1$的增广路，让每条边的至少一个端点在匹配中。然后枚举长$3$增广路的中间那条边，在两侧各找一个未匹配点。关键的观察是这样产生的新的匹配边不会再出现在长$3$的增广路中，因为在第一步中，它的端点的邻接点都已经是匹配点了。复杂度线性。
loj3657 集训队胡策2021 挑战分解质因数
考虑$pq$怎么做。也就是我们知道$pq$和$(p-1)(q-1)=pq-p-q+1$。那么我们就知道$p+q$。那么就可以用韦达定理构造一下了。
考虑无平方因数怎么做。感觉不好做啊。
感觉比较厉害。考虑一个类似于mr的想法，我们知道如果$a\perp n$，那么$a^{\varphi(n)}\bmod{n}=1$。设$\varphi(n)=2^km$，那么把$1$移过来并平方差，我们又有了$(a^m-1)\prod\limits_{i=0}^{k-1}(a^{2^im}+1)=0$。如果这些项中有一个$0$，那就不好，否则由于它们都不是$0$而乘积是$0$，我们都和$n$取一下gcd就找到了$n$的一个因数。
看一眼二次探测定理的证明，发现它确实说明成功的概率是$\frac{3}{4}$。
usaco23feb Pt A. Hungry Cow
看起来是单侧递归线段树例题。以前是管它叫类楼房重建的，从今天开始我要改叫单侧递归了。
看起来我们需要考虑一个点左边留下的非$0$的情况。考虑左儿子区间中有多少个$0$，如果左边来的比这些要多，那么左儿子就被填满了，只需要递归右儿子。否则左儿子留下的是固定的，每个点维护此时右儿子的情况即可。
icpc2020 Shenyang L. Forged in the Barrens
dag定长最短路。很遗憾这东西显然并不四边形不等式。
考虑极差有啥性质。想起最大化极差的一个经典做法是改成任意两个数的差，然后就可以费用流了，这里需要拆点保证包含每个点的区间只有一个。那么我们知道答案是凸的。然后可以写个dp，分治闵和，或者直接模拟费用流。这里只可能在有东西的一段或空的一段中间选或者在相邻的 有东西的一段和空的一段 之间选，线段树支持查询区间左边选一个贡献负，右边选一个贡献正，或者反过来的最大值，然后开个堆模拟即可。
cco2018 Boring Lectures
时间分治。插入一个数，找到附近的$\max$并尝试更新答案即可。一开始先用单调队列扫个答案出来，复杂度$O(n+q\log^2 n)$。
多头给了一个牛逼做法。考虑按$k$大小分块，那么我们断言答案中两个数在其所在块中必然是最大或次大。对于同一块的情况显然正确，对于不同块的情况，如果我们选择了$x,y$，两块的最大值分别是$a,b$，那么选择$a,x$或$b,y$必然不劣，否则我们知道$a<y,b<x,x<a,y<b$，这就成环啦。
slyzoj485 未知来源题
简化之后是，仙人掌，每条边都在至少一个简单环上，求所有点对间最小割的和。
那我们必然割环，割环的话必然割最小的那条边，所以把它先割掉，把它的边权加到同一环的所有边上，然后按树做。树是经典的。
区间平面最近点对
大家都会平面最近点对。考虑按$d$大小把平面分成若干$d\times d$的矩形，那么如果一个矩形中有两个点，就给出一个$\leq \sqrt{2}d$的方案。取$d$为各$\lfloor\sqrt{2}2^k\rfloor$，从大到小枚举一个$d$看是否存在一个矩形中有两个点，那么对每个矩形排序之后，只有每两个序列上位置相邻的点需要贡献，BiT数数就好啦。现在每个矩形中有最多一个点，可以看到的是每个矩形最多和周围$5\times 5$并挖掉四角的矩形产生贡献，并且由于每个矩形中有最多一个点，我们现在处理矩形$A$中的$a$和矩形$B$，只有$B$中出现位置离$a$最近的两个点有用，更远的如果和$a$贡献，就说明$B$中不止一个点。复杂度$O(n\log^2 n)$，但是常数太大，多叉树或者根号平衡会变快。
区间一维最近点对，随机数据
我并不会降低这玩意的复杂度。
usaco23 feb Pt C. Watching Cowflix
https://codeforces.com/blog/entry/113088?#comment-1008590
厉害的。
考虑从小到大枚举$k$，那么一个非常有道理的感觉是选的连通块之间只会合并。把选的连通块缩成一个点，这还是一棵树，树上任意两个选的点的距离$\geq k$，否则直接合并更优，所以考虑以每个选的点为中心画半径$\frac{k}{2}$的邻域，那么任意两个邻域不能有交，而如果直径长度$\geq \frac{k}{2}$，每个邻域覆盖至少$\frac{k}{2}$个点，否则只能有一个邻域，也就是说选的点只有不超过$\frac{2n}{k}$个。建立虚树然后dp即可。
但是因为我们在缩点，所以还有一些小问题，缩起来的点的dfn取其中随便一个点的即可，求lca的时候，就是求出lca再找到对应的连通块。看起来还是比较正常的!
然后这个东西其实是线性的。注意到当$k$减少了$1$，每个连通块的代价都减少$1$，所以如果连通块个数是$t$，$k$减少$1$之后答案至少减少$t$。而答案一共减少不超过$2n$，所以连通块总数不超过$2n$。
1st ucup Slovenia F. Differences
考虑我们容易算一个串和其它串共有多少个位置不同。
考虑我们给每个串一个随机权值，然后带权算这个东西，容易算出结果应该是多少。
pa2022 Palindrom
先把两边换到两种字符出现次数相同，然后把左边和倒过来的右边求个逆序对即可。
洛谷8456 swtr-8 地地铁铁
感觉比较带劲啊。考虑如果有个环，环上同时有D和d，那么环上任意两个点都行了啊，除了$O(1)$对点可能不太行。所以考虑一些连通性操作，因为是点简单路径，缩个v-dcc先，然后如果树上两个点之间有两个方点满足v-dcc中分别有D和d，那肯定就能满足要求了。全D或全d显然不行，问题是一个v-dcc中同时有D和d的情况。
看看v-dcc有啥性质。我们找到共端点的一个D和一个d，设$u,v,w$中$u,v$之间是D，$v,w$之间是d，那么猜测从任何一个点$s$进到v-dcc中，走过$u,v,w$然后从任何一个点$t$出去是几乎必然有方案的。因为这是v-dcc，$u$到$w$还有另一条路径，这就给出一个包含$u\leftrightarrow v,v\leftrightarrow w$的环。从$s,t$分别走到这个环上，如果本来在环上那就不走。如果$s,t$在同一个点上，那么因为这是v-dcc，必然还有另一条路径到这个环上。如果使用了这另一条路径，或者因为本来就在环上而没有另一条路径，此时$s,t$中还是有至少一个在$v$上，那就不是很有救啦。如果$s,t$都不在$v$上，那就赢啦。
然后还是这个环上至少有两个$v$。有问题当且仅当$s$就是其中一个而$t$就是其中另一个，此时可以爆力dfs求解，更简单的方法是如果dcc中有至少三个$v$则有解否则无解。注意到如果还是不行，我们总是可以选择d还是D，也就是说对外面的影响相当于是如果经过这个dcc和别的至少一个dcc就必然有解。那么减去这个情况和路径上方点全部是同一个颜色的情况即可，后者可以直接在圆方树上dfs得到。
cf1511G
也就是每次求一个值域区间减去区间左端点的xor和。不妨考虑减去任何一个$k$。枚举一个$t$，$t-1$位有值当且仅当$(i-k)\bmod{2^t}$的$t-1$位有值，也就是$(i-k)\bmod{2^t}\in[2^{t-1},2^t)$，或者$i\bmod{2^t}\in[(2^{t-1}+k)\bmod{2^t},k\bmod{2^t})$，这里的区间是用 从左端点每次$+1$直到右端点，经过的所有点 来定义的。
注意到这是值域区间，相当于我们在序列上每$2^t$个求后$2^{t-1}$个的和，然后加起来，这样的。差分，求出每个$t$，每个点开始的这样的答案，边界处可能会多加一段，特殊处理一下即可。复杂度$O(n\log n)$。
thupc2022 rsraogps
range subrange range and or gcd prod sum。
这些东西都一共只有$n\log n$段，所以直接枚举左端点，直线乘矩形求和就是$O(n\log^2 n)$。
砍砍你的。考虑如果只有and/or，我们可以对每一位分开，然后就可以前缀和啦。如果只有gcd，好像不太会了。
感觉比较厉害。从右往左扫$l$，注意到当一个$[l,r]$的权值改变的时候影响的前缀很多，但是影响的后缀有均摊(具体为啥可以往后看)，所以我们把$[l,r]\times [l,r]$差分为$[l,n]\times [l,n]-[l,r]\times [r+1,n]+[r+1,n]\times [r+1,n]$，没有$[r+1,n]\times [l,r]$是因为它是$0$。$[l,n]\times [l,n]$这样的东西是好求的。从右往左扫$l$，对每个位置$r$维护$[l,r]\times [r+1,n]$，那么$l$移动一步，我们需要加入$l\times [r+1,n]$的权值和。如果$[l,r+1]$的权值和改变了，这样的事情只会发生$O(n\log n)$次，否则$l\times [r+1,n]$的权值都没改变，因此变化量和上一轮相同，也就是支持修改$b$，$a\leftarrow a+b$这样的，记录上一次推标记的时刻就$O(1)$啦。复杂度$O(n\log v+q)$。
去补了 洛谷8283 MCOI-08 Dantalion 的类似做法，可以看看我关于sdptt22 r1的文章。
未知来源题
有长$n$的序列$a$和$m$个初始为$0$的计数器，每次随机一个$a_i$和一个计数器，给它加上$a_i$，求所有计数器都达到$k$的期望时间，膜$998244353$。$n,m,k\leq 100$。
min-max容斥。我都忘了min-max容斥了!对于每个$j$计算子集$T$内走了$j$步还未结束的概率，求和然后乘上$\frac{m}{\vert T\vert}$(因为min-max容斥需要考虑子集外的影响)，概率可以用方案数来算。为啥是和呢?考虑一个$t$步结束的方案，它会在$j=0,…,t-1$各贡献一次，一共$t$次。
\[\sum_{i=0}^m\binom{m}{i}(-1)^{i-1}\sum_{j=0}^{mk}\frac{j!m}{i^{j+1}}[t^j]{\left(e^{t\sum\limits_l z^{a_l}}\bmod{z^k}\right)_{z=1}}^i\]这个exp，直接展开，发现每次卷上一个$\sum\limits_l z^{a_l}$即可，复杂度$O(n^3)$。外面直接做就是$O(n^4)$，法法可以做到$O(n^3\log n)$。
unr6 D1 C. 稳健型选手 $q=1$
正的序列，你每次取走一个数，然后第一个数会消失，最大化你取走的总和。
结论是，一个方案是我们选的数的集合，那么它合法当且仅当前$2k$个选了不超过$k$个。证明考虑如果选了超过$k$个显然不行，否则，选择第一个还没选的就可以维持这个性质。
进一步的，我们必然选一半，如果$n$是奇数那么最后一个数必然是我们选走，所以可以把它删掉变成$n$是偶数的情况。倒着考虑，就是后$2k$个选了至少$k$个，并且一共选了$k$个，那么我们从后往前每次加入两个数，然后选择还没选的数中的一个。用堆维护即可。
完整题解请见 一些比赛的题解。
也许是唐队长题
正的序列，你每次取走一个数，如果序列长度是奇数，并且你取的数在正中间，你的得分加上它，最大化得分。
结论是，一个方案是我们取的时候在正中间的数的集合，那么它合法当且仅当距离两边$\leq d$的数选了不超过$d$个。证明考虑如果取了超过$d$个显然是不行的，否则，这个等价于从大到小考虑到两边的距离(的$\min$)，每次加入距离$=i$的数(必然是一个或两个)，然后选择不超过一个还没有选择的数。那么如果选了一个这一轮加入的数，我们就把它和另一个加入的数配对，也就是这俩在相邻两轮选走。否则，把选的那个数和这俩中一个配对，原来和它配对的数和这俩中另一个配对，两个新配对交叉的方案必然保持中位数不变。如果$n$是奇数，先删掉中间那个数。对于最大化的问题，用堆维护即可。
k倍动态减法游戏
icpc 2008 asia beijing B. A simple stone game
取石子，第一次不能取完，接下来每一次不能超过上次的$k$倍，不能取就输了。
如果$k=1$，那么所有$2^i$先手必败。如果不是$2^i$，先手可以每次拿lowbit。
如果$k=2$，那么所有斐波那契数先手必败。拿zeckendorf表示的lowbit，因为zeckendorf表示中没有相邻的1，而相距2的fib数，后一个至少是前一个的两倍。
那么对于$k$任意的情况，我们构造一个数制，满足如果两个1可能相邻，那么后一个的位权至少是前一个的$k$倍。也就是说如果各位权是$a$，当然从小到大处理，我们找到目前最小的不能表示的数，那么它就作为下一位的位权，而最小的不能表示的数也就是最大的能表示的数$+1$，我们先选最后一个$a$，然后每次往前找到第一个不比上一个的$\frac{1}{k}$大的$a$即可。
loj6728 u群把妹王
集合划分容斥。来自djq的命名。
只介绍怎么做到$O(n^2)$。首先两维分别钦点一个集合划分，那么如果两维各有$i,j$个行，列的等价类，一共就有$ij$个格子的等价类，非常好对吧!然后乘个容斥系数以在钦点和恰好之间转化，就可以dp出这个钦点的方案数了。关键是容斥系数应该如何算，这里是集合所以设$F$是合法大小的egf，$G$是容斥系数的egf，那么$\exp G=1+F$对吧。
要做到$O(an\log n)$，使用拉格朗日反演直接推那个dp的结果。
vuq的矩阵乘法题
给$n$个长$m$的序列，每次问两个有没有交，$nm$和$q$同阶。
我好像会除$w$。
cf1626 F. A Random Code Problem
大家都会$O(2^knk^2)$。但是$n$好大啊!
考虑一个数贡献的变化只跟膜$\operatorname{lcm}(1,…,17)$的值有关。但是这也有1e7捏。
注意到是求和，所以直接拆贡献即可。这样就可以$O(2^kn)$了。
对一个数可以dp，设$dp(i,j)$表示前$i$轮，现在一共减了$j$的方案数和总贡献，它是一个一次多项式。转移考虑这一轮选不选，如果选要乘$1+(a-j)z$，否则要乘$n-1$表示选了一个别的的方案数。复杂度$O(nk^3)$。
能不能再给力一点啊?考虑膜$17$的余数没有用，所以$\operatorname{lcm}$可以除一个$17$。
考虑对所有数同时dp，设$dp(i,j)$表示现在膜$\operatorname{lcm}$是$i$，进行到$j$轮，的贡献，它是一个一次函数。复杂度$O(n+\operatorname{lcm}(1,…,k-1)k)$。
cf1827 C. Palindrome Partition
问题是证明选最短的是对的!
如果一个串有border，那么一定有长度不超过一半的border。转而考虑周期，如果有不超过一半的周期，让它不停翻倍就必然能得到超过一半的周期。
manacher之后单调栈即可。
hnoi2003 历史年份
最后一个数最小就是直接设$dp(i)$表示前缀$i$最后一个数最小是多少对吧。转移枚举这一段，那么$dp(j)$要比$j+1,…,i$小，这里$dp(j)$只需要记长度，可以用sa判断做到$O(n^2)$。
那么可以注意到$j+1,…,i$总是随$i$增加而单增的，也就是说每个位置一旦可以转移就一直可以转移了。那么对每个$j$向后二分出第一个可以转移到它的$i$即可。
然后问题是怎么让第一个尽可能大，再dp，固定住最小的最后一个数，设$dp(i)$表示后缀$i$，第一个数最大是多少，看起来和前面一样做。
注意到比较大小的时候，两个数去掉前导$0$之后如果长度不同那就直接比出来了，所以我们其实不需要二分，只需要往后找到第一个非$0$的数，然后检查两种情况。可以直接用二分hash来比较，复杂度$O(n\log n)$。
cf1458 F. Range Diameter Sum
看起来是根号题啊。但是啥都没什么想法/cf
注意到直径可以合并，考虑对序列嗯分治，但是直接考虑直径比较麻烦，我们考虑外接邻域，两边分别是$\mathrm{N}(c_1,r_1),\mathrm{N}(c_2,r_2)$，$d=\mathrm{dis}(c_1,c_2)$，那么如果$d+r_2<r_1$或$d+r_1<r_2$则并的外接邻域是$\mathrm{N}(c_1,r_1),\mathrm{N}(c_2,r_2)$，否则直径必然是$r_1+r_2+d$，证明只需要考虑外接邻域的定义是，一个点集的外接邻域是$\mathrm{N}(c,r)$当且仅当有两个来自$c$不同子树的点到$c$的距离是$r$，且没有点超过$r$。更进一步的结论是，并的外接邻域中心是$c_1$到$c_2$路径上距离$c_1$为$\frac{1}{2}(d+r_2-r_1)$的点。
然后问题是有若干个邻域，静态查一个邻域包含的所有邻域的权值和这样的，点分治双指针即可。总复杂度$O(n\log^2 n)$。
但是有更简单的做法，注意到前缀邻域显然是每一个都包含上一个，那么固定左边的邻域，贡献就分成左边包含右边，互不包含，右边包含左边三段，都是单调的可以双指针。问题是要求一个点到一个点集的距离和，支持修改点集，点分即可。但是复杂度还是$O(n\log^2 n)$。