蒟蒻刚学线段树,样例全过WA0,求助
查看原帖
蒟蒻刚学线段树,样例全过WA0,求助
533854
CodingShark楼主2022/9/14 22:02
#include <bits/stdc++.h>
using namespace std;
struct node
{
    int l, r;
    long long tag;
    double SIN, COS;
} t[1000005];
int n, q, opt, l, r, v, a[200005];

void add(int idx, long long val)
{
    t[idx].SIN = t[idx].SIN * cos(val) + t[idx].COS * sin(val);
    t[idx].COS = t[idx].COS * cos(val) - t[idx].SIN * sin(val);
    t[idx].tag += val;
}

void pushup(int idx)
{
    t[idx].SIN = t[idx << 1].SIN + t[idx << 1 | 1].SIN;
    t[idx].COS = t[idx << 1].COS + t[idx << 1 | 1].COS;
}

void pushdown(int idx)
{
    if (t[idx].tag)
    {
        add(idx << 1, t[idx].tag);
        add(idx << 1 | 1, t[idx].tag);
        t[idx].tag = 0;
    }
}

void build(int idx, int l, int r)
{
    t[idx].l = l, t[idx].r = r;
    if (l == r)
    {
        t[idx].SIN = sin(a[l]);
        t[idx].COS = cos(a[l]);
        return;
    }
    int mid = l + r >> 1;
    build(idx << 1, l, mid);
    build(idx << 1 | 1, mid + 1, r);
    pushup(idx);
}

void update(int idx, int l, int r, long long val)
{
    if (l <= t[idx].l && t[idx].r <= r)
    {
        add(idx, val);
        return;
    }
    pushdown(idx);
    int mid = t[idx].l + t[idx].r >> 1;
    if (l <= mid)
        update(idx << 1, l, r, val);
    if (r > mid)
        update(idx << 1 | 1, l, r, val);
    pushup(idx);
}

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

int main()
{
#ifndef ONLINE_JUDGE
    freopen("data.in", "r", stdin);
    // freopen("data.out", "w", stdout);
#endif
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", a + i);
    build(1, 1, n);
    scanf("%d", &q);
    while (q--)
    {
        scanf("%d %d %d", &opt, &l, &r);
        if (opt & 1)
        {
            scanf("%d", &v);
            update(1, l, r, v);
        }
        else
            printf("%.1lf\n", query(1, l, r));
    }
    return 0;
}
2022/9/14 22:02
加载中...