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 操作
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和题解

P6327 区间加区间sin和题解

题目描述

想法

`up`

`down`

实现

最新文章

热门文章

巴特西

P6327 区间加区间sin和 题解

P6327 区间加区间sin和 题解

题目描述

想法

up

down

实现

最新文章

热门文章

P6327 区间加区间sin和题解

P6327 区间加区间sin和题解

`up`

`down`