P6327 区间加区间sin和
luogu: P6372
区间加区间sin和 线段树上只维护\(sin\)和是很难更新的，想到和角公式，维护\(cos\)的和。 \[sin(x+y)=sin(x)*cos(y)+cos(x)*sin(y)\]
\[cos(x+y)=cos(x)*cos(y)-sin(x)*sin(y)\]
这道题卡常，所以要尽量减少\(sin\)和\(cos\)的运算。
注意一下懒标记用\(long
long\)存就可以了。
时间复杂度\(O((n+m)log n)\)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87#include<cstdio>
#include<cmathjax>
using namespace std;
#define lson (p << 1)
#define rson ((p << 1) | 1)
#define mid ((l + r) >> 1)
const int N = 5e5 + 10;
int n, m;
long long tag[N << 2];
double sinx, cosx, b[N], a[N], Sin[N << 2], Cos[N << 2];
int read() {
int w = 0;
char ch = getchar();
while(ch > '9' || ch < '0') ch = getchar();
while(ch <= '9' && ch >= '0') {
w = w * 10 + ch - 48;
ch = getchar();
}
return w;
}
void build(int l,int r,int p) {
if(l == r) {
Sin[p] = a[l];
Cos[p] = b[l];
return;
}
build(l, mid, lson);
build(mid + 1, r, rson);
Sin[p] = Sin[rson] + Sin[lson];
Cos[p] = Cos[rson] + Cos[lson];
}
void add(int p, long long v, double sv, double cv) {
double Sumsin = Sin[p];
Sin[p] = Sin[p] * cv + Cos[p] * sv;
Cos[p] = Cos[p] * cv - Sumsin * sv;
tag[p] += v;
}
void pushdown(int p) {
if(tag[p] != 0) {
add(lson, tag[p], sin(tag[p]), cos(tag[p]));
add(rson, tag[p], sin(tag[p]), cos(tag[p]));
tag[p] = 0;
}
}
void modify(int p, int l, int r, int L, int R, long long v) {
if(l > R || r < L) return;
if(l >= L && R >= r) {
add(p, v, sinx, cosx);
return;
}
pushdown(p);
modify(lson, l, mid, L, R, v);
modify(rson, mid + 1, r, L, R, v);
Sin[p] = Sin[lson] + Sin[rson];
Cos[p] = Cos[lson] + Cos[rson];
}
double query(int p, int l, int r, int L, int R) {
if(l > R || r < L) return 0.0;
if(l >= L && R >= r) return Sin[p];
pushdown(p);
return query(lson, l, mid, L, R) + query(rson, mid + 1, r, L, R);
}
int main() {
n = read();
for(int i = 1; i <= n; i++) {
int x = read();
a[i] = sin(x), b[i] = cos(x);
}
build(1, n, 1);
m=read();
while(m--) {
int opt, l, r, v;
opt = read();
if(opt == 1) {
l = read(); r = read(); v = read();
sinx=sin(v),cosx=cos(v);
modify(1, 1, n, l, r, (long long)(v));
} else {
l = read(); r = read();
printf("%.1lf\n",query(1, 1, n, l, r));
}
}
return 0;
}