D1
A. stones
这是一个典题。但是不知道在哪/kx
B. tree
树，有一个函数序列f(u)=v，其中v是u向某个给定点移动一步得到的点，每次求区间复合的点值。n≤105，5s。
分块先。零散部分容易线性。
同时移动所有答案，考虑复合一个函数会发生什么。可能会有两个答案相撞，这玩意看起来就很有均摊。缩起直链用块状链表维护即可。复杂度O(n√n)。
但是块状链表太扯淡了，主要问题是我们需要快速分裂一条边，注意到只有O(√n)个函数，所以我们可以直接把它们拿出来作为finger。
C. seq
序列a和置换p，如果ai+1=pai就在i,i+1之间连一条边，支持a的单点修改，或者给区间和x，求区间最大的存在某个ai=x的连通块。n≤106，8s。
包含x比较见鬼。根号分治一下容易√npolylog(n)。
置换是有意义的。考虑我们把同一个置换环重编号成连续的一段，然后把每个数画到平面上，那么问题就是查经过某条横线段的某种斜线的最长长度了，这里边界不完整的段大概是好做的。直接维护答案，修改的时候是两个O(1)个矩形加减。这个感觉就不是很好做啊。
然后比较厉害，考虑我们把一个段都挂到左端点去，那么问题变成插入竖线，删除竖线，求和一条横线交的竖线的最大权值。直接树套树即可。当然可以离线分治砍砍常数。
支配对
编号区间虚树点数
一个点在虚树上，当且仅当它在查询区间中，或者查询区间包含两个点在它的不同子树中。
如果有三个点i<j<k，i,j在不同子树中，j,k在不同子树中，那么i,k就被支配了。
对子树启发式合并，在小的里面枚举一个，大的里面查它的编号前驱后继。复杂度O(nlogn)。
Ynoi2006 rldcot
也就是改成查类似于虚树上的不同深度个数的东西。
2-side矩形数颜色。容易做到O(n√n)。
考虑枚举一个颜色，也就是深度，把查询放到平面上，问题是给这些矩形的并+1。这里是左上2-side矩形所以很容易求并，单调栈即可。
Ynoi2003 铃原露露
也就是求有多少子区间对lca是封闭的。
考虑找到使子区间不合法的对。考虑如果u,v的lca是w。如果u<w<v，那么u,v就被u,w;v,w支配了。如果u<v<w，只需要取最大的u。如果w<u<v，还是只需要取最大的u。启发式合并即可。然后又求矩形并了。线段树维护区间最小值，区间最小值个数，区间最小值=0时个数的历史和。
cf765 F. Souvenirs
典。
codechef minxor
差不多做/mgx
Ynoi2004 rpmtdq
边分治，那么dis就被拆成两个东西的和啦。考虑一对(i,k)，如果i到分治中心的距离d比k更小，那么左侧到分治中心距离≤d且在[i,k]中的点都不会和k贡献，因为它们到i的距离不超过2d，>d的。
杂题
Ynoi2002 Optimal Ordered Problem Solver
也就是2-side矩形向一个side贴。
发现所有修改过的点会贴在所有修改的包络线上。平衡树维护就好了。
劲爆的是可以一边改一边矩形数点。考虑左下2-side矩形，如果它在包络线下答案是0，否则我们把它差分成所有点减去一个上1-side，一个右1-side，再加上一个右上2-side矩形。前两个可以维护，第三个只包含没有被改过的点。
D2
A. a
数最小环个数。O(nm)。
在直径处统计，问题是最短路计数。
B. b
小写字母串，每次查一个区间最长的形如xyxyxyxy…的串的长度。n≤1.5×106,q≤105，3s。
枚举x,y。差分，求出每个后缀的答案，但是发现我们不知道[l,r]中匹配的最后一个字符是x还是y。
结论是，从y往左找到第一个x或y，那么匹配的最后一个字符必然是它。比如如果它是x，那么它到r不能有y，因此如果最后匹配y，这个y必然在它前面，所以其实可以继续匹配它。
复杂度O(nΣ+qΣ2)。
C. c
排列，每个位置还有一个颜色，每次给l,r，求有多少个值都在[l,r]且端点同色的区间。n,q≤5×105，4s，线性空间。
发现排列是1,…,n时这是小z的袜子。所以考虑根号。
对颜色出现次数根号分治，小的部分只有O(n√n)对，把(min,max)拍到平面上，可以根号平衡一下数点。为了卡空间，比如我们扫max，数据结构维护min，那么建立大根笛卡尔树，从下往上扫，启发式合并一个hash table就可以得到所有的对。峰哥好像有些简单做法，但是这个大概并不难写，因为我场上居然写出来了。
大的部分，注意到如果没有颜色的限制可以直接回滚莫队，对每种颜色分开做，把别的颜色缩起来复杂度就是对的。这部分据说非常难写。
总复杂度O(n√n)。
不过好像没有出成线性空间，直接分常数轮跑就好了。
倍增值域分块
处理>x的−x一类的问题。
大概是，如果值域上顺序变了，我们让势能减少一些。
cf702 F. T-Shirts
据说可以一个log。
先考虑俩，这玩意和取膜比较相似，从大到小考虑，每次买连续的一段，那么这一段结束的时候必然折半。线段树维护即可。
或者考虑扫序列，数据结构维护所有查询，那么问题就是≥x的−x并答案+1，x是递减的。倍增值域分块，掉块则爆力重插，就是俩log啦。
劲爆做法是，倒着扫，维护每个钱数的答案，那么如果现在扫到了x，把<x的复制出来接在前面，≥x的打+1标记，可持久化平衡树即可。复杂度O(nlogv)。
Ynoi2007 rgxsxrs
classic。直接倍增值域分块，每个块开个线段树维护序列，只需要区间min以找到是否需要掉块。
但是据说是线性空间，所以需要平衡树，压缩trie或者底层爆力。不知道后两个哪个更快。
Ynoi er 2022 堕天作战
注意到x≥0。每个数如果<x又−x，就变得<0了，此后它总会−x，所以找到小的数爆力，大的数和rgxsxrs一样做即可。
cf1515 I. Phoenix and Diamonds
t-shirts的第一个做法仍然适用。
可以用倍增值域分块重新描述它，如果我们在某块中取不了，那么一直取小块中最大的直到掉块。如果在某块中能取，那么一下就会掉块。
ioi2021 地牢游戏
如果我们赢了同一块中的某个敌人，必然直接进入下一块，否则对于每个块前缀认为其中的都能赢，其外的都不能赢，这么搞一个数据结构，然后每次一直跳直到进入下一块或者赢了这一块中的某个。这是个基环树，树的部分剖一剖，环的部分直接做即可。或者这里倍增会简单一些。为了知道何时赢这一块中的某个，维护最小的初始值使得会赢这一块中的某个。
把倍增值域分块改成更大的进制以卡常。/kx
杂题
图穷匕见。
meta hacker cup 22 final D
树，边权是小写字母，每次给一个点和一个字典序，从这个点开始每次走字典序最小的邻边，并删掉这条边，求最后停在哪个点。
剖先，问题是我们要找到沿重链连续向上或向下走的长度，这给出一些 一个字符比另一个字符小 的限制，二分即可。压位以砍一个Σ，复杂度O(nΣlog2n)。换个静态lct就好啦!
或者直接lct，就不需要处理向上走了/fendou
D3
赢了。但是没完全赢/cf
A. i universal cup ukraine G. Graph Problem With Small n
B. bad
C. computer
四路并行计算前缀字符串hash，最小化操作次数，不能差分。具体一点，有n个字符串，每次操作是给出四个三元组，每个称为ai,bi,ci吧，对每个执行ti=ai+bi，然后对每个执行ci=ti。
可以想到一个12n次的做法，我们两个一块，每次操作做下一块块内的前缀和，并让这一块加上这一块的前一个。不过这只用了三路。
可以想到一个716的做法，我们三个一块，还是每次把一块加上这一块的前一个。
注意到前者块内做的比块间快，后者块间做的比块内快。平衡一下，一个两个的块，一个三个的块，可以做到25。
可以发现下界在25附近。如果某组操作让k个位置变对了，那么我们之前至少要k−1次额外的操作，爆力枚举让1,2,3,4个位置变对的操作组数，可以发现它是25略小一点。
那么问题就是如何卡常啦!
杂题。
ec final 22 Magic
考虑一个间隔有贡献，当且仅当以它左边作为右端点的区间或以它右边作为左端点的区间
xx open cup gp of moscow Hidden Graph
考虑不停删掉度数≤k的点，然后我们就发现了一个k+1染色。
考虑每次加入一个点，找到它到前面所有邻边，那么既然可以O(m)地找到一个k+1染色，我们找到这k+1个独立集，然后每次和一个独立集查，如果有边，就必然是和这个新点的连边啦。这样最多会有n(k+1)次查不到，整张图有nk条边，刚刚好。
xx open cup gp of moscow Graph Coloring
也就是每个点的入边和出边的颜色集合不交，并且每条边起点的出边和终点的入边颜色集合有交。我们只钦点入边，出边是入边的补，那么问题变成没有一个集合包含另一个。这是一个可比图最大独立集，跑最长反链即可。或者直接选择所有大小为7的子集。
xxii open cup gp of bytedance Graph Operation
结论是度数对应相等就行啦。显然这是必要的。考虑随便找到一个点u，我们现在希望把它的邻接点v换成w，也就是说w现在不和u邻接。如果w和某个t邻接，而u最后不邻接t，那么操作一次就好了。劲爆事情是，显然操作可逆，我们同时在正图和反图上做，那么只用这个必然可以让u在两边的邻接点相同。
考虑如果正图不能操作，那么u邻接所有w的邻接点。如果反图不能操作，那么w邻接u的所有邻接点。因为u邻接w而w不邻接w，u的邻接点和w的邻接点不完全相同，所以正图上u的邻接点比w的邻接点多，对称的，反图上u的邻接点又比w的邻接点少，这就与度数对应相等矛盾了。
使用bitset优化找t的过程。
qoj141 8染色
考虑二染色是可以做的，那么我们发四组，就可以做到2n个bit。
劲爆事情是，如果一个点度数<8，我们可以直接删掉它，最后染邻接点没出现的颜色即可，那么这样做完之后每个点度数≥8，也就是说点数不超过m4了。这就赢了。
discover sigapore 19 by moscow workshops D5 300iq contest Good Coloring
问号构造。考虑钦点从编号小的颜色走到编号大的，那么跑一个dag最长路，显然每层是一个独立集，也就是说取这些层就得到了一个染色。
moscow workshops icpc programming camp 19 D2 Colored Graph
问号构造。考虑随便找一个哈密顿回路，如果所有边同色就结束了，否则必然存在一个点的两条邻边颜色不同，删掉它递归下去，最后必然可以加回来。
ec final 22 Rectangle
如果三条线同方向。直接线段树优化dp。但是直接枚举中间那条就是线性啦。
如果三条线不同方向。找到和另两条不同方向的那条，枚举它在哪，问题是支持插入删除，求用两个点覆盖所有区间的方案数。
考虑往平面上画，那么
ec final 22 Map
gcj 22 final Wonderland Chase
考虑如果所有点至少是二度，那么A必胜，因为他可以等B走到一个邻接点，然后走到另一个。这里重边视为一条。
剥掉所有一度点，它们形成若干树。B的策略是走到树根拦截A，A的策略是走到树根。如果B更快，那么A会尽可能往上走，然后走到子树中最深的点，否则A赢。
D4
A. grandmaster
有n个向量，构造一个方案，选两个切成两段(可以切出实数，第二次可以选第一次切出来的)，然后分成两组使得和相等。n≤105。
B. toptree
树，点权，求对于所有边集的子集，每个连通块min的和的和。n≤105。
考虑一个点何时贡献，从大到小加点，那么我们要做一个几乎是 包含某个点的连通块个数 的dp，lct ddp即可。
但是这个做法太复杂啦!考虑直接dp，设dp(u,i)表示u子树，min为i的连通块的贡献和，转移就是min卷积，可以线段树合并。统计答案只需要全局求和。
C. circle
环，你可以选择一个i，做操作ai−1,ai,ai+1←ai−1+ai,−ai,ai+1+ai，求最小的操作次数使得所有数≥0。多测，∑n≤3×106。
这个操作比较经典，前缀和一下就变成交换两项了。但是这是环，所以开头和结尾会很奇怪。
考虑强行扔掉开头结尾，我们做一个无限长的前缀和pi=pi−1+aimodn，这里面每个数都是未定义的但是我们仍然可以考虑大小关系，可以发现原序列合法当且仅当这个前缀和递增，并且此时操作彻底变成交换相邻两项了。我们不能对无限长的序列求逆序对数，但是可以对每个位置定义后面比它小的数的个数ri，因为原序列的总和，设为s，必须是正的(负的必然误无解，0有解当且仅当全0)，所以我们知道每个r必然有限。
考虑操作i之后r会如何变化，modn=i−1,i位置的p会交换，现在只考虑i−1,i两个位置，那么ri−1,ri也交换了，如果pi−1<pi那么ri−1会增加1，pi−1>pi那么ri−1会减少1。
于是问题是我们要求r1,…,rn。ri=∑pj<pi[i<j]+⌊pi−pj−1s⌋。那个[i<j]就是个逆序对数，问题是[pj<pi]⌊pi−pj−1s⌋的和。
考虑把⌊s⌋扔掉，我们扔掉之后全部加起来，减去pi−pj−1mods，然后除一个s。中间那个东西就是pi−1mods−pjmods+[pjmods>pi−1mods]s，于是这是一个二维偏序。赢了。
cco20 D2 Shopping Plans
收录于 未归类问题。
discover singapore 19 D5 Equal MEX
考虑如果有一个0，那么每一段都要有一个0。
如果还有一个1，那么每一段都要有一个1，因为每一段已经都有一个0了。
所以所有段的mex是相等的，都等于全局mex。直接dp即可。
xx open cup gp of moscow Joining Points
不交就非常好对吧!
注意到每个颜色必须画恰好一个弧，所以我们不可能画超过n个弧，所以dp，只需要记最大值及其方案数。
问题是这是环，可以枚举随便一个颜色选了哪个弧，然后从它断开dp。
cts22 D1 独立集问题
如果全正，可以发现我们只需要抛弃一个最小的。但是这个没啥用。
如果有负数。考虑如果对一个点进行了一次操作之后，又进行了一次，效果就是把它取负了。于是被操作产生的数在最后的贡献必然可以是正的。大力dp，状压父边两侧有没有选，如果选了谁先谁后之类的即可。
xxii open cup gp of yuquan The Profiteer
固定一个端点，另一个端点是一个前缀。
分治。问题是如何O(nk)求一个。直接二分，如果向左递归，那么右边都不会涨价，如果向右递归，那么左边都会涨价，所以我们只需要加入O(n)个元素。
xxii open cup gp of yuquan Dynamic Reachability
时间分块。
ptzsc20 D1 Raid
考虑怎么求最少的逆序对个数。考虑折半，但是合并需要归并。
考虑如果现在考虑了前i个，后面的数把值域分成若干段，那么每一段只有选多少个有用。
考虑这玩意状态数有多少，只考虑一个i，那么相当于i+1个和为n−i的数乘积最大是多少。考虑k个和为n的数乘积最大是多少，应该是(nk)k。导一导，这玩意在k=ne的时候最大，所以复杂度是˜O(ene)。
xx open cup gp of zhejiang Fast as Ryser
收录过，但是remake。
考虑爆力怎么做，状压dp，记每个点是否已经匹配。
xmas contest 22 Fast as Fast as Ryser
考虑
xvii open cup gp of romania Salaj
看起来很劲爆。考虑我们如何构造一个图，首先scc数量单减，如果一次操作减少了k个scc，我们可以建一条链，只有1所在的scc可能非平凡，这样只需要把1所在scc后面第k个点连到1。看起来不太能用更少的边了。
问题是边也可能太多，导致链已经穿过所有点，那么我们就顺着链连。如果顺着链也连满了，连1所在的scc。如果边数还要大，那就没救了。这样方案是唯一的。
dp，设dp(i,j,k)表示长i，ai=j，链长为k的方案数。复杂度O(n4)，可以前缀和优化到O(n3)。
D5
由于A1 B1都被南夫拉斯势力做过，换了，所以今天有五题。由于A2也被南夫拉斯势力做过，今天unrated。
A1. a
树，求有多少种方案加上一些边，使得它变得边双连通。n≤5000。
容斥，钦点一些边不被覆盖，然后只需要记u所在的连通块大小就可以转移啦。
A2. aa
树，从s出发随机游走，每一步等概率走到一个邻接点，走到1就停下。随机把k条边变为指向1，求步数的期望。n,k≤106。
手动主元法消消，可以发现如果k=0，设f(u)表示现在在u，走到父亲的期望步数，是很有意义的。这玩意的转移是个几何分布，设度数是d，我们需要期望d次走到父亲，这样从u出发有d步，还有d−1次等概率走到一个儿子，也就是f(u)=d+d−1d−1∑vf(v)。那么f(u)就是u子树所有点的度数和，答案就是s→1上每个点的f之和。
现在k>0。考虑一个点的贡献，如果它不在s→1上，如果它到s→1的链上有边指向1，那它不会贡献。否则，它儿子的父边可能被选，枚举有多少条被选，二项式系数选选即可，然后它的贡献还要带一个链上到第一条被选的边的距离的系数，枚举这个距离，这里是个上指标求和。如果它在s→1上，还要考虑它的父边被选的情况。
B1. b
dag，边权可能是a或b，每次给a,b，求1走到某个点的最短路。n≤5×104,m≤105。
直接跑凸壳。复杂度O(n23m+qlogn)。
B2. bb
给定n×n的矩阵a，你要给每行i分配一个si，每列j分配一个tj，使得ai,j+si+tj≥0,∑si+∑ti=0。n≤500。
看起来像是km的顶标。我们就是要对−ai,j这个完全二分图找一组(最大权完美匹配的)可行顶标使得顶标和为0。
所以如果km求出的最小顶标和>0，那么必然无解。如果最小顶标和=0，那么就找到了解。如果<0，直接给随便一个加上一些即可。
C. c
序列，每次可以交换相邻两个，对每个前缀求把它变得双调(先增后降)的最小操作次数。n≤5×105。
从大到小扫，发现加入一个数的时候，它放在最前面则恰好跟比它大且在它前面的数贡献一次，放在最后面则恰好跟比它大且在它后面的数贡献一次，每个数是独立的。
因为我们只往后加数，前者不变，后者只会变大，每个数只可能从后面切到前面，线段树维护即可。
图论。
先补一下km是啥。
将最大权完美匹配对偶，问题变成，每个左部点一个变量x，每个右部点一个变量y，要求xi+yj≥wi,j，最小化∑xi+∑yi。
联合省选23 D1 B. 城市建造
比较容易看出的是缩v-dcc，然后每个v-dcc内的边要么全断要么全不断，并且选择断的v-dcc在圆方树上是一个连通块。
k=0比较经典。枚举连通块大小s，所有子树大小为s的倍数的点的父边都要断。如果恰好产生ns个连通块，那就对了。
k=1时。注意到圆方树的重心必然断，所以我们以它为根，那么一个v-dcc断了，的祖先考虑子树大小<s的必然不断，≥s+1的子树中必然有一个断了，所以必然要断，
联合省选23 D2 B. 填数游戏
写写我场上做法。图论转化大家都会了。基环树是简单的。考虑树，猜测存在某种类似于center的东西，使得最优策略是让所有边都指向它，换根dp即可。我调出枚举根的时候只剩10min了，所以没有换根是64pts。
dmopc22 contest2 F. Yogyakarta Elevators
相当于每个电梯是一个团，然后无向图传递闭包。那么不行当且仅当存在一个点没有电梯，或者存在两个出现过的电梯不连通。
那么对于每个左端点，不可行区间的右端点就是m个区间的并，每个左端点表示一个电梯出现，每个右端点表示一个电梯合并进连通块。从右往左扫，可以维护出每两个电梯何时合并，然后枚举一个合并时间就可以做到O(nm2)。
只需要维护mst。每次会加O(m2)条边，但是其实我们只要加任意一个生成树，也就是O(m)条，直接kru地remake mst，复杂度O(nmα(m))。
考虑怎么线性地合并mst，发现因为加的边权都一样，
cf235 D. Graph Game
考虑树怎么做，考虑一个点贡献次数的期望，考虑类似于快速排序的分析，计算u作为分治中心时v在u分治块中的概率，发现它就是1d(u,v)。
bjoi2018 染色
收录于 oi题选做。
coi 2010 ROBOTI
我们可以知道到底走没走。让一个波特走整张图，然后另一个的位置就知道啦。
D6
A. a
cf1799 F. Halve or Subtract 加强版
n≤105。
只有最大的若干个数会被操作。把数分成≥2b,≥b,<b三段，那么第一部分直接塞满，第二部分必然是一个前缀都选，然后一段选×12，然后一段选−b，然后如果有数没选，第一段长度必然是0否则不优，否则考虑第三部分，必然是一个前缀−b，然后一段选12，然后一段不选。枚举第二部分第一段长度，那么单独的−b的个数就确定了，考虑两边的答案关于−b个数都是下凸的，做闵和即可。除去排序，复杂度O(n)。
也可以模拟费用流。让我想考虑一下类似的图是不是总可以简单地闵和。
B. b
环，给若干个弧，你要给每个弧染黑色或白色，使得对于每个点，包含它的弧(弧包括端点)的颜色不只有一种，可能无解。n≤105。
我做法是啥，考虑如果是链，贪心即可。如果是环，如果我们可以确定方案的一部分，使得有一个已经合法的点(可以只是一个点而没有长度)，那么从这里断环成链即可。考虑找到最长的弧，把它转成[0,r)，然后找到包含0的弧中左端点最左的[l′,r′)，那么如果这俩弧颜色不同，0就合法了，如果相同，不妨设都是黑色，那么必然还得有一个别的白色弧来覆盖0，由于我们选的是最长的，它必须包含在[l′,r)中，而由于[l′,r)已经有了黑色，完全包含在其中的任何一个弧选白色都是不劣的。这就结束了。
C. c
n×∞的棋盘，每个格子可以放一个炮或不放，如果两个棋盘可以通过若干次交换两行或交换两列变成相同的，那么它们本质相同，求有多少种本质不同的放炮的方案，使得没有两个炮可以互相攻击。n≤105。
还是建个二分图，发现没东西的列可以扔了，那么本质相同当且仅当图同构。环和链肯定不同构，环和环、链和链同构当且仅当长度相同，所以我们就是要计算11−z(1(z2;z))2，这里需要注意单点是环也是链，而且没有方向。直接q-二项式定理即可。
网络流。
蜥蜴
cqoi2012 交换棋子
拆点，匹配。感觉我还是不会匹配。
bjwc2018 餐巾计划问题
icpc06 beijing 狼抓兔子
平面图大师。
D7
A. string
01序列，支持单点修改，或者查询一个区间和一个thue-morse序列的区间的汉明距离。n,q≤3×105。
被根号log冲爆了。
thue-morse某种意义上是循环的，所以直接分块就很好算了。
B. permutation
给一个排列，对每个前缀求有多少个子序列离散化后形如2,1,4,3，其中1,2可以相同，3,4可以相同。n≤5×105。
1,2是顺序对，1,3,2只需枚举3，2,1,3只需枚举1。还是2,1,4,3最为困难。
考虑把2,1挂在2，数据结构维护4的个数，但是发现加入1的时候4的个数会变。考虑容斥成1,1,4,3减去1,2,4,3，这样就不会变啦。复杂度O(nlogn)。
C. rbtree
有一个栈，有一个操作序列，每个位置可能是push 0，push 1，或pop。如果一次pop了一个1，那么下一个push的数会被改成1。支持区间取反push的元素，查询执行一个区间的操作之后有多少个1。n≤6×105。
不会修改push和pop的匹配。考虑一个push只会影响pop它之后的第一次push，所以我们从它向那个push连一条边。那么一个点会变1，当且仅当连向它的点有一个1。也就是说答案就是所有1和根的斯坦呐树大小。从左往右就是一个拓扑序，所以线段树维护区间第一个1和最后一个1即可。
但是，可能，这个区间不是连通的。首先加入足够多的pop弹空，然后加入个push使整棵树连通，那么如果现在要查询[l,r]，考虑l左边第一个push，设为t，把它到根的链加入这棵树，它就必然是连通的了，具体一点就是把t和根两个点加入斯坦呐树。最后删掉这条链只需要减去t到根的距离。
数数。
ATjsc2019_qual_f
如果没这个限制，隔板法即可。
枚举排序后m位的数是啥，有多少个，那么比它小的数和比它大的数的个数就要求我们拿出第二个元了。这就不好，转而考虑m和m+1位不同，枚举m位的数是d，那么问题是选m个≥d的数且有一个d，和n−m个<d的数的方案数，前者隔板，后者容斥，钦点≥d的数的个数，然后隔板。复杂度是调和数。
cf1264 D2. Beautiful Bracket Sequence
又见面了。
也就是找一个子序列使得深度最大。其中对深度没有贡献的匹配括号都可以删去，所以我们找到一个位置使得左边左括号和右边右括号数量的min最大，然后选择这些作为这个子序列即可。
因为是两个相反方向单调函数的min，这等价于左边左括号和右边右括号数量相等。枚举最小的这样的位置，枚举数量，然后选选即可。数量的枚举是个范德蒙德卷积。
arc146 E.
扫值域，dp，设dp(i,j)表示现在填了1,…,i，有j个间隔两侧都是i的方案数，不过还要单独考虑两侧。我们可以用k个i+1生成k−1个新的间隔，那么可以注意到每个i只有一个j可以转移到。
luogu6276
阶就是环长lcm对吧。枚举一个素数幂，考虑它不出现的方案数，那么ban掉所有是它的倍数的环长，
不等关系
容斥，钦点一些>变成<，那么每个连续段是无序的，钦点出连续段即可。发现可以分治法法。
agc060 D.
这玩意就不太阳间了。考虑可以对两个序列同时跑 不等关系 的dp，也就是分别记当前连续段长度，复杂度O(n3)。
考虑继续容斥，我们给(<,<),(<,?),(?,<)各分配一个系数，这样只需要记上一个(?,?)出在哪里。复杂度O(n2)。发现直接就是11−z复合什么东西了，法法即可。
cf1188 E.
考虑如果钦点了每个颜色被操作的次数，要判定是不是能这么操作，那么每次操作出现次数最小的颜色，如果有颜色不够了那就不行，否则必然可以。
注意到如果有至少一个颜色操作0次，那么两个方案不同当且仅当有两个颜色被操作次数不同。
考虑这个判定还是不够好，我们转化成，如果颜色i有ci个，那么在前ci+1次要操作它至少一次，在前ci+t(k−1)+1次要操作它至少t+1次。看起来根据那个贪心，这是充要的。
但是这个判定还是不够好，注意到如果在前ci+1次能操作它至少一次，后面的也必然可以操作了，因为只有恰好k种颜色，每轮的操作数必然够用。也就是说我们操作过的数的值域前缀和满足si≤i之类的东西。
找到第一个爆炸的时刻，那么在此之前每个数可以随意选操作次数。
D8
完全错误估计了BC的trick普及度。
A. logo
cqoi2015 标识设计
/cf
枚举三条竖线，从上往下dp。不是很阳间。
B. point
xviii open cup gp of Ukraine K. Dance
数轴上有一些点，如果有一个点x，你要选择x+d或x−d，然后用一些区间覆盖你选的这些点，一个长k的区间代价是a+bk，最小化总代价。n,x≤150,1≤a,b≤106。
选择的话，相当于x+d,x−d至少选一个。
考虑如果选完之后一个间隔长度是k，那么我们就会选min(a,bk)。
考虑我们有关于最近的那个的贡献，还有相距2d的限制。
考虑每个位置选没选，按2d大小分块，把这些块当作行，排成一个矩阵，此时只有每个位置和上下的限制，以及和这一行上一个1的限制。但是这个不够局部，我们转而考虑每个位置在不在一个选了的区间里，现在行上的贡献也变得局部了。根号分治，如果2d很小，竖着扫，也就是依次扫每一块。如果2d很大，横着扫，相当于每次填一个mod2d等价类，还需要枚举一下第一列的状态以和最后一列拼起来。轮廓线dp即可。复杂度˜O(2√2v)。
C. rabbit
给一棵树，有m个未确定的点xi，q个限制，每个表示xa,xb,c的y-center是d。构造一组可行的x。n,m,q≤150。
2-sat。给每个x在每个点建一个变量ti,u，问题是如何限制ti,…至少有一个1。因为这是一棵树，考虑做个子树和，这样我们只需限制根是1，并且可以发现限制都是子树相关的所以恰好可以表示。然后直接连复杂度就是O(n3)，可以前缀和做到O(n2)。
如果这是一般图，只需要使用杏仁就可以规约色数。
usaco23 feb Pt C. Watching Cowflix
he_ren讲了一个top tree做法，但是我不懂。
考虑猜测随着k变大，我们选的点必然是越来越多。注意到如果两个连通块距离≤k，那么
loj2398 自然公园
注意到删掉一个点之后，剩下的点最多分裂成7个连通块。考虑我们可以查u到一个连通块有没有边，我们只允许从它中转，然后看看能不能到点集中任何一个点即可。那么我们只需要跑一个dfs树，在dfs序上二分。然后挖掉这个点继续做，这会产生不超过7个连通块，可以O(1)地知道u到每个有没有边。
问题是我们还得加点，于是我们希望加点过程中连通块数尽可能少。直接让它是一个连通块。考虑如果尝试了u，它到已知部分S没有边，那么我们找u到S路径上随便一个点，尝试加入它，直接二分就可以找到这么一个点。如果加上之后还不连通，那么继续尝试直到连通。这样每个点只会被加入一次，付出log的代价。
总复杂度O(nlogn+m(d+logn))。
cf1801 E. Gasoline Prices
相当于链到链对应位置合并，维护所有区间长度的乘积。
静态lct维护链hash值。
loj2785 交换
好像被xtq搬过zroi。
贪心。可以注意到只有到根的链和链上每个点的儿子可以换过来。dp，设dp(u,i)表示u子树，u现在是i的最小字典序，i只有log个，复杂度O(nlogn)。但是比较字典序需要比较序列，所以其实是O(nlog2n)的。
也可以直接贪。考虑要让一个位置是某个数的方法是唯一的，枚举要哪个数，维护每条边用没用，直接爆力check即可。
codechef Balancing Network Revisited
注意到2i−1,2i各操作一次就达到n2。
考虑维护若干个对和孤立点，每个对都被操作过一次，并且现在可以让其中任何一个是1另一个是0。操作两个孤立点则得到一个对，操作对和孤立点则
-
如果操作孤立点和1，把0,1互换，并让孤立点和新的0成为新的对，1成为新的孤立点。
-
如果操作孤立点和0，让孤立点和新的0成为新的对，1成为新的孤立点。
操作对和对也是类似的。
-
如果操作0和1，
-
如果操作两个0/两个1，0,1互换一对，这样当你想要改的时候，可以改为互换另一对的。
构造方案的话，直接胡乱维护一下就好啦!大概是要维护互换会发生啥，好像就是如果把换一对改成换另一对看成另一种操作，只要打一个取反标记。
joisc23 D2 A. Belt Conveyor
考虑我们希望让两个物品不可能重合，此时可以推出每个物品从哪里来。考虑按深度mod3分类，这样就不会重合啦，那么我们每次可以确定每个还未确定的点的一条邻边的方向。
这个还是不够好，我们每次选择一个极大的点集，使得对于每个点，没有距离在3以内的点被选，如果有k个还未确定的点，这样的点集大小至少是23k。于是只需要查询log轮。
joisc23 D2 B. Council
考虑如果最后那个阈值是k，并且现在已经删掉了一个数，那么如果有一位出现k次，删掉这一位是1的会让答案减少，此外啥也不会发生了。相当于查和某个数x and的最小的popcnt。考虑枚举and，但是这会算小。考虑枚举or来容斥，or只会算大，所以就赢了。因为会删一个数，维护两个特例。
但是这个法嘛塔比较智障，考虑直接批量处理 从集合中一个数出发，每次修改一位，直到完全改成查询的x 这个过程，也就是设dp(i,j)表示前i位是查询的x，后面的位是集合中某个数的最小答案，转移枚举下一位查啥，而初值是每个集合中的数。
gcj23 farewell contest Round C D. Game Sort
如果有相邻两个字符，前一个比后一个大，那就赢了。但是这要求k≥4。
先考虑k≥4。现在它是单调递增的，如果有一种字符出现至少三次，也可以分出一个aa a，那么就赢了。
如果仍然不存在这样的字符，那么可以感觉到必然无解。
考虑k=2，枚举分段点，比较前面的最小字典序和后面的最大字典序，那么依次比较每个字符即可。可以注意到必然是前一半全相同且是最大的字符，且这个最大的字符在这一段出现次数比后面多。
考虑k=3。考虑找到最后一个最大的字符，如果它不在最后一位，我们可以把它单独划出来。如果第一个最小的字符不在第一位，也可以把它单独划出来。如果有一个最小的字符不在第二位，也可以把它单独划出来，这样它必然比第一段小。
否则，不管怎么切，第一段都必然是最小的段，因为只有第二位可能是最小的字符了，不可能产生一个比第一段更小的段。所以问题变成让第二段比第三段大，和k=2类似，找到一个不包含n的最大的字符的连续段，使得这一段中最大的字符比后面出现次数多即可。
joisc19 D1 Meetings
随机两个点u,v，跟所有w查，那么w在链上当且仅当答案是w，并且这可以求出每个点在链上哪个点的子树中。还需要求出相对顺序，我们通过查询u,w1,w2就可以知道w1,w2哪个在前哪个在后，sort即可。
首先sort的复杂度是O(nlogn)，因为每个点只会参与一次sort。
注意到经过边分的中心边的概率是Ω(1)的，所以复杂度是O(nlogn)。这里认为k=18是常数。不过它看起来不怎么常数啊?
或者有个确定性做法，加点，维护一个点分治，那么可以通过和每个邻接点查一下得到应该走进哪个子树，走到一条边的时候查一下它和端点，就可以知道这条边发生什么变化。如果按子树从大到小查询应该走进哪个子树，那么如果我们查了k次，子树大小至少减少到1k，所以复杂度就是O(nklogkn)。
但是这个需要卡一个12。考虑我们走到一个分治中心，问查询点和它的两个儿子，那么问题是如果答案是分治中心怎么办，此时查询点必然在它到两个儿子的边上，判断是哪条边即可。
现在考虑那个随机做法的复杂度，注意到链有至少12的概率砸中重心，并且它对儿子个数也是期望按顺序随机抽中的，所以这俩做法复杂度是一样的。
D9
A. tree
图，对每个边数求连通生成子图个数。n≤15,m≤200。
直接取ln。转为点值以加速边数上的乘法。
让我来写个半在线卷积把大家都杀了。
B. difference
cf1500 F. Cupboards Jumps
未知序列，给每相邻三个位置中max和min的差，构造一个序列符合它。n≤2×105,v≤1012。
dp。发现我们只需要记差，所以设dp(i,j)表示前i个，|ai−ai−1|=j是否可行。那么设i−1,i,i+1的限制是b，如果j<b则可以转移到b或b−j，如果j>b那就没救，如果j=b则可以转移到0,…,b。
那么也就是支持截断一个后缀，塞一个点，翻转一个前缀，也可能会全部推平。注意到推平产生一个线段，塞的点总在最前或最后，所以可以用双端队列维护，胡乱打打全局标记就赢了。
C. function
cf1098 F. Ж-function
我好像会莫队二次离线，但是还是看看polylog吧嘉然们!收录于 几个不需要静态top tree的静态top tree问题。
dp。
cf1810 G. The Maximum Prefix
经典地，设dp(i,j)表示前i个，maxkak=ai+j的概率，
agc061 C. First Come First Serve
这玩意就是若干个两个端点都单调的区间。
heren做法比较厉害，考虑我们贪心构造字典序最小的方案，那么这个方案当然是唯一的，我们对可能出现的方案进行dp，一个方案不可能出现，当且仅当有一个数的区间中没有一个点被选，但是它选了b。容斥，钦点出这样的区间，和它相交的区间必须选在它外面的那个，不和被选区间交的区间是自由的。dp即可。
arc134 E. Modulo Nim
又见面了。
arc156 E. Non-Adjacent Matching
排成一个圆。
经典地，如果要构造一个度数序列，我们不停让剩余度数前两大的点连边。那么如果有一个点度数超过一半必然无解。但是如果它俩相邻就不是很好。
注意到我们可以调整一下让一条边换到里面去，也就是a↔b,c↔d→a↔c,b↔d。如果一条外侧的边不能换，那么剩下所有边都和它有公共端点，那么这两个点的度数和要超过总度数的一半。这也几乎是充分的，因为这种东西我们显然是构造不出来的啦。剩下的条件是所有点的度数和是偶数。
注意到相邻且度数和超过总度数的一半的点要么没有，要么只有一对，要么是相邻的三个组成两对。先算总数，减去钦点一对的，此时两对的会被减两次，再加上钦点两对的。
对于没有限制的，直接容斥，隔板法。
对于后两个，总和不超过4m。对于钦点一对，钦点1,2是那一对，枚举x1,x2，可以背包。
对于钦点两对，钦点1,2,3是那两对，枚举x2，
abc290 H. Bow Meow Optimization
类似于 方差，狗和猫分别是单峰的。复杂度O(n4)。
joisc23 D1 B. Festivals in JOI Kingdom 2
joisc23 D3 A. Chorus
非空是没用的。考虑如何判定，找到第一个b，如果前面有t个a，那么我们选择最靠前的t个b。于是也就是，第i个a匹配第i个b。
joisc23 D3 B. Cookies
考虑给一个每个盒子装的数量，如何判定能不能装进去。这是个完全二分图的多重匹配。类似于hall定理，
D10
A. coin
01串，有一些位置没有确定，给定其中0,1的个数，构造一个方案，最小化最长连续段的长度。n≤106。
二分答案，然后单调队列优化dp求出最小和最大的0的个数，设方案分别为a,b，如果限制的0的个数在[a,b]中，那么我们取a的一个前缀和b的对应后缀拼起来，其中必然有一个答案。显然0的个数是连续变化的，问题是两侧拼起来的位置两边可能是相同的字符，此时向一边移动要么不会改变0的个数，要么会让两边变得不同，所以忽略它即可。
好像被各种贪心冲爆了。
B. segments
数轴上有一些线段，两个线段要么要么包含，且没有两个端点重合。给每个线段选一个非空子线段，要求两两不交，最大化总长。
dp，自顶向下决策，需要记子树外在子树内选了多少区间。注意到如果子树大小为s，那么子树外最多选s+1个，所以复杂度是树卷积。
C. upup
两个严格递增序列a,b，求从a出发，每次给两个不同的数+1，到达b，且任意一次操作后没有两个相等的数的方案数，膜109+7。n≤30,ai,bi≤200。
一眼 雅礼集训2017 D11 path，鉴定为lgv lemma。考虑把给两个数+1的操作拆成两个，这样类似于斜杨表计数的做法就能算啦，然后对2i−1,2i操作了同一个数的策略进行容斥即可。需要给一个元素是O(nv)次多项式的矩阵算行列式，插值即可。复杂度O(n3v2+n4v)。
然而爆了ub。以后要开sanitizer测大样例。
杂题。
agc043 D.
也就是归并一下。
考虑如果一个triplet中a1>a2，那么弹a1之后必然立刻弹a2。
考虑如何判定一个序列能不能生成，如果ai>ai+1，那么ai,ai+1必然来自同一个序列。那么分成若干连续下降段，段首之间是上升的，每一段长度不能超过3，长2的不能比长1的多，长3的必然自己一段。记一下长2的个数和长1的个数的差，复杂度O(n2)。
arc118 E.
什 么 ?
还是经典容斥，设dp(i)表示现在在(i,pi)的方案数，但是我们不知道pi是多少捏。考虑我们要钦点一个上升子序列，设dp(i,j,k)表示结尾于pi=j，包含k个?的所有上升子序列的贡献和，最后乘上未确定的数随便排的方案数，可以前缀和优化，复杂度O(n4)。
考虑如何做到O(n3)，注意到中间的系数仅是路径数，可以类似于agc001 E. 的做法来批量转移。再来考虑那个范德蒙德卷积做法，
arc114 F.
可以想到后缀排序，选整个串和前k−1大。
哦，这是个排列啊!
注意到越分字典序越大，所以我们可以先最大化答案和原串lcp的长度。二分这个长度k，如果后面还有k−1个串比原串大那就行。对
cf1672 G.
还是给每行每列建一个点，那么每个操作相当于取反
注意到n,m都是偶数的时候，所有操作是线性无关的。如果有一个是奇数，那么
sdoi2017 硬币游戏
arc117 E.
这是一条折线。考虑扫值域，设dp(i,j,k,l)表示扫到i，长j，有k个接头，有l个区间和为0的方案数。枚举一共留了多少，插板分给接头，复杂度O(n6)。
arc117 F.
差分约束，但是这是环，所以不太好办。
考虑二分总和，这就赢了。但是复杂度是O(n2)。
观察一下，发现环要么经过0←2n,0→2n，要么经过n，所以跑个最短路即可。但是最短路还是不是很会，好消息是这里图性质很好，可以直接dp。
cf1608 F.
感觉很厉害。
dp，设dp(i,j)表示前i个，mex=j的方案数，那么mex只会变大，如果从j1变到j2，那么这个位置必然是j1+1，而j1+2,…,j2都在前面出现过，可以钦点出它们的位置，而前面不能出现过j1。最后有若干个数没有被钦点，但是它们可以是的数不太一样，不过一个数只是不能等于后面出现过的任何一个mex+1，可以在这里留一个接头，到它比mex小的时候再确定。dp，设dp(i,j,k)表示前i个，mex=j，有k个数比mex大且未确定的方案数。可以前缀和做到O(n2k)。
cf1266 H.
状态写成一个向量，非常好对吧!但是这不是一个线性变换。
设出进入每个点的次数，那么分别从两条边离开的次数只和它的初始颜色，最后颜色，是不是1,v有关，并且它是满秩的，可以高消消出来。
但是问题是解出来的东西可能和初始状态不在一个环上。
结论比较震撼。
D11
A. tree
树，点有点权w，选一个集合S，最小化
∑i,j[i∈S,j∈S,i∈anc(j)]B.
xxii open cup gp of imo I. Intellectual Implementation
数论。
wc2020 猜数游戏
因为每个数都要问一次，相当于每个
求一个原根，那么如果a=gk，就可以标记所有gt满足gcd(φ(p),k)∣t。那么f就是gcd(φ(p),k)在整除意义下的极小元个数。
于是枚举一个数，看看它何时是极小元。那么也就是比它小的都不能选。复杂度O(n2)。
gcd(φ(p),k)当然是φ(p)的因数，所以我们只需要在所有因数上跑一个每个点可以到达的点计数。做狄利克雷前缀和即可。
wc2021 斐波那契
补充到 fib数列 了。可能会remake这一篇。
D12
A. colour
序列，奇数位可以填1,3，偶数位可以填2,4，给m个区间，要求每个区间颜色数不能是4，求方案数。n,m≤106。
扔掉被包含的区间。
爆力dp就是设dp(i,j,k)表示现在在i，如果i是奇数，j−1是上一个和i不同的，k−1是上一个和i−1不同的，否则反过来。也就是说j是只看奇数位的上一次变化的位置，k是只看偶数位的。
转移的时候，奇数位是dp(i,…,k)→dp(i+1,i,k)，偶数位是dp(i,j,…)→dp(i+1,j,i)。给每个区间左端点+2，那么扫到一个右端点r的时候，我们要把j,k≥l的所有状态推成0。这看起来有点像sdoi2019 染色，所以我们考虑行的和和列的和，但是这里推成0的时候会有问题。
注意到被推成0的状态对后面完全没有影响，所以不如一开始就不加入它们，也就是说现在i右边第一个r对应l，那么对≥l的行和列我们都不更新。由于l是递增的，可以做到O(n)。
B. rps
模拟。
C. fenwick
一个函数序列，每个位置是f(x)=xxora或f(x)=x−\operatoranmelowbit(x)，这里如果x=0则\operatoranmelowbit(x)=0。每次给一个区间和x，求从左往右代入得到的结果，强制在线。n≤106。
感觉比较厉害。问题在于−lowbit咋做，考虑设f(i,k,j)表示现在在i，低k位是j，低k位变成0
杂题选讲。
cf1514 E.
先用操作2归并求一条哈密顿链，然后沿着哈密顿链向前问。
cf1535 F.
显然f只可能是0,1,2,1337。
考虑0。hash。1337可以集合hash。
考虑1。根号分治。如果串个数不超过根号，直接做。如果串个数超过根号，那么长度不超过根号，枚举哪个区间排序了，hash即可。
考虑怎么poly log。枚举一个串，枚举一个极长上升段，如果两个串之间f是1，必然可以另一个串在这一段排序，并且由于操作方案唯一，这个极长上升段也是唯一的。正反建trie，那么前缀和这个极长上升段前面相等的，后缀和后面相等的就是两个子树的笛卡尔积。数点即可。
cf1508 D.
对于每个环，我们可以留一条边不连。这个显然比较无解啊!考虑一个大环，环上每条边都和另一个二元环相交。
考虑我们选一个点，跟所有点连一条线段，那么每个环上只有一个位置不能换对，也就是说最后每个环上有一个元素会走到下一个环上。
考虑如果只有一个环，我们就赢了。所以极角排序，如果有超过一个环，必然存在两个点满足它们在极角序上相邻且属于不同的环，所以只需要把它俩换一下就可以合并这两个环。
cf1603 D.
注意到k超过log答案必然是n。
dp，设dp(i,j)表示0,…,i分j段的答案。注意到c满足四边形不等式，于是决策单调性分治，使用决策单调性分治指针移动的trick，需要莫反一下算c，复杂度O(nlog3n)，因为每个数贡献不超过log次，而因数个数和是O(nlogn)，k还有一个log。
arc153 E.
考虑怎么算f。我们必然把所有1插到左边，于是找到第一个1，在它左边，我们必然把所有2插入到左边，这样的。也就是说我们倒着每次找到最小的字符，然后正着把剩下的塞进去。那么y必然形如111…1222…2333…3444…4…999…9???…???，其中?就比较随意了。每个?中的数可以插进一个前缀，乘起来即可。我其实是没太懂啊?
洛谷9150.
我们走到点i，能且只能尝试通过已经走过的点走到ki。考虑一个置换环，显然一个环不可能走出去，把环复制一倍，那么如果i能到ki，ki的连通性i可以保留。那么看看ki在链上最远走到哪，比如是x，如果x能到i，i能到kx，那就把kx加入。
考虑我们定义链上一段是强的，当且仅当从第一个点进入，可以
Related Issues not found
Please contact @ShanLunjiaJian @pbrinotwyh @vectorwyx @fireinicecode to initialize the comment