求调,全都TLE了
查看原帖
求调,全都TLE了
753368
chenzhix楼主2025/7/28 15:15

代码如下,样例通过。

#include<bits/stdc++.h>
using namespace std;
#define maxn 200005
int n,m,w[maxn];
struct Tree{
	long long l,r,add;
	double sin,cos;//存储节点的正弦值,余弦值
}tr[maxn*4];
void pushup(long long u){//上传
	tr[u].sin=tr[u*2].sin+tr[u*2+1].sin;
	tr[u].cos=tr[u*2].cos+tr[u*2+1].cos;
}
void pushdown(long long u){//下传
	if(tr[u].add){
		tr[u*2].sin=tr[u*2].sin*cos(tr[u*2].add)+tr[u].cos*sin(tr[u*2].add);
		tr[u*2].cos=tr[u*2].cos*cos(tr[u*2].add)-tr[u].sin*sin(tr[u*2].add);
		tr[u*2+1].sin=tr[u*2+1].sin*cos(tr[u*2+1].add)+tr[u*2+1].cos*sin(tr[u*2+1].add);
		tr[u*2+1].cos=tr[u*2+1].cos*cos(tr[u*2+1].add)-tr[u].sin*sin(tr[u*2+1].add);
		tr[u*2].add+=tr[u].add;
		tr[u*2+1].add+=tr[u].add;
		tr[u].add=0;
	}
}
void build(long long u,long long l,long long r){//建树
	tr[u].add=0,tr[u].l=l,tr[u].r=r,tr[u].sin=sin(w[l]),tr[u].cos=cos(w[l]);
	if(l==r) return;//如果区间长为一,到达叶子节点
	long long mid=(l+r)>>1;
	build(u*2,l,mid);//左树
	build(u*2+1,mid+1,r);//右树
	pushup(u);//更新正弦值和余弦值
}
void change(long long u,long long l,long long r,long long k){//区间修改
	if(r<tr[u].l||l>tr[u].r) return;
	if(l<=tr[u].l&&r>=tr[u].r){
		tr[u].sin=tr[u].sin*cos(k)+tr[u].cos*sin(k);
		tr[u].cos=tr[u].cos*cos(k)-tr[u].sin*sin(k);
		tr[u].add+=k;
		return;
	}
	long long mid=(tr[u].l+tr[u].r)>>1;
	pushdown(u);
	if(l<=mid) change(u*2,l,r,k);
	if(r>mid) change(u*2+1,l,r,k);
	pushup(u);
}
double query(long long u,long long l,long long r){//区查
	if(r<tr[u].l||l>tr[u].r) return 0;
	if(l<=tr[u].l&&r>=tr[u].r) return tr[u].sin;
	long long mid=(tr[u].l+tr[u].r)>>1;
	pushdown(u);
	double sin_sum=0;
	if(l<=mid) sin_sum+=query(u*2,l,r);
	if(r>mid) sin_sum+=query(u*2+1,l,r);
	return sin_sum;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>w[i];
	build(1,1,n);
	cin>>m;
	while(m--){
		int op,l,r,k;
		cin>>op>>l>>r;
		if(op==2) printf("%.1f\n",query(1,l,r));
		else{
			cin>>k;
			change(1,l,r,k);
		}
	}
	return 0;
}
2025/7/28 15:15
加载中...