整数序列

思路(线段树)

利用线段树维护两个区间和，$\sum sin(a_i)\backslash sum\; sin(a\_i)$和$\sum cos(a_i)\backslash sum\; cos(a\_i)$，因为区间修改操作中$\sum sin(a_i+d)=cos(d)\ast \sum sin(a_i)+sin(d)\ast \sum cos(a_i)\backslash sum\; sin(a\_i+d)\; =\; cos(d)*\backslash sum\; sin(a\_i)+sin(d)*\backslash sum\; cos(a\_i)$需要用到$\sum cos(a_i)\backslash sum\; cos(a\_i)$的值

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
const double eps = 1e-6;
const int N = 2e5 + 10;
int n, m;
int a[N];
struct Node
{
    int l, r;
    double ssum, csum;
    LL add;
} tr[4 * N];

void pushup(int u)
{
    tr[u].csum = tr[u << 1].csum + tr[u << 1 | 1].csum;
    tr[u].ssum = tr[u << 1].ssum + tr[u << 1 | 1].ssum;
}

void eval(Node &u, LL add)
{
    double csum = u.csum, ssum = u.ssum;
    double cosadd = cos(add), sinadd = sin(add);
    u.ssum = cosadd * ssum + sinadd * csum;
    u.csum = cosadd * csum - sinadd * ssum;
    u.add += add;
}

void pushdown(int u)
{
    auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
    if (root.add)
    {
        eval(left, root.add);
        eval(right, root.add);
        root.add = 0;
    }
}

void build(int u, int l, int r)
{
    tr[u].l = l, tr[u].r = r;

    if (l == r)
    {
        tr[u].csum = cos(a[l]);
        tr[u].ssum = sin(a[l]);
        return;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void modify(int u, int l, int r, int v)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        eval(tr[u], v);
        return;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid)
        modify(u << 1, l, r, v);
    if (r > mid)
        modify(u << 1 | 1, l, r, v);
    pushup(u);
}

double query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        return tr[u].ssum;
    }
    pushdown(u);
    double res = 0;
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid)
        res += query(u << 1, l, r);
    if (r > mid)
        res += query(u << 1 | 1, l, r);
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> a[i];
    }
    build(1, 1, n);
    cin >> m;
    while (m--)
    {
        int op, l, r, v;
        cin >> op >> l >> r;
        if (op == 1)
        {
            cin >> v;
            modify(1, l, r, v);
        }
        else
        {
            cout << fixed << setprecision(1) << query(1, l, r) << '\n';
        }
    }
    return 0;
}