solution
神仙 dp 题。
下文认为 \(n\) 是题目中给定 \(n\) 的两倍。
先考虑一个给定的序列是否能被消除的条件。
猜测一下应该是
-
序列长度是偶数
-
不存在一个数,在序列中出现超过 \(\lfloor\dfrac{n}{2}\rfloor\) 次,其中 \(n\) 是序列长度。
必要性是显然的。我们每次尽可能消出现次数最多的数,如果满足条件 2,那么当然也是可以消完的(消掉两个数后变成了子问题),所以也有充分性。
设 \(f_i\) 表示考虑前 \(i\) 个数的答案,有转移:
-
\(f_0=1\)
-
\(f_{2k+1}=0\)
-
\(f_{2k}=\sum\limits_{i=0}^{2k-1} [2\mid i][\texttt{chk}(i+1,2k)]f_i\),\(\texttt{chk}(l,r)\) 表示区间 \((l,r)\) 是可消的。
对于第三个式子,固定 \(2k\),从后往前扫,可以顺便维护 \(\texttt{chk}\),时间复杂度 \(O(n^2)\)。
考虑如何优化转移。
打表发现转移没有什么好的性质,每次转移点变化量之和也是不太能接受的大小。
考虑使用 CDQ 分治优化转移(比较突兀哈,zyb 猜的做法,后来发现可以做)。
对于区间 \([l,r]\),设它分成 \([l,mid]\) 与 \([mid+1,r]\) 两个区间,由于是从前向后算,先递归求出 \([l,mid]\) 内所有 dp 值,然后考虑区间 \([l,mid]\) 对区间 \([mid+1,r]\) 的贡献。
这样做有很好的性质。
性质:对于所有 \([L,R],l\leq L\leq mid,mid+1\leq R\leq r\),可能的出现次数大于区间一半的数的种类只有 \(O(\log(r-l))\) 个。
对于证明,先考虑一个前置结论:
一个序列任意前后缀的出现次数大于区间长度一半的数的种类只有 \(O(\log n)\) 个,\(n\) 是序列长度。
比较容易看出,就不证了。
\([L,R]\) 相当于 \([l,mid]\) 的一个后缀和 \([mid+1,r]\) 的一个前缀拼起来,这样数的种类也就不超过 \(O(\log(r-l))\) 个了。
这样就允许我们在计算贡献的时候枚举这样的数了。
注意,这些非法的转移的贡献是负的,要先把所有 \(i<p\) 的 \(f_i\) 贡献到 \(f_p\) 上,然后在根据下面的做法减去这些非法转移的贡献。
枚举左端点,然后枚举这些数,用数据结构维护贡献。
具体实现流程如下:
下面设区间长度为 \(m\)。
先处理出来这样的数,去重。可以 \(O(m\log m)\) 做到。(\(\log\) 是去重时排序给的),设有 \(sz\) 个这样的数。
设一个这样的数 \(p\) 的前缀出现次数是 \(c_{p,i}\),则区间 \([l,r]\) 能因为这个数不合法的条件就是 \(\dfrac{r-l+1}{2}<2c_{p,r}-2c_{p,l-1}\),整理得 \(2c_{p,l-1}-(l-1)<2c_{p,r}-r\)。所以我们不妨给每个数 \(sz\) 个权值,数 \(p\) 在 \(i\) 位置的对应权值就是 \(2c_{p,i}-i\)。然后开 \(sz\) 个差分数组,整个分治区间内的数按照 \((2c_{p,i},i)\) 第一关键字递增,第二关键字递减(第二关键字递减是为了让 \([l,mid]\) 内的数排到后面,处理 \(<\) 号,而不能取等)。再处理出每个数在这 \(sz\) 个排序后的数组里的下标。都可以 \(O(m\log m)\) 处理好。
枚举不合法左端点,再枚举这 \(sz\) 个数,然后在对应的差分数组里做修改,修改是 \(O(1)\) 的,枚举是 \(O(m\log m)\) 的。
最后把差分数组前缀和一遍,对应 dp 值加上贡献即可。
带上 CDQ 的 \(\log\),时间复杂度 \(O(n\log^2n)\)。
细节比较多,而且有点卡常(official solution 是 \(O(n)\) 的)。
code
Submission #47182618 - AtCoder Regular Contest 159
标签:log,mid,ARC159F,序列,枚举,区间,2k From: https://www.cnblogs.com/FreshOrange/p/17808534.html