CYEZ 模拟赛 2-Toy模板网

这篇具有很好参考价值的文章主要介绍了CYEZ 模拟赛 2。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题面

A 毒瘤计数题

萌萌题。

枚举 $i=\min (S)$ ，答案就是 $\sum _{i=1}^n 2^{n-i}(2^{i-1}-1)$ ，容易化成 $n\times 2^{n-1}-2^n+1$ 。

开 __int128。

代码

B 普通图论题

卡卡题。

$O (n)$ 换根。记录最小值、次小值。

代码

C 简单数据结构题

难难题。

算法 1：

标记区间的并，枚举关系，时间复杂度 $O (q (n + m))$ 。

算法 2：

把互斥关系视为二维点。对于 $\in [l_i,r_i]$ ， $\forall j$ ，数 $\in [l_i, r_j]$ 时是否有点。

二维数点一般做法是用 BIT，我们将询问离线后搭配扫描线可以做到 $O((\sum k^2 + m)\log n)$ 。

对于在线做法，考虑可持久化线段树。具体地，考虑维护 $n$ 棵线段树，每棵线段树维护 $x\in [1,i]$ 的矩阵点数。查矩形 $l_i,r_i)(l_j,r_j)$ 就拿第 $r_i$ 棵线段树的区间询问减去第 $l_i-1$ 棵的。复杂度 $\log n + \sum k^2 \log n)$ 。

根号分治

算法 1 在 $q$ 较小时效率较高，算法 2 在 $k$ 较小时效率较高。而随着 $q$ 的增大， $k$ 减小。因此考虑分治， $k > B$ 时算法 1， $\le B$ 时算法 2。

分别计算上界：算法 1 至多执行 $\frac {\sum k} {B}$ 次，上界 $O(\frac {\sum k} {B} (n +m))$ 。算法 2 在 $k$ 较大时会取到上界，所有的 $k = B$ 时，算法 2 至多执行 $\frac {\sum k} {B}$ 次，上界 $O(\frac{\sum k}{B}\times B^2 \log n)$ 。

总时间复杂度为 $O(\frac {\sum k} {B} (n +m) + \frac{\sum k}{B}\times B^2 \log n)$ 。 $n,m,q,\sum k$ 同阶时， $\sqrt{\frac{n}{\log n}}$ 时取得最小值。

代码

总结

预估 $100 + 100 + 40 = 240$ ，实际 $100 + 90 + 60 = 250$ 。B 同样的代码赛后能过，评测机的锅。萌新 A B 花的时间有点长，遂 C 打了个还算优秀的暴力，转二维数点和根号分治比较难想到。文章来源地址https://www.toymoban.com/news/detail-701223.html