洛谷5524 [Ynoi2012]D1T1

Luogu

分析

由和角公式:

$$ \begin{aligned} \sin(a+b)&=\sin a\cos b+\cos a\sin b\\ \cos(a+b)&=\cos a\cos b-\sin a\sin b \end{aligned} $$

线段树维护区间 $\sin$ 和与区间 $\cos$ 和即可。

注意 lazy 标记要开 long long 。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
typedef long long ll;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

int n,m;

#define ls (o<<1)
#define rs (o<<1|1)
double sinv[N<<2],cosv[N<<2];
ll addv[N<<2];
inline void update(int o,ll x) {
    double a=sinv[o],b=cosv[o],c=sin(x),d=cos(x);
    sinv[o]=a*d+b*c,cosv[o]=b*d-a*c,addv[o]+=x;
}
inline void pushup(int o) {
    sinv[o]=sinv[ls]+sinv[rs];
    cosv[o]=cosv[ls]+cosv[rs];
}
inline void pushdown(int o) {
    if (addv[o]) {
        update(ls,addv[o]),update(rs,addv[o]);
        addv[o]=0;
    }
}
inline void build(int o,int l,int r) {
    if (l==r) { int w=read(); sinv[o]=sin(w),cosv[o]=cos(w); return; }
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    pushup(o);
}
inline void modify(int o,int l,int r,int ql,int qr,int w) {
    if (ql<=l&&r<=qr) { update(o,w); return; }
    int mid=(l+r)>>1; pushdown(o);
    if (ql<=mid) modify(ls,l,mid,ql,qr,w);
    if (qr>mid) modify(rs,mid+1,r,ql,qr,w);
    pushup(o);
}
inline double query(int o,int l,int r,int ql,int qr) {
    if (ql<=l&&r<=qr) return sinv[o];
    int mid=(l+r)>>1; double res=0; pushdown(o);
    if (ql<=mid) res+=query(ls,l,mid,ql,qr);
    if (qr>mid) res+=query(rs,mid+1,r,ql,qr);
    pushup(o); return res;
}
#undef ls
#undef rs

int main() {
    n=read(); build(1,1,n); m=read();
    while (m--) {
        int op=read(),l=read(),r=read();
        if (op==1) modify(1,1,n,l,r,read());
        else printf("%.1lf\n",query(1,1,n,l,r));
    }
    return 0;
}
最后修改:2019 年 09 月 27 日 01 : 54 PM

发表评论