利用公式
sin(a+b)=sinacosb+cosasinb
cos(a+b)=cosacosb−sinasinb
可得:
∑sin(ai+v)=∑sinaicosv+∑cosaisinv=(∑sinai)cosv+(∑cosai)sinv
所以按理来说线段树维护区间 ∑sinai 和 ∑cosai,每次区间加 v 的操作对于第一棵树,相当于区间乘 cosv,再区间加 (∑cosai)sinv 就行了,第二棵树同理,那我的代码过了样例,为啥全错?
#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;
}
拜谢大神!