线段树全Wa
查看原帖
线段树全Wa
97737
Wsyflying2022楼主2022/1/18 22:55
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int n,m;
double a[maxn];
struct Segment_Tree{
	int l,r;
	double s,c,add;
	#define l(x) t[x].l
	#define r(x) t[x].r
	#define s(x) t[x].s
	#define c(x) t[x].c
	#define add(x) t[x].add 
} t[maxn*4]; 
void pushup(int p){
	s(p)=s(p<<1)+s(p<<1|1);
	c(p)=c(p<<1)+c(p<<1|1);
}
void build_tree(int p,int l,int r){
	l(p)=l,r(p)=r;
	if (l==r){
		s(p)=sin(a[l]);
		c(p)=cos(a[l]);
		return ;
	}
	int mid=(l+r)>>1;
	build_tree(p<<1,l,mid);
	build_tree(p<<1|1,mid+1,r);
	pushup(p);
}
void spread(int p){
	double k=add(p);
	if (!k) return ;
	s(p<<1)=s(p<<1)*cos(k)+c(p<<1)*sin(k);
	s(p<<1|1)=s(p<<1|1)*cos(k)+c(p<<1|1)*sin(k);
	c(p<<1)=c(p<<1)*cos(k)-s(p<<1)*sin(k);
	c(p<<1|1)=c(p<<1|1)*cos(k)-s(p<<1|1)*sin(k);
	add(p<<1)+=k,add(p<<1|1)+=k;
	add(p)=0;
}
void modify(int p,int l,int r,double d){
	if (l(p)>=l && r(p)<=r){
		s(p)=s(p)*cos(d)+c(p)*sin(d);
		c(p)=c(p)*cos(d)-s(p)*sin(d);
		add(p)+=d;
		return ;
	}
	spread(p);
	int mid=(l(p)+r(p))>>1;
	if (l<=mid) modify(p<<1,l,r,d);
	if (r>mid) modify(p<<1|1,l,r,d);
	pushup(p);
}
double query(int p,int l,int r){
	if (l(p)>=l && r(p)<=r){
		return s(p);
	}
	spread(p);
	double ret=0;
	int mid=(l(p)+r(p))>>1;
	if (l<=mid) ret+=query(p<<1,l,r);
	if (r>mid) ret+=query(p<<1|1,l,r);
	return ret;
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	  scanf("%lf",&a[i]);
	build_tree(1,1,n);
	scanf("%d",&m);
	for (int i=1;i<=m;i++){
		int opt,x,y;
		scanf("%d%d%d",&opt,&x,&y);
		switch (opt){
			case 1:
				double k;
				scanf("%lf",&k);
				modify(1,x,y,k);
				break;
			case 2:
				printf("%.1f\n",query(1,x,y));
				break;
		}
	}
	return 0;
}

2022/1/18 22:55
加载中...