Description

题目链接

题目大意：如题所示。

Solution

第一眼有点吓人，毕竟维护区间 $\sin$ 和是第一次见。然后我想的是由于输入都是整数而三角函数以 $2 \pi$ 作为周期，能不能暴力预处理。

后来发现用公式 $\sin(x + y) = \sin x \cos y + \cos x \sin y$ 就能解决问题了，用线段树维护 $\sin$ 和 $\cos$。容易验证这个对非叶子节点也成立。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

template <class T>
inline void read(T &x) {
    x = 0;
    int f = 0;
    char ch = getchar();
    while (!isdigit(ch))    { f |= ch == '-'; ch = getchar(); }
    while (isdigit(ch))     { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    x = f ? -x : x;
    return ;
}

typedef unsigned long long uLL;
typedef long long LL;

struct Node {
    int l, r;
    double s1, s2;
    LL tag;
} t[800010];

int n, m, tp, tmp;

inline int lson(int x) { return x << 1; }
inline int rson(int x) { return x << 1 | 1; }

void buildTree(int x, int l, int r) {
    t[x].l = l, t[x].r = r;
    if (l == r) {
        read(tmp);
        t[x].s1 = sin(tmp), t[x].s2 = cos(tmp);
        return ;
    }
    int mid = (l + r) >> 1;
    buildTree(lson(x), l, mid), buildTree(rson(x), mid + 1, r);
    t[x].s1 = t[lson(x)].s1 + t[rson(x)].s1, t[x].s2 = t[lson(x)].s2 + t[rson(x)].s2;
}

void update(int x, double sinx, double cosx) {
    double siny = t[x].s1, cosy = t[x].s2;
    t[x].s1 = sinx * cosy + cosx * siny;
    t[x].s2 = cosx * cosy - sinx * siny;
}

void pushDown(int x) {
    if (t[x].tag) {
        double sinx = sin(t[x].tag), cosx = cos(t[x].tag);
        update(lson(x), sinx, cosx), update(rson(x), sinx, cosx);
        t[lson(x)].tag += t[x].tag, t[rson(x)].tag += t[x].tag;
        t[x].tag = 0;
    }
}

double query(int x, int l, int r) {
    if (l <= t[x].l && t[x].r <= r)    return t[x].s1;
    double s = 0;
    pushDown(x);
    int mid = (t[x].l + t[x].r) >> 1;
    if (l <= mid)    s += query(lson(x), l, r);
    if (r > mid)     s += query(rson(x), l, r);
    return s;
}

void modify(int x, int l, int r, LL k) {
    if (l <= t[x].l && t[x].r <= r) {
        t[x].tag += k;
        update(x, sin(k), cos(k));
        return ;
    }
    pushDown(x);
    int mid = (t[x].l + t[x].r) >> 1;
    if (l <= mid)    modify(lson(x), l, r, k);
    if (r > mid)     modify(rson(x), l, r, k);
    t[x].s1 = t[lson(x)].s1 + t[rson(x)].s1, t[x].s2 = t[lson(x)].s2 + t[rson(x)].s2;
}

int main() {
    read(n);
    buildTree(1, 1, n);
    read(m);
    while (m--) {
        int l, r, v;
        read(tp);
        if (tp == 1) {
            read(l), read(r), read(v);
            modify(1, l, r, v);
        } else {
            read(l), read(r);
            printf("%.1lf\n", query(1, l, r));
        }
    }
    return 0;
}