做题记录 25.10.16
szt100309
·
·
个人记录
\textcolor{black}\odot AT_arc138_f [ARC138F] KD Tree
令 dp_S 表示子集 S 的答案
显然 |S|=1 时方案数为 1，答案为 dp_U
枚举 2n-2 条分割线，设第 i 条分割出两个集合 T_i 和 S/T_i，将 T 去重并去掉其中等于 0 或 S 的
转化为可以选择一个 T_i 将 S 拆为 T_i 和 S/T_i，求最终得到的不同序列的数量
令 f_i 表示选择 T_i 时的方案数（对于一个方案，若存在多条合法的，则选择 T 最小的，若不唯一则选择编号最小的），容斥可得 f_i=dp_{T_i}-\sum_{j<i,T_j\subset T_i} f_j dp_{T_i/T_j}，dp_S=\sum_i f_i dp_{S/T_i}
单个 dp_S 转移为 O(n^2) 的，显然 S 一定为某个子矩形内的全体点，因此只有 O(n^4) 种，使用记忆化搜索，总复杂度 O(n^6)，常数较小
代码
参考
\textcolor{black}\odot CF1988F Heartbeat
令 f_{i,j,k} 表示长度为 i 的排列，有 j 个前缀最大值 k 个上升位置的方案数，g_{i,j,k} 表示长度为 i 排列，有 j 个后缀最大值 k 个上升位置的方案数，边界为 f_{0,0,0}=g_{0,0,0}=f_{1,1,0}=g_{1,1,0}=0
转移时考虑最小值放置在首/尾/一对上升位置之间/一对下降位置之间，易得
f_{i,j,k}\to f_{i+1,i+1,j+1}\\
f_{i,j,k}\to f_{i+1,j,k}\\
kf_{i,j,k}\to f_{i+1,j,k}\\
(i-k-1)f_{i,j,k}\to f_{i+1,j,k+1}\\
g_{i,j,k}\to g_{i+1,i,j+1}\\
g_{i,j,k}\to g_{i+1,j+1,k}\\
kg_{i,j,k}\to g_{i+1,j,k}\\
(i-k-1)g_{i,j,k}\to g_{i+1,j,k+1}\\
$$
S_n=\sum_{p=1}^n \sum_i\sum_j\sum_x\sum_y \binom{n-1}{p-1} f_{p-1,i,x}g_{n-p,j,y}a_{i+1}b_{j+1}c_{x+y+[p>1]}
$$
令 $u_{p,x}=\sum_i f_{p,i,x}a_{i+1}$，$v_{p,y}=\sum_j g_{p,j,y}b_{j+1}$，则
$$
\begin{aligned}
S_n=&\sum_{p=1}^n \binom{n-1}{p-1} \sum_x\sum_y u_{p-1,x}v_{n-p,y}c_{x+y+[p>1]}\\
=&(n-1)!\sum_{p=1}^n \sum_x\sum_y \frac{u_{p-1,x}}{(p-1)!}\frac{v_{n-p,y}}{(n-p)!}c_{x+y+[p>1]}\\
\end{aligned}
$$
令 $S'_n=\frac{S_n}{(n-1)!}$，$u'_{i,x}\gets \frac{u_{i,x}}{i!}$，$v'_{i,x}\gets \frac{v_{i,x}}{i!}$，则
$$
S'_n=\sum_{p=1}^n \sum_x\sum_y u'_{p-1,x}v'_{n-p,y}c_{x+y+[p>1]}\\
$$
枚举 $i=p-1,j=n-p,x,y$，将 $u'_{i,x}v'_{j,y}c_{x+y+[i>0]}$ 贡献到 $S'_{i+j+1}
令 t_{i,y}=\sum_x u'_{i,x}c_{x,y+[i>0]}，容易把计算 S 优化到 O(n^3)
总时间复杂度 O(n^3)，空间复杂度 O(n^2)
代码
参考
\blue\odot P14192 [ICPC 2024 Hangzhou R] Fuzzy Ranking
一种暴力的算法为每个 a_{i,j} 向 a_{i,j+1} 连边，然后求出 \text{SCC}，对于每个 a_{1,\ast}，其中的 \text{SCC} 必然为一个区间，因此容易做到 O(nk+q\log n)
可证所有 a_{i,\ast} 得到的区间相同，且 j 为区间右端点当且仅当 |\{a_{i,k}\mid k\le j\}|=j，精细实现容易做到 O(nk+q)
代码
参考