Luogu6327 区间加区间sin和

发布于 10 天前  29 次阅读


Link

前置知识

这个题还是要先学会和角公式(有的什么毒瘤复数的做法太无聊了)

\sin(\alpha + \beta) = \sin(\alpha)\cos(\beta) + \cos(\alpha)\sin(\beta)

\cos(\alpha + \beta) = \cos(\alpha)\cos(\beta) - \sin(\alpha)\sin(\beta)

Sol

有了上面的公式,你应该就会做这个题了.

加入现在要给 [l,r] 内的所有角加上一个 \alpha

那么

\sum_{i=l}^{r} \sin(a_i + \alpha) = \sum_{i=l}^{r} \sin(a_i) \times \cos(\alpha) + \sum_{i= l}^{r} \cos(a_i) \times \sin(\alpha)

那么需要维护区间 \sin\cos 的和

\sum_{i=l}^{r} \cos(a_i + \alpha) = \sum_{i=l}^{r} \cos(a_i) \times \cos(\alpha) - \sum_{i= l}^{r} \sin(a_i) \times \sin(\alpha)

也许到这里你就会了.

还要注意的地方是,每次更新 \sin\cos 的时候要先记录一下没更新前的值,再更新.如果你这么做的话

tree[lson(p)].sine = cos(tree[p].tag) * tree[lson(p)].sine + sin(tree[p].tag) * tree[lson(p)].cosine;

tree[lson(p)].cosine = tree[lson(p)].cosine * cos(tree[p].tag) - tree[lson(p)].sine * sin(tree[p].tag);

就会跟我一样sb

还有要开long long

Code

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int SIZE = 3e5 + 5;

int n, q;
int a[SIZE];

struct node {
    int l, r, tag;
    double cosine, sine;
} tree[SIZE << 2];

namespace ae86 {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (!isdigit(c))b ^= c == '-', c = fetch();
        while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
        return b ? a : -a;
    }
}
using ae86::read;

#define lson(p) p << 1
#define rson(p) p << 1 | 1

inline void pushUp(int p)
{
    tree[p].cosine = tree[lson(p)].cosine + tree[rson(p)].cosine;
    tree[p].sine = tree[lson(p)].sine + tree[rson(p)].sine;
}

inline void pushDown(int p)
{
    if (tree[p].tag != 0.00) {
        double lsine = tree[lson(p)].sine, rsine = tree[rson(p)].sine;
        double lcos = tree[lson(p)].cosine, rcos = tree[rson(p)].cosine;
        tree[lson(p)].sine = cos(tree[p].tag) * lsine + sin(tree[p].tag) * lcos;
        tree[lson(p)].cosine = lcos * cos(tree[p].tag) - lsine * sin(tree[p].tag);
        tree[rson(p)].sine = cos(tree[p].tag) * rsine + sin(tree[p].tag) * rcos;
        tree[rson(p)].cosine = rcos * cos(tree[p].tag) - rsine * sin(tree[p].tag);
        tree[lson(p)].tag += tree[p].tag, tree[rson(p)].tag += tree[p].tag, tree[p].tag = 0;
    }
}

inline void build(int p, int l, int r)
{
    tree[p].l = l, tree[p].r = r;
    if (l == r) {
        tree[p].cosine = cos(a[l]), tree[p].sine = sin(a[l]);
        return;
    }
    int mid = (l + r) >> 1;
    build(lson(p), l, mid); build(rson(p), mid + 1, r);
    pushUp(p);
}

inline void modify(int p, int l, int r, int v)
{
    if (l <= tree[p].l && tree[p].r <= r) {
        double si = tree[p].sine, co = tree[p].cosine;
        tree[p].sine = cos(v) * si + sin(v) * co;
        tree[p].cosine = co * cos(v) - si * sin(v);
        tree[p].tag += v;
        return;
    }
    pushDown(p);
    int mid = (tree[p].l + tree[p].r) >> 1;
    if (l <= mid) modify(lson(p), l, r, v); 
    if (r > mid) modify(rson(p), l, r, v);
    pushUp(p);
}

inline double query(int p, int l, int r)
{
    if (l <= tree[p].l && tree[p].r <= r) {
        return tree[p].sine;
    }
    pushDown(p);
    int mid = (tree[p].l + tree[p].r) >> 1; double ans = 0.00;
    if (l <= mid) ans += query(lson(p), l, r);
    if (r > mid) ans += query(rson(p), l, r);
    return ans;
}   

signed main()
{
    n = read();
    for (int i = 1; i <= n; ++ i) {
        a[i] = read();
    }
    build(1, 1, n);
    q = read();
    int opt, l, r, v;
    while (q --) {
        opt = read();
        if (opt == 1) {
            l = read(), r = read(), v = read();
            modify(1, l, r, v);
        }
        if (opt == 2) {    
            l = read(), r = read();
            printf("%.1lf\n", query(1, l, r));
        }
    }
    return 0;
}

朴实沉毅