FUN WORLD

Statement 给你一个长为 nnn 的序列 aia_iai​，mmm 次询问，每次询问给出 l,rl,rl,r，求 min⁡i,j∈[l..r]∧i≠j{∣ai−aj∣}\min_{i, j \in [l.. r] \land i \ne j}\{|a_i - a_j|\} i,j∈[l..r]∧i=jmin​{∣ai​−aj​∣} 数据范围：n≤105n \le 10^5n≤105，m≤3×105m \le 3 \times 10^5m≤3×105，0≤ai≤1090 \le a_i \le 10^90≤ai​≤109。 Solution 离线询问并按右端点升序排序，在 rrr 右移的过程中维护每个 lll 的答案。每次 r−1→rr - 1 \rightarrow rr−1→r 时，要加入 ara_rar​ 和前面的数的贡献。 下面考虑 ax≥ara_x \ge a_rax​≥ar​ 的情况，ax<ara_x < a_rax​<ar​ 的情况同理。 用主席树找到 [1..r−1][1.. r - 1][1..r−1] 中最大的 xxx 满足 ax≥a ...

T1. 假期计划 枚举 B, C 就行，预处理前三大的 A / D。时间复杂度 O(nm+n2)O(nm + n^2)O(nm+n2)。 T2. 策略游戏 按照 B 中是否有正负数分讨即可。 T3. 星战 判断的条件就是每个点出度都为 111。 给每个点随机一个权值 vali\text{val}_ivali​，对于每个点 vvv 维护 sv=∑(u,v)∈Evalus_v = \sum_{(u, v) \in E} \text{val}_usv​=∑(u,v)∈E​valu​，并维护 ∑sv\sum s_v∑sv​。每次检查 ∑sv\sum s_v∑sv​ 是否等于 ∑vali\sum \text{val}_i∑vali​ 即可。 感觉不稳的话就多随几次。 T4. 数据传输 k=2k = 2k=2 的时候中途的点不会跳出 sis_isi​ 到 tit_iti​ 的链上。矩乘加速是显然的。 k=3k = 3k=3 的时候中途的点可能会跳出 sis_isi​ 到 tit_iti​ 的链上，但是可以发现出去的点一定是这条链某个点的邻居。进一步可以发现，这个点一定是链上某个点所有 ...

Statement 有 nnn 根竹子，第 iii 根初始时高度为 hih_ihi​。你需要依次进行如下操作 mmm 轮： 重复 kkk 次，从 nnn 根竹子中选出一根，将它的高度减少 ppp。若当前 hi<ph_i<phi​<p，则将 hih_ihi​ 改为 000。 对于 ∀i∈[1..n]\forall i\in[1..n]∀i∈[1..n]，将第 iii 根竹子的高度增加 aia_iai​。 请你最小化所有操作结束时，最高的竹子的高度。 数据范围：n≤105n\le10^5n≤105，m≤5000m\le5000m≤5000，k≤10k\le10k≤10。 Solution 考虑二分答案后如何 check。不好做的是 hih_ihi​ 会改成 max⁡{hi−p,0}\max\{h_i-p,0\}max{hi​−p,0}。 尝试将整个函数向上平移，函数就变成了 hi+Δh_i+\Deltahi​+Δ 出发到 mid\text{mid}mid，一路上 hih_ihi​ 均 ≥0\ge0≥0。 因为最后时刻是确定的，因此倒序考虑，变成了『有 nnn 根 ...

Statement 给你一张 nnn 个点的完全图，边 (i,j)(i,j)(i,j) 的边权是 w(i,j)w(i,j)w(i,j)。保证所有边权形成一个 1∼n(n−1)21\sim\frac{n(n-1)}21∼2n(n−1)​ 的排列。 请你对每个 k∈[1..n]k\in[1..n]k∈[1..n]，求出把 nnn 个点划分成 kkk 个点集的方案数，满足： 对于任意四个点 a,b,c,da,b,c,da,b,c,d 满足 a,b,ca,b,ca,b,c 同组但 ddd 不同组，有 w(a,b)<w(c,d)w(a,b)<w(c,d)w(a,b)<w(c,d)。 数据范围：n≤1500n\le1500n≤1500。 Solution 条件就是组内边小于组间边，也就是组内边的最大值小于组间边的最小值。 所以按边权从小到大加边，可以发现一个结论：一个连通块可以单分为一组，当且仅当这个连通块在加边的时候，变成了一个团。 因此按照 Kruskal 的过程，维护当前连通块是否是团。到这里应该可以得到指数级的 DP。 比较显然的是，合法连通块一定是 Krusk ...

T1. 排水系统 拓扑排序 + 高精。 T2. 字符串匹配 题意：给你一个长度为字符串 SSS，求对 SSS 的划分个数，使得 S=(AB)iCS=(AB)^iCS=(AB)iC，其中 (s)i(s)^i(s)i 表示将 sss 复制 iii 遍拼接，A,B,CA,B,CA,B,C 均为非空字符串。 多组数据。T≤5T\le5T≤5，∣S∣≤220|S|\le2^{20}∣S∣≤220。 枚举倍数调和级数是 O(nln⁡n+26n)O(n\ln n+26n)O(nlnn+26n) 或者 O(nln⁡nlog⁡26)O(n\ln n\log 26)O(nlnnlog26) 的。 扩展 KMP 可以做到 O(n)O(n)O(n)。 T3. 移球游戏 题意：有 n+1n+1n+1 根柱子，前 nnn 根柱子上每根有 mmm 个球。所有 n×mn\times mn×m 个球共 nnn 种颜色，每种颜色 mmm 个。 你可以对当前局面进行以下操作若干次： 将某柱子顶端的球移到另一个柱子的顶端。 最后使得将相同颜色的球最后全部放置在相同柱子上。操作过程中需要满足： 原来的柱 ...

