260407-260409

260407 T1

有 \(n\) 天，有两种共享单车，每天是三种情况之一：只有第一种，只有第二种，两种都有。你一次可以购买一种自行车在一段长为 \(L\) 的时间区间的使用权，问你如果每天都要有自行车用，至少要买多少次。

\(n\le 5\times 10^6\)

直接 dp，发现其实只需要记录第二种自行车的剩余时间，然后发现只关心 dp 值最优的一个，于是直接 dp。

有 \(n\) 个集合，你需要从每个集合中选出一个数，使得选出的数两两不同，定义方案的权值为选出的数的乘积，不同集合选出的数相互区分。求所有合法方案的权值和。

\(n\le 18,~\sum|S|\le 5\times 10^6\)

考虑容斥，我们钦定全集的一个划分，每个部分内部颜色全相等。一种划分会被所有更细的划分统计到。不同于我们的经典容斥，那是会被所有子集统计到。

考虑划分中的一个块，我们希望它的所有划分的容斥系数之和等于 \([|S|\le 1]\)，也即容斥系数的 \(\exp\) 等于 \(1+x\)，直接取对数：

\[ \ln(1+x)=x-\frac{x^2}{2}+\frac{x^3}{3}-\frac{x^4}{4}\cdots=\sum_{i=1}(-1)^{i+1}(i-1)!\frac{x^i}{i!} \]

也就是说给划分中的一个块赋予 \((-1)^{|S|+1}(|S|-1)!\) 的容斥系数，就可以使每种不合法方案被统计 \(0\) 次。

给定一个排列，你可以选择一个起点，每次走到左边第一个更大的位置或者右边第一个更大的位置上。有 \(m\) 次询问，每次给定 \([l,r]\)，询问如果只走值域在 \([l,r]\) 内的数，有多少种可能的路径。

\(n,m\le 2\times 10^5\)

建出大根笛卡尔树，然后按 \(l\) 扫描线，发现每次加一个点形如更新一条根链，但是根链不能暴力跳。考虑树分块，我们找到最近的一个关键点，中间的非关键点直接用一个 \(O(1)-O(\sqrt n)\) 的分块维护，对关键点我们预处理出每个关键点对每个深度以下的贡献，查询时直接枚举所有关键点即可。

逐个处理关键点可以做到线性空间。