Spark Exam 20240711
Conclusion
比较可惜，做前面AB的时候状态不错，但是后面就不行了，C题直接想错了一个点，然后又没有继续想，D题确实不知道一些技巧，但是其实已经凑齐了正解的全部拼图，可以拿到 60-70 pts.
score240|rnk3|est260|ideal360|idealrnk2
A. flandre
Statement
定义一个序列的权值：
\[S(a)=\sum_{i}{a_i}+\sum_{i<j} \left\{\begin{aligned} &k && a_i<a_j\\ &-k && a_i>a_j\\ &0 && a_i=a_j \end{aligned}\right. \]给定一个可重集，求将它的一个子集排序之后能够得到的权值的最大值。
Solution
可以证明，当选择集合 \(S\) 之后，一定按照升序排列，则对于大小为 \(|S|\) 的方案来说，一定要选择最大的那些，故降序排序 \(\mathcal O(n\log n)\) 解决。
B. meirin
Statement
对于序列 \(a,b\) ，维护操作：
-
单点修改 \(b\)
-
求 \(\sum_l\sum_r(\sum_{i\in[l,r]}a_i)\times(\sum_{j\in[l,r]}b_j)\)
Solution
拆掉下面的式子，尝试把式子变成点对贡献的问题（这样就多一个分讨），然后发现线段树做不了emm。这里的关键在于本题是全局查询，不需要、也很难维护区间，所以考虑维护一个前缀和后缀和，轻松愉悦 \(\mathcal O(n)\) 切掉。
考试时的精神状态：
我有没有搞错，这个直接线段树是不是就解决了？ 哦不是 拆一下式子看看 \sum_{i=[l,r]} (a_i\sum_{j=[l,r]} b_j) 每一个包含数对 (i,j) 的区间都会贡献一次 a_i*b_j 这个数量是(若i<=j) i*(n-j+1) 个区间 假设下面先算 i<=j 的情况 \sum_i\sum_j a_i*b_j*i*(n-j+1) \sum_i (a_i*i)\sum_j b_j*(n-j+1) |as1 |bs1 后面这个式子内的值，和i没有关系处理为 SUM 则优化至 O(N) i>j 则同理 ---------------------------------------- 以上当然是不带修改的做法 一旦修改，则 SUM 会发生变化 (b_j+k)*(n-j+1) += k*(n-j+1) =k*(n+1)-k*j 什么，怎么感觉不用线段树？ 现在补全一下 i>j \sum_i\sum_j a_i*b_j*j*(n-i+1) \sum_i a_i*(n-i+1)\sum b_j*j |as2 |bs2 还真的不用线段树？？？ 什么玩意 我算错了吗 不对，后面那个部分是有范围的 那就用线段树 把左边区间的 \sum_i(a_i*i) 和右边的 \sum_j b_j(n-j+1) ×起来贡献给答案即可 然后把左边区间的 \sum b_j*j 和右边的 \sum_i a_i*(n-i+1) 也这样 然后单独算 i==j \sum_i a_i*b_i*i*(n-i+1) 上面这些能够很快维护 SUM 的值，所以才可以打的上标记 O(n\log n) 答案怎么维护？这个区间当前肯定已经考察了全部数对 (i,j) 对于 j,对左边的所有i多贡献k(n+1)-k*j 对于右边的多贡献 k*j 对总体区间多贡献 (j-l+1)(k(n+1)-k*j)+(r-j)k*j jk(n+1)-kj^2-lk(n+1)+lkj+k(n+1)-kj+rkj-kj^2 这样，因为是全局查询，我们不应该维护这种利于区间查询的信息 而是对于要被修改的 j，总共多贡献： |SP (\sum_{i<=j}a_i*i)*(k*(n+1)-k*j)+ (k*j)*(\sum_{i>j}a_i*(n-i+1)) |SA k(SP*(n+1)+(SA-SP)*j) 这样就又不用线段树了（雾
C. sakuya
Statement
有点复杂跳过。