Spark Exam 20240713
Conclusion
还可以，没有挂分（反向挂分什么鬼）。
数据简直太平洋，T1放掉log，T3 30变80，T4 10%的特殊case变成30%的特殊case
dp 还是很不行，其他方面的思维还可以。
A. 不相邻集合 (a)
Statement
称可重集合 \(S\) ，若满足 \(\forall x\in S,x-1\notin S,x+1\notin S\) ，称 \(S\) 满足 \(P\) 性质。给定序列 \(a\) ，对于 \(i\in[1,n]\) ，求最大的满足 \(P\) 性质的 \(|S|\subseteq \{a_i|i\in [1,i]\}\) 。
\(1\le n\le 3\times 10^5,1\le a_i\le 5\times 10^5\)
Solution
Algorithm 1
注意到，若将数排序，那么当前最小的能选的数一定必选。这为我们带来一个 \(\mathcal O(n^2)\) 的方法。
Algorithm 2
使用线段树维护包不包括端点的答案，发现可以上传标记，\(\mathcal O(n\log n)\) 切掉。
Algorithm 3
注意到，上面我们的做法中，没有考虑到两个前后缀之间只加了一个数这个事实，发现一段连续段的贡献是长度除二上取整，而添加一个数，连续段更改是 \(\mathcal O(1)\) 个的 ，则考虑 std::set 维护连续段，\(\mathcal O(n\log n)\) 切掉。
这是作者的做法（虽然没有 Algorithm 4 好写）
Algorithm 4
值域不大，可以直接开一个数组维护属于的段编号，Algorithm 3 中的维护能够在 \(\mathcal O(1)\) 之内完成。同理，使用并查集可以在 \(\mathcal O(\alpha(n))\) 的时间内完成，总共时间复杂度 \(\mathcal O(n)\) 切掉。
B. 线段树 (b)
Statement
对于如下代码生成的线段树：
void build(int i, int l, int r) {
L[i] = l; R[i] = r;
if (l == r) return;
int mid = (l+r)/2;
build(i*2, l, mid); build(i*2+1, mid+1, r);
}
\(T\) 次询问，求 \(\sum_{x\le L[i]\le R[i]\le y} i\pmod {10^9+7}\)
\(T\le 10^4,x,y\le 10^{18}\)
Solution
注意到：询问区间可以在线段树上拆成 \(\mathcal O(\log n)\) 个点，又发现，一棵线段树的形态只与区间长度有关系，考虑到线段树的标号和可以表示为 \(aS+b\) 其中 \(S\) 是根节点编号，则可以递推计算这个关系式，此时能够通过 \(40\%+20\%\) 的数据。
考虑不要推那么多，只推二的次幂，然后不是整次幂的就记忆化搜索，就切掉了。
C. 魔法师 (c)
Statement
维护可重集 \(S,T\) ，支持如下操作 \(Q\) 次：1. 向其中一个集合加入二元组 \((a,b),a,b\in \mathbb N\) 2. 删除一个二元组 \((a,b)\) 。每次操作之后，求出 \(\min_{(a,b)\in S,(x,y)\in T}\max\{a+x,b+y\}\)
Solution
真是太可惜了，已经找出所有需要的了，维护方法却没想到，这方法明明是我之前独立想出来过的。
Algorithm 1
暴力做，这是 \(\mathcal O(n^3)\) 的，期望获得 \(10\%\) 的分数。
数据太水，实际上获得了 \(80\%\)
Algorithm 2
\(\max\) 记号很不好处理，考虑分类讨论。对于 \(a+x\le b+y\) ，移项得 \(a-b\le y-x\) ，考虑将两个集合分别排序，然后可以使用双指针处理询问，复杂度是 \(\mathcal O(n^2)\) 的，期望得分 \(30\%\)
这就是作者的做法，可是得了 80 emm
Algorithm 3
我们走在正确的道路上！这种有偏序关系的询问我们不由得想到分治算法，但是其关键是通过部分排序进行双侧贡献，我们还要支持修改，用线段树的左右区间不是也可以限制偏序关系吗！这样我们就避免贡献不必要的节点，\(\mathcal O(Q\log n)\) 切掉。
本题做法其实与前天
meirin那个题目很像，不过那个题目线段树无法更新答案呢。但是这个用线段树限制偏序关系的思路是值得借鉴的！