Day 1
挂分仙人。
T1
比较简单，找到所有区间，算每个颜色不被多少区间包含。因为贡献区间长度固定，所以可以转成对 $l$ 的限制，前缀和一下做完了。
T2
建出 trie 树，根据右儿子的奇偶性判断：
如果为奇数，则右儿子至少有一个不匹配，然后可以找一个不匹配，剩下的两两匹配这一位就都是 $0$，一定不劣。有两种方案，第一种是选一个单独成集合，第二种是选一个和左子树异或起来，两种取 $\min$。
如果为偶数，则向左右分别递归，答案取 $\max$。
T3
首先考虑如果只有一种操作，确定了第一行之后后面的操作都是确定的。然后有两种操作的话，可以 $2^n$ 枚举每一列能用那种操作，然后再枚举第一行那些位置进行了操作，总枚举量是 $3^n$ 的。每一行哪些位置需要操作可以用位运算简单优化一下，总复杂度 $\mathcal O(3^mn)$。
T4
显然只会从根连向其他点。考虑如何对一个点求答案。先二分答案 $k$，然后可以不断找到深度最大的没有被删的点，然后把根和他的 $k-1$ 级祖先连边，这样就把 $k-1$ 级祖先的子树全部删掉，不断重复这个过程做 $k$ 次就得到了答案。单词复杂度 $\mathcal O(k\log^2n)$。
对于多个点，性质是相邻点的答案不超过 $1$，所以可以不用二分了。换根处理，找深度最大的点有一些细节，在向下递归的时候对 $dep$ 做一个 $dfn$ 序上的区间加即可。chk 的复杂度是 $ \mathcal O(k\log n)$，第一个点暴力做，剩下的点只会 chk $\mathcal O(1)$ 次，这样总复杂度就是 $\mathcal O(nk\log n+n\log n)$。
Day 2
map 当数组使。
T1
枚举中间的点，然后考虑左边和右边的点的前若干位一定相同，然后第一位不同的话，假设 $j$ 这一位是 $1$，则要求 $i$ 是 $0$ 并且 $k$ 是 $1$，反之亦然。然后可以把 trie 树建出来，每次加入左边的一个点，删去右边的一个点，像线段树一样维护每一层每个节点的左儿子“左边出现次数”乘右儿子“右边出现次数”和反过来两个信息，统计答案就枚举第一个不同的位置即可，总复杂度 $\mathcal O(n\log V)$。
T2
先统计序列已经填好的位置之间的逆序对，然后可以设 $f_{i,j}$ 表示前 $i$ 个空位出现了 $j$ 个逆序对的方案数，这样 $j$ 的状态数是 $\mathcal O(nk)$ 的，总复杂度 $\mathcal O(nk2^k)$，但是没有前途，因为 $n$ 非常的大。
看起来这像是在做一个背包的过程，背包值域非常大的时候可以折半搜索：枚举前 $\frac k 2$ 个位置的值域集合，这部分枚举量是 $\binom{14}{7}$ 的，然后可以算出左右之间的逆序对数量，然后左右各花 $7!$ 的代价爆搜出所有情况下可能的逆序对数（需要一些预处理），然后把两部分拼起来查询即可。总复杂度 $\mathcal O(n+\binom{k}{k/2}(k/2)!)$。
T3
一眼看上去非常的不可做，如果考虑高斯消元就死透了。
考虑树上随机游走是怎么做的：设 $f_{i}$ 表示点 $i$ 的答案，可以吧 $f_i$ 表示成 $a_i+b_if_{fa_i}$，然后进行代入消元。扩展到这个题上，可以考虑保留 $f_i=\sum_{j}c_{i,j}f_j+c_{i,0}$，其中 $j$ 是 $i$ 的所有祖先。这样把所有儿子合并起来即 $f_{i}=\frac 1 {deg_i-1}\sum_{j\in\mathrm{son}(i)}f_j+1$，这里相加是对应的 $c$ 的位置合并。然后查询 $c_{i,i}$ 的系数，吧 $c_{?,i}$ 这一项消掉，整体乘一个 $1-\frac{c_{i,i}}{deg_i-1}$ 的系数。这样传到 $1$ 号点的时候，只有 $c_{1,0}$ 有值并且其为最终答案。
上述过程暴力做是 $\mathcal O(nm)$ 的，可以线段树合并优化，或者 set 维护启发式合并做到 $\mathcal O(m\log n)$。
T4
不会。
Day 3
赢！
T1
从后向前扫，维护后缀的单调栈，在上面二分找到能用的即可，复杂度 $\mathcal O(n\log n)$。
T2
我好唐啊。
考虑拿一个堆维护当前所有可用的选择。把 $a$ 从大到小排序，初始把 $[1,i],i\in[L,R]$ 加进堆，假设选了的点是 $1$，没选的点是 $0$，如果 $1$ 的右边是 $0$ 就可以把 $1$ 向右移动一位。
可以主席树维护这个过程：选择最小的能移动的 $1$ 向右移动，或者是撤销上一次移动，把上一次移动的 $1$ 变成 $2$（意为以后不能移动这个位置）然后继续移动最小值，复杂度 $\mathcal O(n\log n)$，但是空间也是 $\mathcal O(n\log n)$ 的。
简单做法：其实不必每次严格的加入最小值。可以每一个 $1$ 移动到目标位置后再移下一个 $1$。可以用堆存三元组 $[l,r,x]$ 表示当前 $[1,l]$ 的 $1$ 没有移动，第 $l+1$ 个 $1$ 在 $x$ 的位置，第 $l+1$ 个 $1$ 最多移动到 $r$。可以变成 $[l,r,x+1]$ 或者 $[l-1,l,x-1]$。复杂度也是一个 $\log$。
T3
我好唐啊。
首先考虑如果选择了集合 $S$，则一定是交换 $S$ 中最大的 $k$ 个的代价和 $S$ 外面的最小的 $k$ 个的代价。
按照代价从大到小排序，如果选了$k$ 个交换，则一定是一段后缀 $[i,n]$，全部支付代价，然后从 $[i,n]$ 中选择 $k$ 个不记收益，这个可以简单处理。
对于 $[1,i-1]$ 的部分，一定是先钦定一个前缀 $[1,j]$ 中选收益前 $k$ 大的（不记代价），然后 $[j+1,i-1]$ 的部分正常做背包。注意到 $[1,j]$ 和 $[j+1,i-1]$ 的部分可以拼到一起（背包 $f_{i,0}$ 的初值设成 $[1,i]$ 中收益前 $k$ 大之和），这样复杂度是 $\mathcal O(n^2+nV)$ 的。
对于没用完 $k$ 次机会，则 $[j+1,i-1]$ 内部一定没有选任何东西（因为如果选了就能用上这次交换），所以也可以比较暴力的做：枚举 $i$，枚举用了几次，从 $[i,n]$ 里选收益最小的 $k$ 个删掉，然后 $[1,i-1]$ 里选收益最大的 $k$ 个加进来，复杂度是 $\mathcal O(n^2)$。
T4
首先考虑有一个二维平面，如果 $a_i=b_j$ 则 $(i,j)$ 是黑的，要求选一个权值最大的全白矩形，其中权值是横轴上的和和纵轴上的和之和。
考虑进行中点分治，从上到下扫描线矩形下边界，则对于矩形上边界的选择就是 $mid$ 左右两侧的单调栈，可以用线段树加单调栈维护每个上边界的权值，总复杂度 $\mathcal O(n\log^2 n)$。
发现中点分治是不必要的：先求出来序列 $A,B$ 中和较大的那个和，记为 $S$，则最终答案一定在某个序列上的权值 $>S$，所以在两个序列上找到一个分界点，则最优解一定跨过其中一个，这样扫描线只用做两次，复杂度变为 $\mathcal O(n\log n)$。
Day 4
最唐的一集。
T1
不会。
T2
最大值显然是把笛卡尔树建出来搞一搞。最小值可以从前向后考虑。考虑操作区间的右端点可以是 $r$ 的充要条件，感觉就是 $r=n$ 或者 $a_r>a_{r+1}$，这样才能保证操作数最小，线段树什么维护一下随便做做。
T3
直接做。发现会算重。容斥。构式。做完了。
T4
建出圆方树，树形 DP，换根 DP，做完了。
Day 5
T1
保留直径两端点到所有点的连边是对的。
T2
数据范围很像是小常数 $\mathcal O(n\log^2 n)$。考虑分治，把序列划分成若干个 $01$ 连续段，让 $0$ 全移到左边，$1$ 全移到右边。容易发现一次操作可以让连续段个数减半，分治到两侧。然后两侧向上合并的时候可能需要补空操作，很不好写。
T3
不会。猜测抽到了 $a_i$ 之后扔掉，之后再抽到 $<a_i$ 的也会扔掉，这样就有 $\mathcal O(n^2q)$ 的 DP 了。
T4
边权非常小，转成计算联通性。
Day 6
T1
可以直接树形 DP。
T2
建出来笛卡尔树，二分答案求出第 $L,R$ 小的权值，然后直接求出来权值在这个区间内的所有的就行了。注意一下边界问题。
T3
哎。
考虑容斥，钦定若干个位置等于 $b_i$ 或者 $c_i$。首先考虑连边 $b_i,c_i$，然后选若干条边，组合意义是选若干个位置出来可以等于 $b_i$ 或者 $c_i$。这样选一个树的系数就是树大小，基环树的系数是 $2$，但是不太好做。
一个很牛的思路是不只钦定位置，还钦定他等于 $b_i$ 还是 $c_i$。连边 $(i+n,b_i)$ 和 $(i+n,c_i)$，这样图是若干个环因为每个点度数都是 $2$。这样问题就变成了选若干个端点不交的边。可以简单 $\mathcal O(n^2)$ 求出，也可以 FFT 做到 $\mathcal O(n\log^2 n)$。
T4
感觉很唐。
假设 $1$ 能打败 $2$，$2$ 能打败 $3$，$3$ 能打败 $1$。只考虑序列中 $1$ 的位置能不能成为最终赢家，这样做三次就是原问题。
考虑 $1$ 的左边和右边最后是剩下了若干个 $2$。左右是一样的，只考虑左边的一段：过程一定是 $3$ 先把其余的 $1$ 干掉，然后 $2$ 把 $3$ 全干掉。
容易发现第二步中只需要有一个 $2$。这样问题就是能否完成第一步的前提下保留至少一个 $2$。
核心性质是第一步中 $3$ 不会被干掉因为一定不优。这样用 $3$ 把序列分成若干段，如果中间的段有 $2$ 或者是开头和结尾的第一个是 $2$ 则合法，否则不合法。总复杂度 $\mathcal O(n)$。
Day 7
T1
THUSC D1T2。从高位到低位考虑，状压记录每一个数是 $<a_i$ 还是 $=a_i$。
T2
考虑合并树的结构，叶子节点权值是序列权值，非叶子节点权值是 $K$，这样一个点如果距离根距离是偶数则贡献是 $+1$ 否则是 $-1$。
枚举贡献是 $+1$ 的非叶子节点个数 $i$，则 $-1$ 的个数就是 $n-1-i$。$-1$ 的序列权值个数就是 $2i-(n-1-i)$，$+1$ 的序列权值个数是 $2(n-1-i)-(i-1)$（因为根节点不能作为儿子）。
这样把序列排序一下，求一下前缀和，建出来凸包就行了。
T3
首先删一条链可以改变两端的奇偶性。然后如果删两条链，同时覆盖了一个边那这个边就可以不删，所以只需要保留一个树就行了。
因为字典序要最大所以保留最大生成树。然后随便做做（？）。
T4
挺牛的啊感觉。
考虑进行一个号的标，让 $i$ 子树内距离 $i$ 等于 $k(k<10)$ 的点编号连续，并且对于距离 $i$ 大于等于 $10$ 的点标号也连续。可以 DFS 过程中 BFS 距离 $x$ 小于 $10$ 的所有点，给没标号的标上号。
这样操作 $13$ 都能 $\mathcal O(k\log n)$ 做了。对于操作 $2$，一个很牛的东西是在点 $x$ 操作距离他为 $k,k-1$ 的点，然后 $x\leftarrow fa(x),k\leftarrow k-1$，继续做直到 $k=0$，这样就能不重不漏覆盖所有点，注意特判 $x$ 走到了根之后的情况！！！
Day 8
有点烦。
T1
值域非常的大，考虑一个操作的贡献，可以发现 $3$ 操作的贡献次数是后面 $1$ 操作的操作次数，$2$ 操作的贡献次数和后面 $1$ 操作的所有出现位置之和有关，从后向前 DP，状态是有几次操作 $1$ 和操作下标之和，值存在 DP 值里，总复杂度 $\mathcal O(Tn^4)$，但是大概有 $\frac 1 {12}$ 的常数。
T2
考虑根号分治，对于小块对小块可以暴力树状数组，大块对大块和大块对小块都可以预处理大块的前缀和，然后扫一遍做，总复杂度 $\mathcal O(n\sqrt{n\log n})$。
T3
感觉这题很弱智。
因为操作次数是 $\mathcal O(n)$ 的，所以不要瞎想分治，考虑每次把一种球做好并留一个空位。容易发现只要一个球在上面就可以在 $6$ 步之内做到。
T4
感觉这题也很弱智。
| 考虑容斥，有 $\frac{n(n-1)}2$ 种限制。先爆搜出相对大小，然后求出 $f_S$ 表示违反了 $S$ 子集中为 $1$ 的位的限制的方案数。然后求出 $g_S$ 表示至少违反 $S$ 子集种为 $1$ 的位的限制的方案数，然后答案就是 $\sum_T(-1)^{ | T | }g_T$。这样能过 $n=5$，有 $70$ 分。 |
限制看成图，发现 $n=6$ 的本质不同无标号无向图只有 $152$ 个，所以直接压缩一下打表就做完了。
Day 9
寄了。
T1
最后剩下的值是确定的，求出序列 & 之后从前向后贪心就行了。
T2
这也能挂。。。
观察一下，如果存在一个子矩阵的四个角分别是 RBRB 那一定寄了。很典的扩展一下：如果是 B 则行向列连边，否则列向行连边，检查是否有环即可。
构造最小操作次数：因为全涂了，首先假定每行都操作过（每列同理），那考虑行染色染的形态是那一列，则和这一列相同的列的代价是 $0$，否则是 $1$，哈希找出相同的列的最大值即可。
T3
首先预处理 $pos_i$ 表示 $i$ 的另一次出现位置，设 $f_i$ 表示 $S1$ 当前选的最后一个点是 $i$，$S2$ 选的最后一个是 $pos_i$，转移树状数组优化，总复杂度 $\mathcal O(n\log n)$。
T4
非常深刻。
首先考虑一个 dfn 区间是若干个子树还有一个不满的子树，所以 $k=1$ 是简单的，当然可以数边但是不太好扩展到 $k>1$，可以预处理 $nex_i$ 表示 $siz_i+dfn_i$ 是哪个点，然后倍增一下。
对于 $k>1$，首先两个段 $[l_1,r_1],[l_2,r_2],r_1<l_2$ 之间的交点一定是 $[l_2,r_2]$ 的若干个根和前面的交点。所以考虑按照 dfn 序从小到大扫，用一个栈维护当前根链上的所有区间。因为根链的 dfn 序是递增的，所以可以只存在这个根链上的 dfn 大区间，不用找出具体的位置，然后一个区间如果完全不在根链上了就把他删掉。
每次移动到下一个区间的左端点的时候，就查询该区间内所有子树根和栈内节点的交，查询方式还是倍增。如果跳过了一整个栈内节点那就直接把这个节点从栈里面删掉。然后查询完了就把该区间再扔进栈里面。总复杂度 $\mathcal O((n+k)\log n)$。
Day 10
T1
直接模拟，拿一个 vector 存当前还活着的所有小精灵即可，每次暴力移动并删掉没用的小精灵，总复杂度均摊 $\mathcal O(nm+q)$。
T2
首先考虑原序列的和是 $\sum_i opt_id_i+na_n$，所以要求 $\sum_i opt_i d_i\equiv S\pmod n$。
然后还有非负的限制，考虑把 $d$ 从小到大排序，这样枚举一个 $i$，钦定 $[i,n-1]$ 的后缀全都是正的。这样前面需要满足同余的限制下，让和最小，因为这时候 $opt=-1$ 的上界已经确定，要做的就是最大化 $a_n$ 来让 $a_n$ 大于这个上界。预处理 $f_{i,j}$ 表示前 $i$ 个数，选取方式的和在 $\bmod n$ 意义下同余 $i$ 的和的最小值即可，总复杂度 $\mathcal O(n^2)$。
T3
暴力 DP 是设 $f_{i,j}$ 表示第一个学校录取前 $i$ 人，第二个录取前 $j$ 人的方案数，初值 $f_{X,Y}=1$，然后如果 $i+j-in(i,j)=X+Y$ 就把累加到答案里，否则转移向 $f_{i+1,j}$ 和 $f_{i,j+1}$。
然后打表（？）发现终止点随着 $i$ 增加 $j$ 是递减的，所以可以想办法找出来终止点直接用组合数计算路径数。
T4
很牛感觉。
首先 Floyd 预处理最短路 $d_{i,j}$。然后考虑新加了一个边 $(a,b)$，从 $i$ 走到 $j$ 的最短路变成了 $\min\{d_{i,j},d_{i,a}+d_{j,b}+1,d_{i,b}+d_{j,a}+1\}$。
然后核心性质是新加的两种方式不可能都比 $d_{i,j}$ 更优。因为假设： \(d_{i,a}+d_{j,b}+1<d_{i,j}\\ d_{i,b}+d_{j,a}+1<d_{i,j}\) 则有 \(d_{i,a}+d_{i,b}+d_{j,b}+d_{j,a}+2<2d_{i,j}\\\) 但是应当有 \(d_{i,j}<d_{i,a}+d_{j,a}\\ d_{i,j}<d_{i,b}+d_{j,b}\) 所以原假设不成立。这样就可以直接做了。
Day 11
T1
一个点上只会有最小边和其他边连边，然后暴力跑 Kruskal 即可。
T2
首先看成有连边，则一定只有一个环。感性理解就是环的限制比较严，树的限制不严。因为只要有了一个环，则后面的点都可以挂在环的某一个点上形成树，这样一个边权对应一个点权。现在就在想办法构造一个环。
首先考虑奇环，可以发现，当且仅当序列中有偶数的时候会连自环。这部分比较简单。
| 如果序列中全是奇数，那只能尝试连偶环，列列式子可以发现限制的是取两个集合 $S,T$，满足 $ | S | = | T | $ 并且 $S$ 中元素和等于 $T$ 中元素和。 |
值域非常大，$n$ 很小，考虑折半搜索，分成两个 $n=15$ 的部分，$3^{15}$ 枚举 $S,T$ 集合，然后拿手写哈希维护一下左边，右边做的时候直接查就行了，复杂度 $\mathcal O(\sqrt 3^{n})$。
T3
唐完了。
首先这玩意是凸的，然后就一去不复返了。。分治合并凸包可以做到 $2^23^2n\log n$，显然过不去。
然后考虑如果没有两个极差，那一定是选 $c$ 最大的。如果有了极差最多会选四个 $c$ 比较小的，随便预处理一下就行了。
T4
首先只会出现原序列的数。设 $f_{i,j}$ 表示 $[1,i]$ 的前缀最大值是 $j$ 时的最大收益。转移： \(f_{i,j}= \begin{cases} f_{i-1,j}\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad j>a_i\\ \max_{k\leq j}f_{i-1,k}+num(a_i)-num(j)+b_i\quad\; j\leq a_i \end{cases}\) 对 $f$ 整体取一个前缀最大值： \(f_{i,j}= \begin{cases} f_{i-1,j}\;\;\qquad\qquad\qquad\qquad\qquad\qquad j>a_i\\ f_{i-1,j}+num(a_i)-num(j)+b_i\quad j\leq a_i \end{cases}\) 然后这样就只需要在完成一个滚前缀最大值的操作，总复杂度 $\mathcal O(n^2)$。
考虑线段树维护这个东西，是前缀 $a_i\overset +\leftarrow b_i$ 和 $a_i\overset +\leftarrow C$，这两个都可以打 $tag$。
然后还有滚前缀最大值，容易发现前缀经过操作后还是递增的，所以可以线段树上二分找出被更新的后缀再做一个区间覆盖即可，总复杂度 $\mathcal O(n\log n)$。
Day 12
T1
首先 $a+b$ 是不变的，所以可以只记录一个量 $a$。设 $C=A+B$，则一次变换后 $a$ 可以变成 $2a$ 或者 $2a-C$。观察到经过 $k$ 次操作后，$a$ 可以变成 $2^ka+xC$，其中 $x\in[0,2^k-1]$。所以答案不会超过 $\log V$，暴力枚举答案，判断需要的 $x$ 在不在区间里即可。
T2
需要知道当前有哪些下标和 $1$ 的 LCP 顶到了 $i$，这个就是 border，跑一边 KMP，维护一下所有 border 的和就行了。
T3
考虑什么时候赢了：一定是分成两个集合 $S,T$，其交集为空并且并集为全集。$S$ 中的通过抽卡把碎片抽满了并且剩下了一些，$T$ 中的没有抽满，然后直接 DP，设 $f_{i,j,k}$ 表示考虑了前 $i$ 种数，一共抽了 $j$ 个碎片，能合成的碎片数减去还需要的碎片数为 $k$ 的方案数，总复杂度 $\mathcal O(nV^3)$。
T4
首先把整个矩形拆成若干个横竖长条，然后可以线段树优化建图来进行连边，跑 $01$ bfs 就能确定每个长条的答案。对于最终答案，是跨过他的两个长条的 $\min$。但是两个长条答案的差一定为 $1$，因为首先他们两个的差 $\leq 1$ 因为可以通过一个长条在这个位置走到另一个。然后因为他们横竖不同，所以答案的奇偶性不同。所以最终答案也是好算的。总复杂度 $\mathcal O(n\log n)$。
Day 13
T1
按照频率排序之后直接做背包就行了。
T2
考虑给定了 $S$ 串怎么做，一定是贪心的往后不断地拼最长的匹配子串。所以如果钦定 $S$ 添加了一段串，则该串在 $T$ 中所有出现位置后面都不能接 $S$ 的下一个字符。
设 $f_{i,j}$ 表示选的串开头字符是 $i$，下一个串的开头字符可以是 $j$ 的最短串，即最小长度的等价类后面不能拼接 $j$ 的长度。这个可以枚举 $i,j$ 遍历一遍 SAM 求。出然后矩阵快速幂一下，做倍增即可，总复杂度 $\mathcal O(T^2n+T^3\log n)$，其中 $T=4$。
T3
我是彩笔。
假设 $1$ 先出现 $n$ 次，算出来最后吧答案 $\times 2$ 即可。考虑枚举 $1$ 出现的最后一次位置。
\[\begin{aligned} ans&=\sum_i\sum_{j=a_i+1}^{a_{i+1}-1}2^{-j}\binom{j-1-i}{n-1}+\\ &\sum_{j>a_k}2^{-j}\binom{j-1-k}{n-1}+\\ &\sum_{j>a_k}2^{-j}\binom{j-1-k}{n-1-k}+\\ &2^{a_k}\binom{a_k-k}{n-k} \end{aligned}\]第一、二行都是好算的，因为下指标是定值，所以可以预处理直接查询。对于第三行，设 $F_k(l,r)$ 表示 $\displaystyle \sum_{l\leq i\leq r}2^{-i}\binom{i-1-k}{n-1-k}$：
\[\begin{aligned} F_k(l,r)&=\sum_{l\leq i\leq r}2^{-i}\binom{i-1-k}{n-1-k}\\ &=\sum_{l\leq i\leq r}2^{-i}\binom{i-2-k}{n-1-k}+\sum_{l\leq i\leq r}2^{-i}\binom{i-2-k}{n-2-k}\\ &=\frac 1 2\sum_{l-1\leq i\leq r-1}2^{-i}\binom{i-1-k}{n-1-k}+\sum_{l\leq i\leq r}2^{-i}\binom{i-1-(k+1)}{n-1-(k+1)}\\ &=\frac 1 2F_k(l-1,r-1)+F_{k+1}(l,r)\\ F_{k+1}(l,r)&=F_k(l,r)-\frac 1 2 F_k(l-1,r-1) \end{aligned}\]$\mathcal O(\sum k)$ 的复杂度递推即可。
T4
逆天。再见。
Day 14
T1
从小往大填，暴力拿 map 记录当前左右的最靠外和次靠外的两个是什么，状态数可以简单的分析到 $\mathcal O(n^3)$。
T2
懒得喷，调了两个点。
直接区间 DP 就行了。
T3
傻逼读错题了。
时光倒流，维护一下右，下的颜色，线段树维护状态和答案增加量即可。
T4
17k 的含金量。
设 $c_{i,j}$ 表示答案，$a_{i,j}$ 表示输入数据。
首先可以确定 $c_{3,3}=a_{2,2}-a_{2,1}-a_{1,2}+a_{1,1}$，
用二维差分可以知道 $c_{i,j},c_{i-3,j},c_{i,j-3},c_{i-3,j-3}$ 的关系，这样就能推出来 $c_{a,b}$，其中 $a,b\equiv 0\pmod 3$。
这样利用了左上角的东西，然后右上右下左下也是一样的，所以可以确定出来 $i\equiv 0/n-2\pmod 3$，$j\equiv 0/m-2\pmod 3$ 的所有格子 $c_{i,j}$。
然后如果 $n-2,m-2$ 都不是 $3$ 的倍数，这样就知道了整个矩阵：
黑色格子是上面知道的。知道了所有黑色格子之后深灰色的格子也是可以求出来的（依靠同一条边边上两个相邻 $a$ 的差分可以知道相邻两个格子的和，如 C2 和 C1 的和就是 $a_{1,2}-a_{1,1}$，然后 C1 因为已经知道了，所以也能知道 C2）。最后在填浅灰色的格子，没填的直接给他填上就行了。
对于 $n-2$ 不是 $3$ 的倍数但是 $m-2$ 是的情况，首先画出来能直接确定的格子：
还是用二维差分，观察能确定那些格子：
容易发现这样信息已经“满了”，即不可能再确定任何一个格子。但是这样可以用一维差分知道相邻两个数的和，也能知道跨过一条黑线的相邻两个数的和（如 $c_{3,1}+c_{3,2}+c_{3,3}=a_{2,2}-a_{1,2}$，然后 $c_{3,3}$ 已经确定，这样就能知道 $c_{3,1}+c_{3,2}$。然后 $c_{6,1}+c_{6,2}+c_{6,3}-c_{3,1}-c_{3,2}-c_{3,3}=a_{5,2}-a_{4,2}$，$c_{3}$ 的和也知道了，所以就能知道 $c_{6,1}$ 和 $c_{6,2}$ 的和……依此类推）。
然后显然只保留相邻两个数的和的限制就能满足原限制。所以如果和是 $0$ 或者 $2$ 就直接填，这样图上会剩若干条链，链上满足相邻的都是 $01,10$ 即可。
对于 $n-2,m-3\equiv 0\pmod 3$：
你发现他十分的菜，只能确定一些单点的确切值。但是相邻两个浅灰色格子的和以及跨过一个黑色格子的两个相邻浅灰色格子的和都是知道的，所以可以用第二种情况确定出灰色格子的和的。
实际上是这样。然后你发现你只能知道相邻四个的一个田字格的数的和了，忽然发现这个是经典问题矩阵游戏的弱化版，直接粘个 spfa 上来就过了。
){kind=link}
但是实际上因为值是 $01$，所以可以枚举左上角填什么，把第一行和第一列剩下的未知量设成主元，然后你发现！！！！！他很厉害，每个格子只有两个未知量，就可以愉快的 2-sat 了。但是实际上 spfa 就跑的非常快。
Day 15
T1
二分，染色，随便做，但是我咋写了这么久。
T2
考虑直接贪心：离散化，一个区间在某地出现，某地消失。从前向后做，遇到一个颜色把他加入第一个集合。
如果当前位置的颜色不是满的，就从第一个集合里面拿出来一些放到第二个集合里直到第二个集合包含所有颜色。一个区间消失的时候需要判一下删掉某个集合中的元素。
T3
组合意义：选择三个相同的子序列。设 $f_{i,j,k}$ 表示第一个子序列在 $i$ 结尾，第二个在 $j$，第三个在 $k$。转移是枚举 $x<i,y<j,z<k,M_{a_x,a_i}=1$。
原来我根本不会前缀和。
设 $s_{i,j,k}$ 表示 $\sum_{x<i,y<j,z<k,M_{a_x,a_i}=1}$。注意 $s$ 和 $f$ 都只在 $a_i=a_j=a_k$ 的地方有值。
更新了一个 $f_{i,j,k}$ 之后，把它自己做一个二维前缀和，并在 $M_{a_i,a_x}=1$ 的地方更新前缀和数组即可，转移的时候就能直接查询 $s_{i,j,k}+1$ 作为 $f_{i,j,k}$。
没见过这种东西啊，感觉自己唐完了。就是对它有贡献的数是确定的，所以并不需要开 $n$ 个前缀和数组。
T4
暴力是 $\mathcal O(n^3)$。考虑第一个的前缀最大值还有第二个的前缀最小值，枚举他们的交点，发现交点前面的贡献就是 $a_i>v$ 的前缀最小值个数还有 $a_i<v$ 的前缀最大值个数，后面的贡献是 LIS 加 LDS 长度。这两个东西随着 $i$ 的变化，变化量都可以用区间 $+$ 来表示。拿线段树，支持区间加，全局最大值即可。
Day 16
T1
二分答案，设 $f_{i,j}$ 表示 $i$ 子树内用了 $j$ 条一类边，在保证直径小于 $mid$ 时的最短根链，合并的时候讨论一下即可，复杂度是 $\mathcal O(nk\log V)$。
T2
建图，行向列连边。上界是最大匹配，下界是连通块个数。先求最大匹配然后每个连通块内保留至少一条边，再删边就行了。
构造方案可以找到每个点上下左右第一个点，钦定每个点只能消除他周围的。这样把选择保留的关键点拿出来跑 bfs 即可。
T3
感觉很唐氏。要求哈密顿路，设 $f_{S,i}$ 表示当前消了集合 $S$ 中的所有数，当前所有指针在数字 $i$ 的最小代价。转移的贡献可以狂暴预处理得到：假设从 $j$ 走到了 $k$，则贡献就是 $\sum_i s_k-s_j+[pos_k<pos_j]m$。因为前缀和相减在跨过一圈的时候会算错所以有了后面的。对于每种数预处理一下就行了，复杂度 $\mathcal O(2^mm^2+nm^2)$。
T4
唐氏。这个故事告诉我们分块不要先想着离线。
首先如果一个点是右儿子，则它父亲的左儿子一定在它之前遍历。然后一个点左右儿子对他自己的答案也是可以简单求的。
这样就只需要考虑祖先单点对后代的影响。考虑在编号维上分块，预处理 $f_{i,j}$ 表示 $i$ 块内，是 $j$ 祖先的点的个数。
定义一个块的状态是整的就是块内所有颜色相同，散的就是可能不同。对于一次操作，其影响到两个块会变成散块。对于散块，如果一个点是 $-1$，那左右子树答案都 $+1$，如果是 $0$ 则只有右子树 $+1$，拍到 dfn 序上，就是需要区间加。
对于操作完整覆盖的块，如果他原来是散块就要把贡献从数据结构里删掉，这部分复杂度均摊是对的，然后给他打上 tag 就行了。
对于一个查询，散块对他的贡献已经在数据结构里存好了，可以直接单点查询。整块可以直接扫一遍，通过 $f$ 来计算贡献。容易发现需要的数据结构修改 $\mathcal O(n\sqrt n)$ 次，查询 $\mathcal O(n)$ 次，可以简单分块做（维护单点和整块和，查询的时候扫一遍 $\mathcal O(\sqrt n)$ 个整块和 $\mathcal O(\sqrt n)$ 个散点）。这样总复杂度 $\mathcal O(n\sqrt n)$。
Day 17
T1
取最小生成树，相邻点黑白染色。
T2
把操作按照 LCA 的深度从大到小排序，每次如果一个操作路径上已经有删掉的点那就不管他，否则把 LCA 删了。需要单点 $+1$，路径查询和，可以转成子树 $+1$，单点查询，复杂度 $\mathcal O(n\log n)$。
首先可以桶排，然后删点的时候从 $x$ 开始 DFS，遇到已经删了的点就返回，这样把子树里的点全部标成 $1$，查询直接查就行了，复杂度 $\mathcal O(n)$。
T3
挺唐的，扫描线右端点，不断加入可用区间。
加入一个 $[l,r]$ 的可用区间可以看成是 $[1,l]$ 中，$\geq l-1$ 的数变成 $r$，可以吉司机线段树。
查询是单点查询，修改是单点修改，势能是对的，总复杂度 $\mathcal O(n\log n)$。
T4
考虑找到图中两个对称的点作为两个根，这样到两个根距离相等的就是叶子。把叶子删了之后判一下树同构。
首先判图中存在一度点，这样两个一度点一定都是根。
没有一度点的情况，考虑找到图中的一个环，它一定是被叶子劈成两半的。考虑把这个环删掉，这样如果环上有两个点仍然在一个连通块里面，则这两个点就可以作为根。
判是否是树可以简单判点边关系。
Day 18
T1
直接 bfs。
T2
直接贪心。
T3
$n$ 比较大的时候，找到 $siz$ 最小的集合把他作为起始点，然后做容斥就行了。
$n$ 比较小的时候，先做一遍加到答案里，然后把集合 $1,n$ merge 在一起，然后再做一遍减到答案里……这样是 $\mathcal O(nm)$ 的。
T4
傻逼。
等价于最大化每一个，定长分块，前后缀维护一下李超树即可，不用可持久化。
Day 19
牛逼了，少打一个点。
最近代码源比赛题面怎么都这么唐。
T1
只有可能全横放或者全竖着放，排一下序就行了。
T2
注意到答案只和差值有关。枚举时间，再枚举 $5!$ 排列，去重一下贡献到差值里面，查询 $\mathcal O(1)$。
T3
唐氏题。
设 $f_{i,j}$ 表示 $2^i$ 用 $j$ 个 $2$ 拼起来是否可行，打表发现（好像也可以有理有据的证明）当 $1800\leq j\leq 2^{i-1}$ 时全部合法，所以只需要 DP 1800 位。
再设 $g_{i,j}$ 表示考虑了 $V$ 的低 $i$ 位，用 $j$ 个是否可行。转移类似，只需要保留 $1800$ 位。
输出的时候有一定细节。。。。
T4
不太会。可能会。
少打一个点导致的。
核心性质：一个数只有一个 $\geq 10$ 的质因子，所以对于每一段分别处理，枚举 $2^4$ 的子集，表示这个数有 $\{2,3,5,7\}$ 中的哪些质因子（注意枚举了有哪些是强制剩下的全都没有的）。
这样对于一个限制，如果其和枚举的 $\{2,3,5,7\}$ 的子集有交，就不管它，否则把他的大质因子扔进限制里面。现在问题转化为，要求一个区间 $[l,r]$ 内，包含 $S$ 中质因子，并且不包含 $T$ 中质因子的数的个数，其中 $\lvert T\rvert\leq 4$，这里可以暴力容斥。总复杂度 $\mathcal O(3^4m^2)$，也可以做到 $\mathcal O(3^4 m)$ 啥的。