测试题目选集
2024/09/09
qoj #8822. Guess The Sequence 2
给出长度为 \(n\) 的排列 \(a\)，需要选择一个 \([1,n]\) 上的一些子区间构成的集合，然后对于集合中的每个区间返回 \(a\) 上这段区间的 \(a_i\) 最大值。如果通过这些信息可以唯一确定排列 \(a\)，那么称这个集合是好的。需要统计有多少个区间集合是好的。
\(n\le 10^5\)，排列随机均匀生成。
觉得主要的困难点在于考场上并不能很快的笃定性质是否正确，做法是否会算少算多。
将区间按照 \(\max_{l\le i\le r}a_i\) 分成 \(n\) 个种类，称 \(\max_{l\le i\le r} a_i=k\) 的区间 \([l,r]\) 为第 \(k\) 类。
考虑一种通过已知信息求出 \(a\) 的方法：
策略是从小往大确定 \(a_{i_1}=1,a_{i_2}=2,\cdots\) 的这些 \(i_1,i_2,\cdots\)。
给出四条性质，对求值有帮助：
- 如果已知 \(i_1,i_2,\cdots,i_{k-1}\)，且存在第 \(k\) 类区间，则可以求出 \(i_k\)。
- 如果已知 \(i_1,i_2,\cdots,i_{k-1}\)，而不知道 \(i_k\)，但是区间集合中对于第 \(k+1,k+2,\cdots,j\) 类区间都存在与 \(i_k\) 不交的一个该类区间，那么可以求出 \(i_{k+1},\cdots,i_j\)。
- 如果已知 \(i_1,i_2,\cdots,i_{k-1},i_{k+1},\cdots,i_j\) 且存在第 \(j\) 类区间与 \(i_k\) 有交，那么可以求出 \(i_k\)。
- 每次求出一个未知的 \(i_t\)，如果要求每次的 \(t\) 都是最小的，那么如果求出 \(i_t\) 后存在超过一个 \(q < t\) 满足 \(i_q\) 尚未确定，那么说明区间集合一定无法唯一地确定出 \(\{i\}\)。
那么就可以进行 dp 了。记 \(f_u\) 表示已经决定了第 \(1,2,\cdots,u-1\) 类区间的选取，且已知 \(i_1,i_2,\cdots{},i_{u-1}\)，选取第 \(u\) 类到第 \(n\) 类区间的方案数。x
为了方便，记 \(i\) 左边第一个大于 \(a_i\) 的位置为 \(l_i\)，没有则为 \(0\)；右边第一个大于 \(a_i\) 的位置为 \(r_i\)，没有则为 \(n+1\)； \(w(x)=2^x\)。
那么转移为：
\[\forall i:a_{p_i}=i \\ a_{p_u}=u< a_{p_v}=v : \\ f_u \leftarrow \\ [\max_{(i-p_u)(i-p_v)\le 0} a_i=v]\prod_{i=u+1}^{v}( w(|\{[x,y]\mid l_{p_i}\le x\le p_i\le y \le r_{p_i}, p_u\notin [l_{p_i},r_{p_i}] \}|) -1) (w(|\{[x,y]\mid l_{p_v}\le x\le p_v\le y \le r_{p_v}, p_u\in [l_{p_i},r_{p_i}] \}|)-[v=n])f_v \]初始 \(f_{n+1}=1\)，答案是 \(f_1\)，式子中的 \(|\{\cdots\}|\) 可以通过 \(l_i,r_i\) 计算。
看似时间复杂度是 \(O(n^2)\) 的，但是发现因为有 \(\max_{(i-p_u)(i-p_v)\le 0} a_i=v\) 的限制，所以 \(p_v\) 一定在原排列的笛卡尔树上是 \(p_u\) 的祖先。随机数据下排列的笛卡尔树树高期望为 \(\log_2 n\)，因此期望时间复杂度为 \(O(n\log_2 n)\)。
Miscellaneous
Codeforces 1967E2 - Again Counting Arrays(Hard Version)
考虑如何能够做到 \(O(nm)\) 的实现。
讲讲我的思路：可以把通过 \(a_i\) 求出合法 \(b_i\) 的过程，看作是从前往后维护位置 \(i\) 的可选的 \(b_i\) 构成的集合 \(s_i\)，然后如果 \(a_i\) 在这个集合中就将其删去变为 \(s_i'\)，然后得到 \(i+1\) 的集合 \(s_{i+1}=\{x\mid \exists t\in s_i',|t-x|=1\}\)。发现这个集合实际上是一个以 \(0\) 或 \(1\) 为左端点，只包含奇数或者偶数的一段区间。那么只需要维护最大值就可以了。
但是实际上换换思路也可以直接想到维护最大值。
然后就会有一个 dp：\(f_{i,j}\) 代表考虑位置 \(i\) ，且最大值为 \(j\) 时的不同的 \((a_1,\cdots,a_i)\) 的个数。转移较为简单，可以直接考虑 \(a_{i+1}\) 的取值，\(a_{i+1}=j+1\) 的情况转移到 \(f_{i+1,j-1}\)；其他情况则转移到 \(f_{i+1,j+1}\)。请注意 \(b_i\) 的值域是 \([1,m]\)，所以对于 \(f_{i,m}\) 就直接乘以 \(m^{n-i}\) 计入答案就可以了。
答案就是 \(\sum_{i=1}^{n-1} m^{n-i} f_{i,m}+\sum_{i=1}^m f_{n,i}\)。
当然显然是过不去的，那么考虑本质。上述的问题实际上是一个 \(n+m\) 个终点的格路计数，条件是每次走左上乘以 \(m-1\) 或者左下乘以 \(1\)，除了终点外不经过 \(y=-1\) 和 \(y=m\)。直接做可以做到 \(O(\frac{n^2}{m} + m)\)。于是可以得到一种缝合得到 \(O(n\sqrt n)\) 的做法。但是不足以通过 Hard Version。
感觉 \(n+m\) 个终点实在繁琐，于是考虑当折线第一次经过 \((i,m)\) 之后仍然按照正常的方式走，最终从这个点走出直到所有 \((n,x)\) 的贡献加起来应该就是 \(m^{n-i} f_{i,m}\)，正是我们所需要的。
这样我们就转化成了 \(2n+1\) 个形如 \((n,x)\) 的终点，其中 \(x\in[-n,n]\)。
首先一个基本的事情是，如果没有任何要求，那么从 \((0,b)\) 走到 \((n,x)\) 的方案数为 \({n\choose (x-b+n)/2}\)。
记事件“以前不与 \(y=m\) 相交或者最近与 \(y=m\) 相交后又与 \(y=-1\) 相交，当前与 \(y=m\) 相交”的事件称为 \(A\)，同理记 \(y=-1\) 相关的为 \(B\)，记 \(F(Q_1Q_2Q_3\cdots)\) 表示 \(Q_1,Q_2,Q_3\cdots\) 顺次发生后抵达当前位置的方案数。如果不清楚定义的可以去查查格路计数相关内容。
显然，到达 \((n,x)\) 的折线经历的事件必然是 \(\empty\) 或者 \(ABABA\cdots\)（先经过 \(A\)）。
那么可以考虑 \((n,x)\) 的贡献，但是需要考虑 \(x\ge 0\) 和 \(x<0\) 两种情况。当 \(x\ge 0\) 时贡献是 \(F(\empty) - F(B)+F(AB)-F(BAB)+\cdots\) ；而当 \(x<0\) 时贡献是 \(F(A)-F(BA)+F(ABA)-\cdots\)。而把两种情况单独考率容斥，会发现经过对称后他们仍然落在连续的位置上，会给答案贡献形如 \((-1)^t {n\choose (i-b+n)/2}(m-1)^{i-d}\)，其中 \(t\) 和 \(d\) 因情况而异。于是可以使用差分，对于每个 \(i\) 将 \((m-1)^i\) 当作额外系数。于是就可以做了。借鉴了别人的实现，代码非常精简。
Submission #280925816 - Codeforces
标签：le,可以,09,2024,集合,cdots,那么,做做,区间 From： https://www.cnblogs.com/imcaigou/p/18412870