Description：

给定长度为 $n$ 的实数序列 $a_i(1 \le i \le n)$ 你需要在数列上进行两类操作：

1. $\forall i \in [l,r],a_i \leftarrow a_i + c$ 2. 求 $\sum\limits_{i=l}^{r}\text{cos}(a_i)$

$n \leqslant 10^5$

Solution：

假设当前处理的区间是 $[l,r]$ , 有一个集体加 $c$ 的标记, 假设我们知道了答案 $x=\sum\limits_{i=l}^{r}\cos(a_i)$ , 现在我们要将所有的 $a_i$ 变成 $a_i+c$ ，即

$$ x'=\sum_{i=l}^{r}\cos(a_i+c)=\sum_{i=l}^{r}\cos(a_i) \cdot \cos(c) - \sin(a_i) \cdot \sin(c) $ $

分离一下之后

$$ x'=\cos(c) \cdot (\sum_{i=l}^{r}\cos(a_i)) - \sin(c) \cdot (\sum_{i=l}^{r}\sin(a_i)) $ $

那么可以发现只要再维护一下 $\sum\limits_{i=l}^{r}\sin(a_i)$ 就好了

设 $y=\sum\limits_{i=l}^{r}\sin(a_i)$ ，那么可以得到

$$ y'=\sum_{i=l}^{r}\sin(a_i+c)=\sum_{i=l}^{r}\sin(a_i) \cdot \cos(c)+\cos(a_i) \cdot \sin(c) $ $

也就是说

$$ y'=\cos(c) \cdot y + \sin(c) \cdot x $ $

整理一下就是

$$ x'=\cos(c) \cdot x - \sin(c) \cdot y $ $

$$ y' = \cos(c) \cdot y + \sin(c) \cdot x $ $

之后线段树随便更新标记就行了

Code：

没有代码