SDOI2021正睿一轮集训

Day 1

一、线段树

定理：任何一个区间在线段树上会划成 \(O(logn)\) 个区间

P4868

二、树状数组

考虑前驱，去掉所有右儿子

每个点维护 \([x-lowbit(x)+1,x]\) 的和

P4868另一种做法

POJ2155 二维树状数组(一维扩二维即可)

三、动态开点线段树

每次编号，每个节点多维护左儿子和右儿子编号

四、可持久化线段树

维护所有历史版本线段树，每次修改都建一个新点

CF323C

五、线段树合并

从根开始合并。可持久化就每次合并直接新开一个点即可。

一次合并复杂度是两棵线段树公共点个数。每次合并总结点个数会减去公共节点个数，复杂度会加上它，所以均摊复杂度O(logn)。

CF600E（可以DSU on TREE）

六、二维线段树（可用KDT）

第一维 \([l_1,r_1]\)，第二维 \([l_2,r_2]\)，维护矩形\((l_1,r_1,l_2,r_2)\)。

七、李超树

支持插入直线，求 \(x\) 处最大值

每个区间维护 \(mid\) 处取值最大的直线，考虑几种情况分类讨论，可以保证每一次都只会下放一条直线到最多一半区间。每个区间不一定是最值，最后单点查询的时候比较从根到其路径上 \(O(logn)\) 个直线的最优解。

加线段？李超树合并？CF932F

八、分块

两边暴力，中间整块的维护，每次 \(O(B+n/B)\)。

HDU6756，不太会

九、莫队

二维O(n^{(3/2))，三维O(n}(5/3))。

学会如何调整块大小！奇偶块排序只会优化大概1/2常数。

CF86D板子

十、带修莫队

加一个指针记录版本，三维莫队即可。

P1903板子

十一、树上莫队

欧拉序：DFS时进入和离开节点时记录节点编号形成的序列。

st_l到st_r上出现奇数次的点出现在路径上（无祖先关系就再加LCA）。

P4074 树上带修莫队板子

十二、平衡树

1.Splay

通过旋转使整棵树深度均摊O(logn)。

2.fhqtreap

treap=tree(bst)+heap，满足堆的性质。

fhqtreap通过分裂和合并维护。

需要修改或者查询的时候，就分裂开，然后单独搞，搞完之后再合并即可。每次分裂和合并都是期望O(logn)。

fhqtreap的可持久化就是修改新开一个点就行。可持久化之后就不能用修正值的堆性质了，需要用类似按秩合并的思想用概率合并。

十三、树链剖分

1.轻重链剖分

重儿子是子树大小最大的儿子。

十四、LCT(Link-Cut Tree)

平衡树使用Splay可以做到均摊O(logn)。维护一个重链的森林。

access(x) 把它到根的边都变为重边。

makeroot

findroot

split

link

cut

LCT还可以维护子树信息。

十五、ETT(Euler Tour Tree)

用平衡树维护每个点在欧拉序上的括号序列。比较好维护子树信息。

把边改掉相当于对一个子树在区间上平移。

十六、KDT

十七、综合练习题

HDU5118,CF1149C,CF482E,CF1192B,P4764

Day 2

构造题专场？？

T0热身题：

偶数无解，左边加起来n(n-1)，右边加起来n(n-1)/2，模n意义下不相等。

奇数直接取两个一样的从小到大排列即可。

T1三元环问题：

考虑上界，猜出一定有一个构造满足上界。用异或性质一一对应来构造出一组方案。

T2完全图边分组：

