Blog of RuSun

\begin {array}{c} \mathfrak {One Problem Is Difficult} \\\\ \mathfrak {Because You Don't Know} \\\\ \mathfrak {Why It Is Diffucult} \end {array}

P6327 区间加区间sin和

发表于 分类于
本文字数： 3.1k 阅读时长 ≈ 3 分钟
标签：        

P6327 区间加区间sin和

三角函数公式：
$$
\sin(x + \alpha) = \sin(x) \cos(\alpha) + \cos(x)\sin(\alpha) \\
\cos(x + \alpha) = \cos(x) \cos(\alpha) - \sin(x)\sin(\alpha)
$$
对于两个数同时加：
$$
\begin{aligned}
\sin(x + \alpha) + \sin(y +\alpha) &= \sin(x) \cos(\alpha) + \cos(x)\sin(\alpha) + \sin(y) \cos(\alpha) + \cos(y)\sin(\alpha) \\
&= \cos(\alpha)(\sin(x) + \sin(y)) + \sin(\alpha)(\cos(x)+\cos(y))\\
\cos(x + \alpha) + \cos(y + \alpha) &= \cos(x) \cos(\alpha) - \sin(x)\sin(\alpha) + \cos(y) \cos(\alpha) - \sin(y)\sin(\alpha)\\
&= \cos(\alpha)(\cos(x) + \cos(y)) - \sin(\alpha)(\sin(x) + \sin(y))
\end{aligned}
$$
根据数学归纳法，任意长度区间都可以这样做，只需要维护区间 $\sin$ 和 $\cos$ 和即可。

查看代码 
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
88
89
90
91
92
93
94
95
96
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int n, m, w[N];
struct Node
{
    int l, r;
    LL tag;
    double c, s;
} tr[N << 2];
void pushup(Node &x, Node l, Node r)
{
    x.c = l.c + r.c;
    x.s = l.s + r.s;
}
void cal(int x, LL k)
{
    double c = tr[x].c, s = tr[x].s;
    tr[x].c = c * cos(k) - s * sin(k);
    tr[x].s = s * cos(k) + c * sin(k);
    tr[x].tag += k;
}
void pushdown(int x)
{
    cal(x << 1, tr[x].tag);
    cal(x << 1 | 1, tr[x].tag);
    tr[x].tag = 0;
}
void build(int x, int l, int r)
{
    tr[x].l = l, tr[x].r = r;
    if (l == r)
    {
        tr[x].c = cos(w[l]);
        tr[x].s = sin(w[l]);
        return;
    }
    int mid = l + r >> 1;
    build(x << 1, l, mid);
    build(x << 1 | 1, mid + 1, r);
    pushup(tr[x], tr[x << 1], tr[x << 1 | 1]);
}
void modify(int x, int l, int r, int k)
{
    if (tr[x].l >= l && tr[x].r <= r)
    {
        cal(x, k);
        return;
    }
    if (tr[x].tag)
        pushdown(x);
    int mid = tr[x].l + tr[x].r >> 1;
    if (l <= mid)
        modify(x << 1, l, r, k);
    if (r > mid)
        modify(x << 1 | 1, l, r, k);
    pushup(tr[x], tr[x << 1], tr[x << 1 | 1]);
}
Node query(int x, int l, int r)
{
    if (tr[x].l >= l && tr[x].r <= r)
        return tr[x];
    if (tr[x].tag)
        pushdown(x);
    int mid = tr[x].l + tr[x].r >> 1;
    if (r <= mid)
        return query(x << 1, l, r);
    if (l > mid)
        return query(x << 1 | 1, l, r);
    Node res;
    pushup(res, query(x << 1, l, r), query(x << 1 | 1, l, r));
    return res;
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &w[i]);
    build(1, 1, n);
    scanf("%d", &m);
    for (int op, l, r; m; m--)
    {
        scanf("%d%d%d", &op, &l, &r);
        if (op == 1)
        {
            int k;
            scanf("%d", &k);
            modify(1, l, r, k);
        }
        else
            printf("%.1lf\n", query(1, l, r).s);
    }
    return 0;
}
相关文章