Problem
维护一个序列\(a\)，每次操作有两种类型：
-
1 l r v将\(a_l \sim a_r\)的所有数加\(v\)。 -
2 l r求\(\sum_{i = l} ^ r \sin (a_i)\)。
输入数据均小于\(2 \times 10^5\)。
Solution
上午刚做完一个Ynoi，以为是最简单的Ynoi题了，结果这题更是重量级。
不难发现通过两个诱导公式可以做：
\[\sin(\alpha + \beta) = \sin(\alpha) \cos(\beta) + \sin(\beta)\cos(\alpha)\\cos(\alpha + \beta) = \cos(\alpha) \cos(\beta) - \sin(\alpha) \sin(\beta)
\]
然后用线段树，节点维护sin,cos和即可。
# include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n;
double a[N];
int m;
struct node
{
double Sin,Cos,lazy;
}T[N << 2];
void pushup(int root)
{
T[root].Sin = T[root << 1].Sin + T[root << 1 | 1].Sin;
T[root].Cos = T[root << 1].Cos + T[root << 1 | 1].Cos;
return;
}
void build(int root,int l,int r)
{
if(l == r)
{
T[root].Sin = sin(a[l]),T[root].Cos = cos(a[l]);
T[root].lazy = 0;
return;
}
int mid = (l + r) >> 1;
build(root << 1,l,mid),build(root << 1 | 1, mid + 1, r);
pushup(root);
return;
}
void pushdown(int root)
{
if(T[root].lazy == 0) return;
double tag = T[root].lazy;
double sine = sin(tag),cosine = cos(tag);
double sn = T[root << 1].Sin,cs = T[root << 1].Cos;
T[root << 1].Sin = sn * cosine + sine * cs;
T[root << 1].Cos = cosine * cs - sine * sn;
sn = T[root << 1 | 1].Sin,cs = T[root << 1 | 1].Cos;
T[root << 1 | 1].Sin = sn * cosine + sine * cs;
T[root << 1 | 1].Cos = cosine * cs - sine * sn;
T[root << 1].lazy += tag,T[root << 1 | 1].lazy += tag;
T[root].lazy = 0;
return;
}
void update(int root,int l,int r,int s,int t,double d)
{
if(l <= s && t <= r)
{
double sine = sin(d),cosine = cos(d);
double sn = T[root].Sin,cs = T[root].Cos;
T[root].Sin = sn * cosine + sine * cs;
T[root].Cos = cosine * cs - sine * sn;
T[root].lazy += d;
return;
}
pushdown(root);
int mid = (s + t) >> 1;
if(l <= mid) update(root << 1,l,r,s,mid,d);
if(r > mid) update(root << 1 | 1,l,r,mid + 1,t,d);
pushup(root);
return;
}
double query(int root,int l,int r,int s,int t)
{
if(l <= s && t <= r) return T[root].Sin;
pushdown(root);
int mid = (s + t) >> 1;
double ans = 0;
if(l <= mid) ans = ans + query(root << 1,l,r,s,mid);
if(r > mid) ans = ans + query(root << 1 | 1,l,r,mid + 1,t);
return ans;
}
int main(void)
{
scanf("%d",&n);
for(int i = 1; i <= n; i++) scanf("%lf",&a[i]);
build(1,1,n);
scanf("%d",&m);
while(m--)
{
int opt,l,r;
scanf("%d%d%d",&opt,&l,&r);
if(opt == 1)
{
double v; scanf("%lf",&v);
update(1,l,r,1,n,v);
}
else
{
printf("%.1lf\n",query(1,l,r,1,n));
}
}
return 0;
}