对于(x,y)，放在(x+y) mod (2n-1)这一组，然后对于每个k都取一个i，2k=i (mod (2n-1)。放在这一组。

T3完全图构造生成树：

归纳构造，考虑已经构造完2k的情况，考虑2k+1和2k+2的情况如何由2k的情况连几条边得到即可。

通过整除之类的性质先判断上界！

T4平面内三角形：

随机方向向量不与边重合，考虑先构造一组方案，然后用凸包消去多余的点，证明下界2n-2-凸包点数。

T5类魔方变换：

贪心，当前列需要k，那就从后面找个k花几步放回来。构造交换任意两个位置的方案即可。

T6序列大小位置相邻：

划分成n个段，每次选次小值最小的一个段，删去整个段，其他段删去比这个次小值小的数（最多一个），因此必然能选n次，必然有解。

T7向量和为零：不会

T8环上三个颜色：

找中间状态，先考虑如何从中间状态转移。

T9变换：考虑构造一组操作把最大值放在右下角。

T10给uv的较大或较小值：

2-SAT问题，主要就是根据真假关系拆点建边，然后找强连通分量即可。这个题维护一个上界下界，每个点选择赋上下界一定不会更劣，转化为2-SAT求解即可。

CF1375H 值域分块或值域分治

CF1364E

CF1365G

CF1290D

CF1292E

CF1288F

CF1097E

CF1227G

Day 5

Test 1

不能把剩余油量放到 \({dp}\) 方程里，所以需要考虑贪心和 \({dp}\) 转移，设两个 \({dp}\) 数组，\({dp_{i,j}}\)表示从i加满到j，\({dp_{2\ j}}\)表示到j油量为零，仅会有这两种情况。

考虑对于 \((i,j,k)\) 如何从dp_{i,j}和dp2_{j}转移到dp_{j,k}和dp2_{k}。分别考虑四种情况转移即可。

30pts：bitset优化LCS O(n^2/w)

dp(i,j)=max(dp(i-1,j,dp(i,j-1),dp(i-1,j-1)+(s[i]==t[j]));

考虑建成一个网格图，求(a,c)与(b,d)最长路。具体做法：网格图分治，取中间点，枚举怎么通过中间分界线。

70pts：好像是预处理T(n)=T(n/2)+O(n^{1.5)，总的O(n}1.5)=O(|s|^{3)，总的复杂度O(|s|}3+q|s|)。横竖接连着切保证边界上的点是根号级别。

Day 3

ICPC 题目选讲

2020 上海区域赛

L.Traveling in the grid world

Day 6

组合计数

热身题1

有 \(n\) 堆石子，已知每堆石子的数量都介于 \([1,2^m-1]\) 之间且互不相同。给定 \(n,m\)，每堆石子中的数量可以任选（但必须满足上述要求），求有多少种方案可以使得 nim 游戏下先手取胜。

算后手必胜（异或和为 \(0\)） 的情况。如果没有非 \(0\) 和不相同的限制，答案就是 \((2^m-1)^{n-1}\)，除最后一位以外都可以任选。非 \(0\) 的话，算 \(f_i\) 的时候减去 \(f(i-1)\) 即可。算相同的话，式子就是

\[f_i=\prod_{i=2^m-i+1}^{2^m-1}i-f_{i-1}-(2^m-1)(i-1)f_{i-2} \]

复杂度 \(O(n)\)。

热身题2

给出 \(n\) 个正整数 \(a_i\)，你要选出 \(n\) 个正整数 \(b_i\) 和 \(n\) 个正整数 \(d_i\)，对于每个 \(i\) 满足 \(b_i|a_i\) 且 \(d_i|b_i\)，求有多少种选法满足 \(\prod d_i^2\geq \prod b_i\)。\(n\leq 100,a_i\leq 10^9\)。

首先注意到，\(\prod d_i^2>\prod b_i\) 与 \(\prod d_i^2<\prod b_i\) 是一一对应的，所以现在只需要计算 \(\prod d_i^2=\prod b_i\) 的方案数。对每个质因子跑一边背包应该就行了。复杂度 \(O(\sum a_i+(n\log a_i)^2)\)。

CF838D

一轮省集出过的 nb 题！

考虑合链成环，新加一个 \(n+1\) 号点占位（不能被某个人占领）。那么每个点不被占领的概率就是 \(\frac{n+1}{n+1-m}\)，乘以 \(n+1\) 个位置的方案数 \(2^m(n+1)^m\) 即可。

CTSC2017 吉夫特

首先根据 Lucas 定理，选出来的子序列前面的数必须是后面的数的超集。然后这个东西可以直接枚举超集转移，复杂度 \(O(3^{\log(\max a_i)})\)。这个东西还可以进行一个非常 nb 的优化：类似分块，定义 \(f(u,v)\) 表示前 \(9\) 位为 \(u\)，后 \(9\) 位为 \(v\) 的超集的 dp 值之和。这样，计算当前位置的 dp 值的时候，只需要枚举当前 \(a_i\) 的前 \(9\) 位的超集，然后更新的时候只需要枚举后 \(9\) 位的超集。复杂度 \(O(2^9\cdot n)\)。

括号序列

求有多少个长度为 \(n\) 的括号序列满足其所有子序列中最长合法括号子序列的长度恰好为 \(2k\)，多组数据。\(T,n\leq 2\times 10^5\)。

令左括号为 \(+1\)，右括号为 \(-1\)。设前缀和数组为 \(s_i\)，那么最长合法括号子序列的长度为 \(n-s_n+2\min s_i\)。证明大概说的是，考虑一下最少需要拿走多少个括号。从开头开始，一旦当前左括号个数 \(<\) 右括号个数，那么接下来的一段右括号就都不行了。这时候直接把起点放到接下来一段右括号后面然后继续做。最后的时候，起点的高度已经变成 \(\min s_i\) 了，剩下 \(s_n-\min s_i\) 这么多左括号没办法找到匹配的右括号。把这些不能匹配的左右括号扔掉之后，剩下的就能形成合法括号序列了，这个长度是 \(n-s_n+2\min s_i\)。

接下来我们考虑枚举 \(t\)，那么 \(s_n=n+2t-2k\)，计算 \(\min s_i>t-1\) 和 \(\min s_i>t\) 的方案数相减得到 \(\min s_i=t\) 的方案数。计算 \(\min s_i>t-1\) 的话，相当于画一个长度为 \(n\)，高度从 \(0\) 到 \(s_n\) 的不经过 \(y=t-1\) 的折线。使用那什么翻折引理，可以得到这个方案数等于没有任何限制情况下到 \(s_n\) 方案数减去到 \(s_n\) 关于 \(y=t-1\) 对称的位置的方案数（这个证明我想的是构造一个双射，使得每一种不合法情况与后面这种的某种情况一一对应就行了）。

然后可以得到这个式子

\[\binom{n}{\frac{n-s_n}{2}}-\binom{n}{\frac{n-(2(t-1)-s_n)}{2}}=\binom{n}{k-t}-\binom{n}{n-k+1} \]

同理可以得到 \(\min s_i>t\) 的方案数为

\[\binom{n}{k-t}-\binom{n}{k} \]

然后一减，发现和 \(t\) 无关……考虑 \(t\) 的取值只需要满足 \(s_n\geq t\)，解得 \(-t\leq n-2k\)。又因为 \(-t\geq 0\)，所以 \(t\) 有 \(n-2k+1\) 种取值，也就是说，答案为

\[(n-2k+1)\big(\binom{n}{k}-\binom{n}{k-1}\big) \]

某道省选题

一棵树，每条边限制两个端点的大小关系（限制 \(a_u>a_v\) 或 \(a_u）。求有多少种符合要求的排列 \(a\) 满足整棵树的限制。\(n<=5000\)。

首先考虑一个简单的问题：树上所有边的方向都向下。这种情况就等于树上拓扑序计数，答案为 \(\frac{n!}{\prod siz_u}\)（证明大概说的是，考虑每个子树根都必须是子树内最大的，这个在全排列中的概率是 \(\frac{1}{siz}\)）。然后我们考虑一个暴力：对于所有反向的边，直接不予考虑，这样树上会形成若干个连通块，算出这个答案之后，对所有反向边进行一个容斥。接下来就要开始 nb 了：我们考虑一个 nb dp，设 \(f(i,j)\) 表示 \(i\) 为根的子树，当前与 \(i\) 连通的连通块大小为 \(j\) 的方案数。如果是一个正向边直接合并，如果是反向边，那么有两种合并方式（容斥，有一种要乘上 \(-1\) 的系数）。直接做这个树背包就行，复杂度 \(O(n^2)\)。

LOJ 575 不等关系

上边那个题放到序列上，但是 \(n\leq 10^5\)。考虑还是上边那个做法，但是你发现这个时候第二维显得没那么重要了，干脆只开一维，转移为

\[g_i=\sum_{j=0}^{i-1}\frac{[s_j='>']}{(i-j)!}g(j)(-1)^{cnt_{i-1}-cnt_j} \]

就是你枚举上一次的断点在哪里，这里设 < 为正向，那就是找你钦定的上一次的 > 且是断点的地方转移。这个式子看起来很像卷积形式，直接分治 NTT 即可做到 \(O(n\log^2 n)\)。

一些关于 Matrix-tree 定理的半懂不懂的话

Matrix-Tree 定理的本质是对环容斥。正常容斥系数应该是 (-1)^环个数。Matrix-Tree 定理删掉基尔霍夫矩阵中根所在的行列后，任意一个排列如果某一位选了它自己（即选在对角线上），那就说明从出边中随便选了一条；否则剩余的部分会形成若干个环，如果这些环形成的是奇排列则会有 -1 的系数。奇排列就相当于环的总长度减掉环个数是奇数，由于非对角线元素都取了相反数，因此 \((-1)\) 被乘的次数恰好是环的总长度，再乘上奇排列的系数，恰好就是 (-1)^环个数。因此 Matrix-Tree 定理不仅可以用于无向图，也很容易可以推广到任意有向图上。

某道题

给?张 \(n\) 个点 \(m\) 条有向带权边的有向图。这张图的?个树形图定义为：从 \(m\) 条边中选出 \(n-1\) 条边,使得所有点都可以通过这些边走到 \(n\) 号点。 ?个树形图的权值定义为这 \(n-1\) 条边的权值和。求出所有树形图的权值和，答案对 \(998244353\) 取模。\(n\leq 500\)。

一个经典的加转乘做法是，把每条边看作一个一次函数 \(wx+1\)，你发现这里的一次函数乘法（\(\bmod x^2\) 意义下）相当于在一次项系数上加！然后这题要注意，\(ax\) 不一定有逆元的（无常数项），如果遇到了一整列都没有，这种情况下要对一整行都除以 \(x\)，然后把答案乘以 \(x\)，当然都是 \(\bmod x^2\) 意义下的。

然后这个题如果没有考虑 \(ax\) 无逆元的情况，可以构造一个答案为 \(\bmod\) 的倍数的图。也就引发出了一道构造题：构造一个有向图，使得以 \(1\) 为根的生成树个数恰好为 \(k\)。\(k\leq 10^{18}\)。

首先把 \(k\) 表示成 \(2^p-2^{a1}-2^{a2}-\ldots\) 这样的，考虑先弄 \(p+1\) 个点，每个点 \(i\) 向 \(i-1\) 和 \(1\) 连边，这样生成树个数就是 \(2^p\)（因为是 DAG）。然后对于某个 \(ai\)，考虑把倒数 \(n-ai\) 位置的点到 \(1\) 的边改成到末尾 \(p+1\) 的边，这样就形成一个环了，用对环容斥的方式可以得到答案为 \(k\)。

某道集训题（正睿NOIP集训Test16-C）

\(y\) 轴正半轴上有 \(n\) 个点 \((0,a_1),\ldots,(0,a_n)\)，他们每次可以向右或向下走一格，求最后分别到 \((1,0),\ldots,(n,0)\) 的方案数。\(n,a_i<=10^6\)。

首先根据 LGV 引理可以得到答案是求：

\[\left|\begin{array}{cccc} \binom{a_1+1}{1}&\binom{a_1+2}{2}&\cdots&\binom{a_1+n}{n}\\ \binom{a_2+1}{1}&\binom{a_2+2}{2}&\cdots&\binom{a_2+n}{n}\\ \vdots&\vdots&\ddots&\vdots\\ \binom{a_n+1}{1}&\binom{a_n+2}{2}&\cdots&\binom{a_n+n}{n} \end{array}\right| \]

提出公因子来可以得到

\[\frac{\prod (a_i+1)}{1!2!\cdots n!}\left|\begin{array}{cccc} 1&(a_1+2)^{\underline{1}}&\cdots&(a_1+n)^{\underline{n-1}}\\ 1&(a_2+2)^{\underline{1}}&\cdots&(a_2+n)^{\underline{n-1}}\\ \vdots&\vdots&\ddots&\vdots\\ 1&(a_n+2)^{\underline{1}}&\cdots&(a_n+n)^{\underline{n-1}} \end{array}\right| \]

然后有一个结论说的是，任意的矩阵满足 \(A_{i,j}\) 为 \(a_j\) 的 \(i-1\) 次多项式，都可以消元成以下形式：

\[\frac{\prod (a_i+1)}{1!2!\cdots n!}\left|\begin{array}{cccc} 1&a_1&\cdots&a_1^{n-1}\\ 1&a_2&\cdots&a_2^{n-1}\\ \vdots&\vdots&\ddots&\vdots\\ 1&a_n&\cdots&a_n^{n-1} \end{array}\right| \]

然后这个东西叫做范特蒙德矩阵，行列式就是

\[\prod_{1\leq i

令 \(g_j\) 表示 \(a_i=j\) 的 \(i\) 的数量，则原式可以写成

\[\sum_{k}k\big(\sum_{j=k}^{10^6}g_j g_{j-k}\big) \]

直接卷积即可。复杂度 \(O(V\log V)\)。

Day 7

图论与网络流

一、强连通分量

1. 强连通分量是一个极大强连通子图。

2. 忘了……

3. kosaraju算法缩点：dfs求post-order(dfs回溯顺序)，然后边反向、用post-order反序dfs，每一次搜到的点都在一个强连通分量里面，这一次的顺序就是DAG的拓扑序。然后建边就扫描原图中的点就行了。

例题：CF949C，根据条件建有向边缩点求最小的出度为0的强联通分量

二、2-SAT

1. 把每个点分成真假两个状态。
2. x->y：若要取x这个状态，必须取y这个状态。
3. 如果x->非x，那么无解。
4. 最后就缩点然后看每个点的哪个状态在强连通分量内即可。
5. a是真：非a->a

例题：P5332，每一个人在每一个时间建一个点然后2-SAT建图，如果最后的那个x能够连向最后的非x，那么忽略这个点。在另外的点中找出每个人真能够连向的所有真。

三、欧拉回路

1. 有一个巧妙的方法。

例题：CF1361C

四、割点与桥

1. 定义dfn和low两个数组。
2. 点双联通分量是用割顶相连的，边双联通是用桥相连的。
3. 求点双联通，找到割点，从栈中弹出来的点都在同一个点双连通分量中。
4. 同理，边双和桥一样。

例题：LCT维护动态的边双联通缩点树，查询树上路径和。LCT经典维护方案，套一个并查集（Father），然后每个点访问到之后直接访问它的find(x)，如果这个点是根，那相当于这个点存在在LCT中，否则不存在。复杂度没有问题。

五、圆方树

0. 仙人掌：任意一条边至多只在一个简单环内。
1. 狭义圆方树求解仙人掌问题。把仙人掌转化为圆方树从而可以使用树形dp等问题求解。
2. 广义圆方树对于每一个图中的点双连通分量建立一个方点，把原图中的点删掉然后从每一个方点向它所对应的点双中的点连边。两个性质。

例题：CF487E，圆方树树剖板子。

六、网络流

1. 最大流Dinic两个优化：当前弧和炸点

例题：CF1082G，基础网络流最小割模型建图。

2. dijk优化spfa的费用流，类似于Johnson。

3. zkw费用流就是在最短路径上跑Dinic。

例题TOPCODER12432

4. 无源汇上下界可行流

5. 有源汇上下界最大流