求调线段树
查看原帖
求调线段树
921177
liuhaoyan0323楼主2024/5/25 17:05
#include<bits/stdc++.h>
#define lc x<<1
#define rc x<<1|1
#define int long long
#define N 200005
using namespace std;
typedef struct TreeNode{
	int l,r,add;
	double sin_sum,cos_sum;
}TreeNode;
TreeNode tr[4*N];
int n,m,opt,l,r,v,arr[N];
inline void read(int &num){
    int x=0,f=1;
	char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    num=x*f;
}
void pushup(int x){
	tr[x].sin_sum=tr[lc].sin_sum+tr[rc].sin_sum;
	tr[x].cos_sum=tr[lc].cos_sum+tr[rc].cos_sum;
}
void build(int x,int l,int r){
	tr[x].l=l;
	tr[x].r=r;
	tr[x].add=0;
	if(l==r){
		tr[x].sin_sum=sin(arr[l]);
		tr[x].cos_sum=cos(arr[l]);
		return ;
	}
	int mid=(l+r)>>1;
	build(lc,l,mid);
	build(rc,mid+1,r);
	pushup(x);
}
void calc(int x,double sinx,double cosx){
	double cosa=tr[x].cos_sum,sina=tr[x].sin_sum;
	tr[x].cos_sum=cosa*cosx-sina*sinx;
	tr[x].sin_sum=sina*cosx+cosa*sinx;
}
void pushdown(int x){
	if(tr[x].add){
		double sinx=sin(tr[x].add),cosx=cos(tr[x].add);
		calc(lc,sinx,cosx);
		calc(rc,sinx,cosx);
		tr[lc].add+=tr[x].add;
		tr[rc].add+=tr[x].add;
		tr[x].add=0;
	}
}
double query(int x,int l,int r){
	if(tr[x].l>=l&&tr[x].r<=r){
		return tr[x].sin_sum;
	}
	pushdown(x);
	int mid=(tr[x].l+tr[x].r)>>1;
	double res=0;
	if(mid>=l)res+=query(lc,l,r);
	if(r<mid)res+=query(rc,l,r);
	return res;
}
void update(int x,int l,int r,int add){
	if(tr[x].l>=l&&tr[x].r<=r){
		double sinx=sin(add),cosx=cos(add);
		calc(x,sinx,cosx);
		tr[x].add+=add;
		return ;
	}
	pushdown(x);
	int mid=(tr[x].l+tr[x].r)>>1;
	if(mid>=l)update(lc,l,r,add);
	if(mid<r)update(rc,l,r,add);
	pushup(x);
}
signed main(){
	read(n);
	for(int i=1;i<=n;++i){
		read(arr[i]);
	}
	build(1,1,n);
	read(m);
	while(m--){
		read(opt);
		read(l);
		read(r);
		switch(opt){
			case 1:
				read(v);
				update(1,l,r,v);
				break;
			case 2:
				printf("%.1lf\n",query(1,l,r));
				break;
		}
	}
}

样例都不对,逻辑上感觉是对的,求调

2024/5/25 17:05
加载中...