题解 P5524 【[Ynoi2012]NOIP2015洋溢着希望】

panyf · 2020-01-27 20:30:46 · 题解

复数解法，常数很小。

我们有公式：

可以考虑维护每个位置的 \cos(ai)+i\sin(ai) ，线段树区间和，提取虚部即为所求。

对于修改操作，线段树打乘法标记 \cos(v)+i\sin(v) 即可。

代码如下：

#include<cstdio>
#include<cmath>
struct C{//复数类
    double x,y;
    inline C operator+(C b)const{return{x+b.x,y+b.y};}
    inline C operator*(C b)const{return{x*b.x-y*b.y,x*b.y+y*b.x};}
}s[525009],t[525009],w;
int a[200009],u,v;
void build(int k,int l,int r){//建树
    t[k]={1,0};
    if(l==r){
        s[k]={cos(a[l]),sin(a[l])};
        return;
    }
    register int m=l+r>>1,a=k<<1,b=a|1;
    build(a,l,m),build(b,m+1,r),s[k]=s[a]+s[b];
}
inline void down(int k,int a,int b){//标记下传
    if(t[k].y||t[k].x!=1)s[a]=s[a]*t[k],s[b]=s[b]*t[k],t[a]=t[a]*t[k],t[b]=t[b]*t[k],t[k]={1,0};
}
void upd(int k,int l,int r){//修改
    if(u<=l&&r<=v){
        s[k]=s[k]*w,t[k]=t[k]*w;
        return;
    }
    register int m=l+r>>1,a=k<<1,b=a|1;
    down(k,a,b);
    if(u<=m)upd(a,l,m);
    if(m<v)upd(b,m+1,r);
    s[k]=s[a]+s[b];
}
C qry(int k,int l,int r){//询问
    if(u<=l&&r<=v)return s[k];
    register int m=l+r>>1,a=k<<1,b=a|1;
    down(k,a,b);
    if(u<=m&&m<v)return qry(a,l,m)+qry(b,m+1,r);
    if(u<=m)return qry(a,l,m);
    return qry(b,m+1,r);
}
int main(){
    register int n,m,i,j;
    scanf("%d",&n);
    for(i=1;i<=n;++i)scanf("%d",a+i);
    build(1,1,n),scanf("%d",&m);
    while(m--){
        scanf("%d%d%d",&i,&u,&v);
        if(i==1)scanf("%d",&j),w={cos(j),sin(j)},upd(1,1,n);
        else printf("%.1lf\n",qry(1,1,n).y);
    }
    return 0;
}