P6327 区间加区间sin和 题解

科技资讯 投稿 5500 0 评论

P6327 区间加区间sin和 题解

P6327 区间加区间sin和 题解

题目描述

\(n\ 的整数序列 \(a_1,a_2,\ldots,a_n\,进行 \(m\ 次操作,操作分为两类。

\(1\:给出 \(l,r,v\,将 \(a_l,a_{l+1},\ldots,a_r\ 分别加上 \(v\

\(2\:给出 \(l,r\,询问 \(\sum\limits_{i=l}^{r}\sin(a_i\

想法

对于一个节点 \([l, r]\ 它维护的应该是 \(\sin a_l + \sin a_{l + 1} +\dots+\sin a_r\

    up 操作
  1. down 操作

up

很明显,对于这道题而言,可以直接把左右儿子维护的 \(\sin\ 和加起来。

inline void up(int k
{
    tr[k].sin = tr[k << 1].sin + tr[k << 1 | 1].sin;
    tr[k].cos = tr[k << 1].cos + tr[k << 1 | 1].cos;
}

down

和角公式:

\[\sin (\alpha +\beta = \sin \alpha \cos \beta + \sin \beta \cos \alpha\\ \cos(\alpha + \beta = \cos\alpha\cos\beta-\sin\alpha\sin\beta \]

\(\cos\ 和。

inline void add(int k, double sinv, double cosv
{
    double sal = tr[k].sin, cal = tr[k].cos; // 注意要先备份一套sin和cos,调了好久Q^Q
    tr[k].sin = sal * cosv + cal * sinv; // 更新区间sin和
    tr[k].cos = cal * cosv - sal * sinv; // 更新区间cos和
}

inline void down(int k
{
    int v = tr[k].tag;
    double sinv = sin(v, cosv = cos(v;
    add(k << 1, sinv, cosv;
    add(k << 1 | 1, sinv, cosv;
    tr[k << 1].tag += tr[k].tag, tr[k << 1 | 1].tag += tr[k].tag;
    tr[k].tag = 0;
}

实现

剩下板

// Problem: P6327 区间加区间sin和
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P6327
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Author: Moyou
// Copyright (c 2022 Moyou All rights reserved.
// Date: 2023-01-31 15:25:03

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#define x first
#define y second
#define speedup (ios::sync_with_stdio(0, cin.tie(0, cout.tie(0
#define INF 0x3f3f3f3f
#define int long long
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int N = 2e5 + 10;

int n, m;
int a[N];

inline char get_char(
{
    static char buf[1000000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf + fread(buf, 1, 1000000, stdin, p1 == p2 ? EOF : *p1++;
}

inline int read(
{
    int x = 0;
    char ch = get_char(;
    while (ch < '0' || ch > '9'
        ch = get_char(;
    while (ch <= '9' && ch >= '0'
        x = (x << 1 + (x << 3 + (ch ^ 48, ch = get_char(;
    return x;
}

double sinv, cosv;

struct owo
{
    int l, r;
    double sin, cos;
    int tag;
} tr[N << 2];

inline void up(int k
{
    tr[k].sin = tr[k << 1].sin + tr[k << 1 | 1].sin;
    tr[k].cos = tr[k << 1].cos + tr[k << 1 | 1].cos;
}

inline void add(int k, double sinv, double cosv
{
    double sal = tr[k].sin, cal = tr[k].cos; // 注意要先备份一套sin和cos,调了好久Q^Q
    tr[k].sin = sal * cosv + cal * sinv; // 更新区间sin和
    tr[k].cos = cal * cosv - sal * sinv; // 更新区间cos和
}

inline void down(int k
{
    int v = tr[k].tag;
    double sinv = sin(v, cosv = cos(v;
    add(k << 1, sinv, cosv;
    add(k << 1 | 1, sinv, cosv;
    tr[k << 1].tag += tr[k].tag, tr[k << 1 | 1].tag += tr[k].tag;
    tr[k].tag = 0;
}

void build(int k, int l, int r
{
    tr[k] = {l, r, 0, 0};
    if (l == r
        tr[k] = {l, r, sin(a[l], cos(a[l], 0};
    else
    {
        int mid = l + r >> 1;
        build(k << 1, l, mid;
        build(k << 1 | 1, mid + 1, r;
        up(k;
    }
}

void update(int k, int ql, int qr, int v
{
    int l = tr[k].l, r = tr[k].r, mid = l + r >> 1;
    if (ql <= l && qr >= r // 查询区间包含当前区间
    {
        add(k, sinv, cosv; // 更新
        tr[k].tag += v; // 打懒标记
        return;
    }
    if (tr[k].tag
        down(k;
    if(ql <= mid update(k << 1, ql, qr, v;
    if(qr > mid  update(k << 1 | 1, ql, qr, v;
    up(k;
}

double query(int k, int ql, int qr
{
    int l = tr[k].l, r = tr[k].r, mid = l + r >> 1;
    if(ql <= l && qr >= r
        return tr[k].sin;
    if(tr[k].tag down(k;
    double tmp = 0;
    if(ql <= mid tmp += query(k << 1, ql, qr;
    if(qr > mid tmp += query(k << 1 | 1, ql, qr;
    return tmp;
}

signed main(
{
    n = read(;
    for (int i = 1; i <= n; i++
        a[i] = read(;
    m = read(;
    build(1, 1, n;
    while (m--
    {
        int op = read(, l = read(, r = read(;
        if (--op
            printf("%.1lf\n", query(1, l, r;
        else
        {
            int v = read(;
            sinv = sin(v, cosv = cos(v;
            update(1, l, r, v;
        }
    }
    return 0;
}

编程笔记 » P6327 区间加区间sin和 题解

赞同 (21) or 分享 (0)
游客 发表我的评论   换个身份
取消评论

表情
(0)个小伙伴在吐槽