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\。
-
down
操作
up
操作
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;
}