2023NOIP A层联测32
目录A flandre
有 \(n\) 种烟花，每种烟花有两个参数 \(a ， b\)，你要构造一种燃放顺序，使得 \(b\) 的和最大， \(b\) 会改变，具体来说：设 \(i\) 在 \(j\) 前燃放，那么。
- \(a_i < a_j\) ，则 \(b_j +k \to b_j\)
- \(a_i = a_j\) 则 \(b_j\) 不变
- \(a_i >a_j\) 则 \(b_j - k \to b_j\)
\(1\le n \le 10^6\)
这个题考场就想到了正解。思考一下，最优方案满足一个性质，将 \(a\) 从小到大排序，依次燃放。暴力求答案，然后选出最优的方案就好了，可惜有一个变量没有给初始值挂了 \(70\) 分，关键是大样例还过了。
B.meirin
给定两个序列 \(a , b\)
\(q\) 次操作，每次把 \(b\) 的 \([l , r]\) 的每个值加上 \(k\) ，每次操作后查询：
\[\sum _{l = 1} ^n \sum_{r = l}^n(\sum_{i= l}^r a_i) \times (\sum_{i= l}^r b_i) \mod (10^9 + 7) \]\(n , q \le 5 \times 10^5\)
因为修改的是 \(b\) 的值，我们就可以考虑把 \([l , r]\) 里面的值对答案的影响算出来。
设 \(sum1_i\) 是 \(i \times a_i\) 的前缀和， \(sum2_i\) 就是 \((n - i + 1) \times a_i\) 的前缀和。
每个 \(b_i\) 的贡献就是 \(sum1_{i - 1}\times (n - i + 1) +sum2_{i + 1} \times i +a_i \times i \times(n - i + 1)\)
用一个前缀和维护一下这个值就可以做到 \(O(1)\) 修改。
考场最后 \(30 min\) 才想到正解，但是码了 \(15min\) 发现只能过小样例过不了大样例，考后才发现是快写打错了。
C.sakuya
有 \(n\) 个房间构成了一棵树，边有边权。树上有 \(m\) 个特殊的房间，求走完这些房间的期望。
每次修改会使得连接 \(x\) 的所有边加上 \(k\)
\(n , m , q \le 5 \times 10^5\)
考虑修改一条边的影响，就是这条边两端的特殊房间的数量的乘积。
先把答案求出来，每次修改的时候就是把答案加上这个影响乘上 \(k\) 就好了。
D. 红楼 ~ Eastern Dream
给出一个长度为 \(n\) 的序列 \(a\) ，有 \(m\) 次操作，格式如下：
- \(1, x , y , k\) 对于所有满足 \((i - 1) \mod x \le y\) 的 \(i\) ，将 \(a_i\) 加上 \(k\)
- \(2, l , r\) 求 \(\sum_{i= 1}^r a_i\)
\(n , m \le 2 \le 10^5\)
根号分治。维护两个数组 \(v_{i , j} , vs_i\) ，表示对于所有 \((x - 1) \mod i = j\) 的 \(x\) ，\(a_x\) 要加上的值， $vs_{i , j} $ 是 \(v _{i , j}\) 的前缀和，即对于所有 \((x - 1) \mod i \le j\) 的\(x\) ，\(a_x\) 要加上的值。
\(x\le \sqrt n\) 可以直接修改。
\(x\ge \sqrt n\) 需要用分块维护差分
总结
期望得分：\(100 +100 + 0 +25 = 225\)
实际得分：\(70 + 30 + 0 + 25 = 115\)
这次本来是一个信心场，但还是失误了。两个题想到正解都挂了，一个是忘记设初值，一个是快写打错，就是自己的代码实现能力不足了。而且码完一个题可以考虑先检查一小会。\(T3\) 还没有拿到暴力分，遇到这种自己不熟练的题目，可以打打暴力，而不是直接就跳了。
标签：10,le,32,sum,times,联测,2023NOIP,mod From： https://www.cnblogs.com/2020fengziyang/p/17834994.html