P6327 区间加区间sin和 题解
第一道Ynoi（捂脸
题目描述
给出一个长度为 \(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;
}