【题解】[Luogu5524]Ynoi2012D1T1

此处题面


前言

这应该是最水的 Ynoi 题了吧,不需要很高级的数据结构也不需要什么奇技淫巧,可以当做线段树练手题。


正文

我第一眼看见操作 22 的时候差点吓傻:区间 sin\sin 和!

但是不用慌,维护这种少见的信息有两个比较套路的方法:

  1. 拆分成好维护的信息
  2. 直接维护,考虑修改对其的影响

我开始想的是方法 11 ,十分 naive 地尝试把 sinx\sin x 展开成麦克劳林级数,然后维护区间 kk 次方和,后来发现区间加之后精度会很惨烈…

于是使用方法 22 ,考虑加法对这个东西的影响,由和角公式:

sin(x+v)=sinxcosv+cosxsinv\sin(x+v)=\sin x\cos v+\cos x\sin v

cos(x+v)=cosxcosvsinxsinv\cos(x+v)=\cos x\cos v-\sin x\sin v

然后就非常好做了,我们同时维护区间 sin\sin 和跟区间 cos\cos 和,上传信息可以直接相加,再维护一个加法标记,用上面的和角公式可以做到 Θ(1)\Theta(1) 下传标记。

1
2
3
4
5
6
7
inline void add(int id,i64 v) {
double x=sinv[id],y=cosv[id];
double p=sin(v),q=cos(v);
sinv[id]=x*q+y*p;
cosv[id]=y*q-x*p;
addv[id]+=v;
}

其它的就是线段树模板了,然后你就能通过这道题。

如果你的常数过大可以考虑减少求 sin\sincos\cos 的次数,可以大幅减小常数。


最后

Ynoi 题就不贴代码了,反正这个题代码也好写。

另外这个题可以考虑对于原序列的 xx 维护 eixe^{ix} ,这样每次修改只需要维护乘法标记即可。

由欧拉公式,查询时可以直接提取虚部,这种方法常数会小些。