带 sin， cos 的线段树

链接：https://www.nowcoder.com/acm/contest/160/D
来源：牛客网

题目描述
给出一个长度为n的整数序列a1,a2,...,an，进行m次操作，操作分为两类。
操作1：给出l,r,v，将al,al+1,...,ar分别加上v；
操作2：给出l,r，询问
输入描述:

第一行一个整数n
接下来一行n个整数表示a1,a2,...,an
接下来一行一个整数m
接下来m行，每行表示一个操作，操作1表示为1 l r v，操作2表示为2 l r
保证1≤n,m,ai,v≤200000；1≤l≤r≤n，v是整数

输出描述:

对每个操作2，输出一行，表示答案，四舍五入保留一位小数
保证答案的绝对值大于0.1，且答案的准确值的小数点后第二位不是4或5
数据随机生成（n,m人工指定，其余整数在数据范围内均匀选取），并去除不满足条件的操作2

输入

4
1 2 3 4
5
2 2 4
1 1 3 1
2 2 4
1 2 4 2
2 1 3

输出

0.3
-1.4
-0.3

题意：给你 n 个数字，第一种操作是将一个区间内每一个数字加上同一个数字，第二种操作是求一个区间内每一个数 sin 的累加和

思路分析：对于每个区间维护一下 cos 和 sin 的值，当一个区间要加上一个数字时，此时再重新计算 sin的值时 , sin(a + x) = sin(a)*cos(x) + cos(a)*sin(x) ，一个区间内的所有值都可以这样计算，因此就会用到区间内的 sin 总和以及 cos 的总和

这个题有个很坑的地方，就是大量的地方用到 sin 与 cos 函数，若输入的是一个整形数强制转变为浮点数后再用 sin函数，cos函数则会超时，不强制转换会快一半的时间！！！

代码示例：

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int maxn = 2e5+5;

#define lson k<<1

#define rson k<<1|1

int n, m;

struct node

{

	int l, r;

	ll lazy;

	double rs, rc;

}t[maxn<<2];

void pushdown(int k){

	double x1 = t[lson].rs*cos(t[k].lazy) + t[lson].rc*sin(t[k].lazy);

	double x2 = t[lson].rc*cos(t[k].lazy) - t[lson].rs*sin(t[k].lazy);

	t[lson].rs = x1, t[lson].rc = x2;

	x1 = t[rson].rs*cos(t[k].lazy) + t[rson].rc*sin(t[k].lazy);

	x2 = t[rson].rc*cos(t[k].lazy) - t[rson].rs*sin(t[k].lazy);

	t[rson].rs = x1, t[rson].rc = x2;

	t[lson].lazy += t[k].lazy;

	t[rson].lazy += t[k].lazy;

	t[k].lazy = 0;

}

int x;

void build(int l, int r, int k){

	t[k].l = l, t[k].r = r;

	t[k].rc = t[k].rs = 0.0;

	t[k].lazy = 0;

	if (l == r) {

		scanf("%d", &x);

		t[k].rs = sin(x), t[k].rc = cos(x);

		return;

	}

	int m = (l+r) >> 1;

	build(l, m, lson);

	build(m+1, r, rson);

	t[k].rs = t[lson].rs+t[rson].rs;

	t[k].rc = t[lson].rc+t[rson].rc;

}

void update(int l, int r, ll v, int k){

	if (l <= t[k].l && t[k].r <= r){

		double x1 = t[k].rs*cos(v)+t[k].rc*sin(v);

		double x2 = t[k].rc*cos(v)-t[k].rs*sin(v);

		t[k].rs = x1, t[k].rc = x2;

		t[k].lazy += v;

		return;

	}

	if (t[k].lazy) pushdown(k);

	int m = (t[k].l+t[k].r) >> 1;

	if (l <= m) update(l, r, v, lson);

	if (r > m) update(l, r, v, rson);

	t[k].rs = t[lson].rs+t[rson].rs;

	t[k].rc = t[lson].rc+t[rson].rc;

}

double sum;

void query(int l, int r, int k){

	if (l <= t[k].l && t[k].r <= r){

		sum += t[k].rs;

		return;

	}

	if (t[k].lazy) pushdown(k);

	int m = (t[k].l + t[k].r) >> 1;

	if (l <= m) query(l, r, lson);

	if (r > m) query(l, r, rson);

}

int main() {

	int pt, l, r;

	ll v;

	cin >> n;

	build(1, n, 1);

	cin >> m;

	while(m--){

		scanf("%d%d%d", &pt, &l, &r);

		if (pt == 1) {

			scanf("%lld", &v);

			update(l, r, v, 1);

		}

		else {

			sum = 0;

			query(l, r, 1);

			printf("%.1lf\n", sum);

		}

	}

	return 0;

}

巴特西

带 sin， cos 的线段树 - 牛客

最新文章

热门文章