为什么不能直接用区间加区间乘维护?
查看原帖
为什么不能直接用区间加区间乘维护?
536337
eb0ycn楼主2024/3/1 14:59

利用公式

sin⁡(a+b)=sin⁡acos⁡b+cos⁡asin⁡b\sin(a+b)=\sin a\cos b+\cos a \sin b

cos⁡(a+b)=cos⁡acos⁡b−sin⁡asin⁡b\cos (a+b)=\cos a\cos b-\sin a\sin b

可得:

∑sin⁡(ai+v)=∑sin⁡aicos⁡v+∑cos⁡aisin⁡v=(∑sin⁡ai)cos⁡v+(∑cos⁡ai)sin⁡v \sum \sin(a_i+v)=\sum\sin a_i \cos v + \sum \cos a_i \sin v = (\sum \sin a_i)\cos v+(\sum \cos a_i)\sin v

所以按理来说线段树维护区间 ∑sin⁡ai\sum \sin a_i 和 ∑cos⁡ai\sum \cos a_i,每次区间加 vv 的操作对于第一棵树,相当于区间乘 cos⁡v\cos v,再区间加 (∑cos⁡ai)sin⁡v(\sum \cos a_i) \sin v 就行了,第二棵树同理,那我的代码过了样例,为啥全错?

#include <bits/stdc++.h>
using namespace std;
int n,a[200001],m,op,qqql,qqqr;
double sv,cv,v,t1[800000],t2[800000],l1[800000],l2[800000],l3[800000],l4[800000],rets,retc;
void build(int l,int r,int root){
	if(l==r){l3[root]=l1[root]=1,t1[root]=sin(a[l]),t2[root]=cos(a[l]);return;}
	int mid=l+r>>1;
	build(l,mid,root<<1),build(mid+1,r,root<<1|1),t1[root]=t1[root<<1]+t1[root<<1|1],t2[root]=t2[root<<1]+t2[root<<1|1],l3[root]=l1[root]=1,l2[root]=l4[root]=0;
}
void pushdown1(int l,int r,int root){
	if(l1[root]==1&&l2[root]==0)return;
	int mid=l+r>>1;
	t1[root<<1]*=l1[root],t1[root<<1]+=(mid-l+1)*l2[root],t1[root<<1|1]*=l1[root],t1[root<<1|1]+=(r-mid)*l2[root];
	l1[root<<1]*=l1[root],l2[root<<1]=l2[root<<1]*l1[root]+l2[root],l1[root<<1|1]*=l1[root],l2[root<<1|1]=l2[root<<1|1]*l1[root]+l2[root];
	l1[root]=1,l2[root]=0;
}
void pushdown2(int l,int r,int root){
	if(l3[root]==1&&l4[root]==0)return;
	int mid=l+r>>1;
	t2[root<<1]*=l3[root],t2[root<<1]+=(mid-l+1)*l4[root],t2[root<<1|1]*=l3[root],t2[root<<1|1]+=(r-mid)*l4[root];
	l3[root<<1]*=l3[root],l3[root<<1|1]*=l3[root],l4[root<<1]=l4[root<<1]*l3[root]+l4[root],l4[root<<1|1]=l4[root<<1|1]*l3[root]+l4[root];
	l3[root]=1,l4[root]=0;
}
double querys(int l,int r,int root,int ql,int qr){
	if(ql<=l&&r<=qr)return t1[root];
	pushdown1(l,r,root);
	int mid=l+r>>1;double ret=0;
	if(mid>=ql)ret+=querys(l,mid,root<<1,ql,qr);
	if(mid<qr)ret+=querys(mid+1,r,root<<1|1,ql,qr);
	return ret;
}
double queryc(int l,int r,int root,int ql,int qr){
	if(ql<=l&&r<=qr)return t2[root];
	pushdown2(l,r,root);
	int mid=l+r>>1;double ret=0;
	if(mid>=ql)ret+=queryc(l,mid,root<<1,ql,qr);
	if(mid<qr)ret+=queryc(mid+1,r,root<<1|1,ql,qr);
	return ret;
}
void update1(int l,int r,int root,int ql,int qr,double v1,double v2){
	if(ql<=l&&r<=qr){t1[root]*=v1,t2[root]*=v2,l1[root]*=v1,l3[root]*=v2,l2[root]*=v1,l4[root]*=v2;return;}
	pushdown1(l,r,root),pushdown2(l,r,root);
	int mid=l+r>>1;
	if(mid>=ql)update1(l,mid,root<<1,ql,qr,v1,v2);
	if(mid<qr)update1(mid+1,r,root<<1|1,ql,qr,v1,v2);
	t1[root]=t1[root<<1]+t1[root<<1|1],t2[root]=t2[root<<1]+t2[root<<1|1];
}
void update2(int l,int r,int root,int ql,int qr,double v1,double v2){
	if(ql<=l&&r<=qr){t1[root]+=(r-l+1)*v1,t2[root]+=(r-l+1)*v2,l2[root]+=v1,l4[root]+=v2;return;}
	pushdown1(l,r,root),pushdown2(l,r,root);
	int mid=l+r>>1;
	if(mid>=ql)update2(l,mid,root<<1,ql,qr,v1,v2);
	if(mid<qr)update2(mid+1,r,root<<1|1,ql,qr,v1,v2);
	t1[root]=t1[root<<1]+t1[root<<1|1],t2[root]=t2[root<<1]+t2[root<<1|1];
}
int main(){
	// freopen("t1.in","r",stdin),freopen("t1.out","w",stdout);
	scanf("%d",&n);for(int i=1;i<=n;++i)scanf("%d",a+i);
	build(1,n,1),scanf("%d",&m);
	while(m--){
	scanf("%d%d%d",&op,&qqql,&qqqr);
		if(op==1)scanf("%lf",&v),sv=sin(v),cv=cos(v),rets=querys(1,n,1,qqql,qqqr),retc=queryc(1,n,1,qqql,qqqr),update1(1,n,1,qqql,qqqr,cv,cv),update2(1,n,1,qqql,qqqr,retc*sv,-1l*rets*sv);
		else printf("%.1lf\n",querys(1,n,1,qqql,qqqr));
	}return 0;
}

拜谢大神!

2024/3/1 14:59
加载中...