样例过了 0pts 线段树求助 qwq
查看原帖
样例过了 0pts 线段树求助 qwq
719978
DYYqwq楼主2024/1/24 15:00

rt

#include<bits/stdc++.h>
#define lson(root) (root << 1)
#define rson(root) (root << 1 | 1)
using namespace std;
struct node
{
	double s , c , lazy;
}tree[800010];
int n , m , a[200010];
void pushup(int root)
{
	tree[root].s = tree[lson(root)].s + tree[rson(root)].s;
	tree[root].c = tree[lson(root)].c + tree[rson(root)].c;
}
void pushdown(int root , int l , int r)
{
	if(tree[root].lazy == 0) return;
	double val = tree[root].lazy , ls = tree[lson(root)].s , lc = tree[lson(root)].c , rs = tree[rson(root)].s , rc = tree[lson(root)].c;
	tree[lson(root)].s = ls * cos(val) + lc * sin(val);
	tree[rson(root)].c = rc * cos(val) - rs * sin(val);
	tree[lson(root)].lazy += val;
	tree[rson(root)].lazy += val;
	tree[root].lazy = 0;
}
void update(int root , int l , int r , int L , int R , int val)
{
	if(L <= l && R >= r)
	{
		double s = tree[root].s , c = tree[root].c;
		tree[root].s = s * cos(val) + c * sin(val);
		tree[root].c = c * cos(val) - s * sin(val);
		tree[root].lazy += 1.0 * val;
		return; 
	}
	int mid = (l + r) >> 1;
	pushdown(root , l , r);
	if(L <= mid) update(lson(root) , l , mid , L , R , val);
	if(R > mid) update(rson(root) , mid + 1 , r , L , R , val);
	pushup(root);
}
double query(int root , int l , int r , int L , int R)
{
	if(L <= l && R >= r) return tree[root].s;
	int mid = (l + r) >> 1;
	double sum = 0;
	pushdown(root , l , r);
	if(L <= mid) sum += query(lson(root) , l , mid , L , R);
	if(R > mid) sum += query(rson(root) , mid + 1 , r , L , R);
	return sum;
}
void build(int root , int l , int r)
{
	if(l == r)
	{
		tree[root].s = sin(a[l]);
		tree[root].c = cos(a[l]);
		return;
	}
	int mid = (l + r) >> 1;
	build(lson(root) , l , mid);
	build(rson(root) , mid + 1 , r);
	pushup(root);
}
int main()
{
	scanf("%d" , &n);
	for(int i = 1 ; i <= n ; i ++) scanf("%d" , &a[i]);
	build(1 , 1 , n);
	scanf("%d" , &m);
	while(m --)
	{
		int op , l , r , k;
		scanf("%d%d%d" , &op , &l , &r);
		if(op == 1)
		{
			scanf("%d" , &k);
			update(1 , 1 , n , l , r , k);
		}
		else printf("%.1lf\n" , query(1 , 1 , n , l , r));
	}
	return 0;
}
2024/1/24 15:00
加载中...