YNOI 选做

太权威了.

蓝题 sin

据说因为太简单被逐出由乃oi.

区间加角度,区间求sin和.
考虑同时维护sin和cos,使用三角函数公式维护,具体地,有

$$\begin{aligned}\sum\sin(a+v)&=\sum(\sin a\cos v+\cos a\sin v)\\&=\left(\sum\sin a\right)\cos v+\left(\sum\cos a\right)\sin v\end{aligned}$$

所以维护一个区间加的tag,按照正常线段树维护即可.

蓝题 牢夸

先从蓝题的YNOI开始刷…但第一题就给我干懵了

题意:给定一个区间,你要支持一个数据结构(1e5):

1. 区间对lr的每个元素都加上x
2. 区间查询子区间的最大平均数(同时限制子区间长度至少为2)

首先考虑不限制子区间长度,那么直接取区间max即可.
现在加上了限制,显然答案就是2区间或者3区间长度,直接用普通的线段树维护即可.

具体地,开两颗线段树分别维护两个元素和三个元素捆绑的区间加,区间max,对于区间修改,由于3的区间会是1233321的修改,一个一个情况维护最多有五种情况,很不优雅.我们考虑覆盖,像做蛋糕一样一层一层对线段树进行修改,如此只需要对两个区间的边界取min和max即可.