解题报告 P5524 [Ynoi2012]NOIP2015洋溢着希望

题目内容

P5524

大意：维护一个序列 a，使其支持以下操作：

• 给定 l，r，求 \displaystyle\sum_{i=l}^r\sin(a_i)
• 给定 l，r，v，让 [l,r] 中的每一个数加 v

解题思路

终于有一道我可以做的 Ynoi 了 qwqwq

最简单的 Ynoi，没有之一，像我这种只会线段树的 sb 都可以切了它 qwq

观察这题，发现要求维护的是 \sum\sin(a_i)，而我们需要进行区间加某数的操作，所以考虑对 \sum\sin(a_i+v) 进行展开：

\begin{aligned}
&\sum_{i=l}^r\sin(a_i+v)\
=&\sum_{i=l}^r(\sin a_i\cos v+\sin v\cos a_i)\
=&\cos v\sum_{i=l}^r\sin a_i+\sin v\sum_{i=l}^r\cos a_i
\end{aligned}

所以我们需要维护两棵线段树，一棵维护 \sum\sin a_i，一棵维护 \sum\cos a_i，而涉及到 \sum\cos a_i 的修改怎么办呢？见下

\begin{aligned}
&\sum_{i=l}^r\cos(a_i+v)\
=&\sum_{i=l}^r(\cos a_i\cos v-\sin a_i\sin v)\
=&\cos v\sum_{i=l}^r\cos a_i-\sin v\sum_{i=l}^r\sin a_i
\end{aligned}

所以两个要同时修改，要建立临时变量来存储之前的 \sum\sin a_i 与 \sum\cos a_i。然后为了优化常数不被卡，每次修改的时候要预处理 \sin v 和 \cos v，不然会被卡。

lazytag 要开 long long，不然在玄学的在 line 几万处 WA

#include <cstdio>
#include <cctype>
#include <cmath>
#define L (k<<1)
#define R (L|1)
#define M (i+j>>1)
typedef long long ll;

const int maxn=2e5+5;
double fsin[maxn<<2],fcos[maxn<<2];
int n,m;
ll tag[maxn<<2];

inline ll read()
{
    char c=getchar();
    ll s=0;
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c))
        s=10*s+c-'0',c=getchar();
    return s;
}

void build(int i,int j,int k)
{
    if(i==j)
    {
        int x=read();
        fsin[k]=sin(x);
        fcos[k]=cos(x);
        return;
    }
    build(i,M,L);
    build(M+1,j,R);
    fsin[k]=fsin[L]+fsin[R];
    fcos[k]=fcos[L]+fcos[R];
    return;
}

void down(int i,int j,int k)
{
    double lsin=fsin[L],rsin=fsin[R],lcos=fcos[L],rcos=fcos[R];
    double sine=sin(tag[k]),cosi=cos(tag[k]);
    fsin[L]=lsin*cosi+lcos*sine;
    fcos[L]=lcos*cosi-lsin*sine;
    tag[L]+=tag[k];
    fsin[R]=rsin*cosi+rcos*sine;
    fcos[R]=rcos*cosi-rsin*sine;
    tag[R]+=tag[k];
    tag[k]=0;
    return;
}

void modify(int i,int j,int l,int r,int k,int d)
{
    if(i>=l && j<=r)
    {
        double ssin=fsin[k],ccos=fcos[k];
        double sine=sin(d),cosi=cos(d);
        fsin[k]=ssin*cosi+ccos*sine;
        fcos[k]=ccos*cosi-ssin*sine;
        tag[k]+=d;
        return;
    }
    if(tag[k])
        down(i,j,k);
    if(l<=M)
        modify(i,M,l,r,L,d);
    if(r>M)
        modify(M+1,j,l,r,R,d);
    fsin[k]=fsin[L]+fsin[R];
    fcos[k]=fcos[L]+fcos[R];
    return;
}

double ask(int i,int j,int l,int r,int k)
{
    if(i>=l && j<=r)
        return fsin[k];
    if(tag[k])
        down(i,j,k);
    double ans=0;
    if(l<=M)
        ans+=ask(i,M,l,r,L);
    if(r>M)
        ans+=ask(M+1,j,l,r,R);
    return ans;
}

int main()
{
    n=read();
    build(1,n,1);
    m=read();
    int t,l,r,v;
    while(m--)
    {
        t=read(),l=read(),r=read();
        if(t==1)
        {
            v=read();
            modify(1,n,l,r,1,v);
        }
        else
            printf("%.1f\n",ask(1,n,l,r,1));
    }
    return 0;
}