Day 1, T1. 卡牌游戏 题意：有 nnn 张牌，第 iii 张牌正面写着数字 aia_iai​，背面写着数字 bib_ibi​，初始时正面向上。请你选择 mmm 张牌翻面，使翻面后所有朝上的数字极差（最大值减最小值）最小。 m<n≤106m<n\le10^6m<n≤106，1≤ai,bi≤1091\le a_i,b_i\le10^91≤ai​,bi​≤109，保证所有 ai,bia_i,b_iai​,bi​ 互不相同，ai<ai+1a_i<a_{i+1}ai​<ai+1​。 答案一定是翻牌的一个前缀和一个后缀，即牌 1∼l1\sim l1∼l 为背面，l+1∼r−1l+1\sim r-1l+1∼r−1 为正面，r∼nr\sim nr∼n 为背面。 而且，最优解时一定不会出现 i∈[1,l],ai>bii\in[1,l],a_i>b_ii∈[1,l],ai​>bi​。同理也不会有 i∈[r,n],ai<bii\in[r,n],a_i<b_ii∈[r,n],ai​<bi​。这是因为翻前缀是要使最小值增大， ...

置换群 一个群，满足： 封：封闭性 结：结合律 幺：幺元（单位元） 逆：逆元 交：交换律 Burnside 引理 ∣S/T∣=1∣T∣∑P∈T∑a∈S[P∘a=a]|S/T|=\frac1{|T|}\sum_{P\in T}\sum_{a\in S}[P\circ a=a] ∣S/T∣=∣T∣1​P∈T∑​a∈S∑​[P∘a=a] 其中 ∣S/T∣|S/T|∣S/T∣ 表示 SSS 对 TTT 的商群，即同构的重复元素只算一次。 Polya 引理（Pólya） 针对 SSS 集合为一类固定格子个数 nnn、固定颜色个数 mmm、每个格子独立选择一种颜色填上的问题（TTT 为任意置换群）。有： ∣S/T∣=1∣T∣∑P∈Tmc(P)|S/T|=\frac1{|T|}\sum_{P\in T}m^{c(P)} ∣S/T∣=∣T∣1​P∈T∑​mc(P) 其中 c(P)c(P)c(P) 表示 PPP 的环个数。 应用：大多数时候会按 c(P)c(P)c(P) 分类。 容斥算 Burnside 下面 ans(x)\text{ans}(x)ans(x) 表示 ...

Statement 给你一棵 nnn 个点的森林，点有黑白两种颜色，初始时全为白色，边带权。初始时森林有 mmm 条边。请你支持 qqq 次操作：加边；删边；翻转 uuu 的颜色；询问 uuu 所在的树中所有黑点到它的距离之和。 数据范围：m<n≤105m<n\le10^5m<n≤105，k≤3×105k\le3\times10^5k≤3×105，∣w∣≤107|w|\le10^7∣w∣≤107。 Solution 边权肯定要拆成点权。难点主要是 LCT 的 MakeRoot 中，翻转根节点时不能维护好答案。所以对于每个 xxx，要维护到所在 Splay 深度最浅的点的距离和，以及到所在 Splay 深度最深的点的距离和。 具体而言，对于每个 xxx，都需要维护： 颜色（111 为黑，虚拟节点全为白）：col\text{col}col 虚子树内黑点个数：vcnt\text{vcnt}vcnt 虚子树和 Splay 子树内黑点个数：cnt\text{cnt}cnt 虚子树内黑点到 xxx 的距离和：vans\text{vans}vans 虚子树和 Splay 子 ...

Statement 给你 nnn 个点的空白图（即初始时没有边）。请你支持：加边；求 xxx 所在连通块重心；求所有连通块重心的异或和。保证任何时刻图是森林。 数据范围：n≤105n\le10^5n≤105，m≤2×105m\le2\times10^5m≤2×105。 Solution 树的重心的性质可以看 这里。 Algorithm 1 这个做法需要用到的树的重心的性质： 一棵树添加一个点，重心最多移动一条边。 删掉重心后，最大连通块大小小于等于总结点个数的一半。 根据性质 1，合并两棵树时我们启发式合并，暴力地将较小的那棵树中的点一个一个地插入较大的那棵树。 用 LCT 维护子树大小，对每个点维护两个值：所有虚儿子子树大小之和 vir\text{vir}vir，Splay 上子树内所有点的虚儿子子树大小之和 sum\text{sum}sum。查询点 xxx 的子树大小，可以将它旋转成所在 Splay 的根，然后求 sum(x)+vir(rson(x))+1\text{sum}(x)+\text{vir}(\text{rson}(x))+1sum(x)+vir(rson( ...

组合数 二项式定理：(a+b)n=∑r=0n(nr)an−rbr(a+b)^n=\sum_{r=0}^n\binom nra^{n-r}b^r(a+b)n=∑r=0n​(rn​)an−rbr 范德蒙恒等式：(n+mk)=∑i=0k(ni)(mk−i)\binom{n+m}k=\sum_{i=0}^k\binom ni\binom m{k-i}(kn+m​)=∑i=0k​(in​)(k−im​) 推论：mn(nm)=(n−1m−1)\frac mn\binom nm=\binom{n-1}{m-1}nm​(mn​)=(m−1n−1​) 或 (nm)m=(n−1m−1)n\binom nmm=\binom{n-1}{m-1}n(mn​)m=(m−1n−1​)n 错排列 前 777 项： D0D_0D0​ D1D_1D1​ D2D_2D2​ D3D_3D3​ D4D_4D4​ D5D_5D5​ D6D_6D6​ D7D_7D7​ 000 000 111 222 999 444444 265265265 185418541854 ⋯\cdots⋯ 公 ...