数据结构-线段树-double

59 阅读 0 评论 39 点赞

我是靠谱客的博主迅速含羞草，最近开发中收集的这篇文章主要介绍数据结构-线段树-double，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

注意lazy的下放

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
#define File(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
#define push(a) ans1=tree[(a)].sin,ans2=tree[(a)].cos,tree[(a)].sin=ans4*ans1+ans3*ans2,tree[(a)].cos=ans4*ans2-ans3*ans1,tree[(a)].lazy+=K
#define limit 0.0000000000001
#define mid ((l+r)>>1)
#define ls (x<<1)
#define rs (x<<1|1)
#define MAXN 100001
struct node {
	double sin,cos,lazy;
} tree[MAXN*4];
double a[MAXN];
int n,q;

inline void pushdown(int x) {
	double K=tree[x].lazy;
	if(-limit>K||limit<K) {
		double ans1,ans2,ans3=sin(K),ans4=cos(K);
		push(ls),push(rs),tree[x].lazy=0;
	}
}

inline void pushup(int x) {
	tree[x].sin=tree[ls].sin+tree[rs].sin;
	tree[x].cos=tree[ls].cos+tree[rs].cos;
}

inline void build(int x,int l,int r) {
	if(l==r)tree[x].sin=sin(a[l]),tree[x].cos=cos(a[l]);
	else {
		build(ls,l,mid);
		build(rs,mid+1,r);
		pushup(x);
	}
}

inline void updata(int x,int l,int r,int L,int R,double K) {
	double ans1,ans2,ans3,ans4;
	if(L<=l&&r<=R)ans3=sin(K),ans4=cos(K),push(x);
	else {
		pushdown(x);
		if(R<=mid)updata(ls,l,mid,L,R,K);
		else if(L> mid)updata(rs,mid+1,r,L,R,K);
		else updata(ls,l,mid,L,mid,K),updata(rs,mid+1,r,mid+1,R,K);
		pushup(x);
	}
}

inline double query(int x,int l,int r,int L,int R) {
	if(L<=l&&r<=R)return tree[x].sin;
	else {
		pushdown(x);
		double ans=0;
		if(R<=mid)ans=query(ls, l ,mid,L,R);
		else if(L> mid)ans=query(rs,mid+1,r,L,R);
		else ans=query(ls,l,mid,L,mid)+query(rs,mid+1,r,mid+1,R);
		return ans;
	}
}

int main() {
	File("sine");
	scanf("%d%d",&n,&q);
	for(int i=1; i<=n; i++)scanf("%lf",&a[i]);
	build(1,1,n);
	for(int i=1; i<=q; i++) {
		int type,L,R;
		scanf("%d%d%d",&type,&L,&R);
		if(type==0)printf("%0.2lfn",query(1,1,n,L,R));
		else {
			double K;
			scanf("%lf",&K);
			updata(1,1,n,L,R,K);
		}
	}
	return 0;
}