Wannafly 挑战赛22 D 整数序列 线段树 区间更新，区间查询

题目链接：https://www.nowcoder.com/acm/contest/160/D

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

给出一个长度为n的整数序列a,a,...,a，进行m次操作，操作分为两类。
操作1：给出l,r,v，将a,a,...,a分别加上v；
操作2：给出l,r，询问

输入描述:

n个数，m次操作
op=1, l,r,v 区间[l,r] 加v
op=2, l,r 区间查询上式
n,m,val[i] <= 2e5

输出描述:

对每个操作2，输出一行，表示答案，四舍五入保留一位小数
保证答案的绝对值大于0.1，且答案的准确值的小数点后第二位不是4或5
数据随机生成（n,m人工指定，其余整数在数据范围内均匀选取），并去除不满足条件的操作2

输入例子:

4

1 2 3 4

5

2 2 4

1 1 3 1

2 2 4

1 2 4 2

2 1 3

输出例子:

0.3

-1.4

-0.3

-->

示例1

输入

4

1 2 3 4

5

2 2 4

1 1 3 1

2 2 4

1 2 4 2

2 1 3

输出

0.3

-1.4

-0.3

很明显区间更新的题 用lazy维护某一段区间的 sin(val[i])和 cos(val[i])值
根据下面的式子  可知道 要保证区间加和性，就要先要 维护sin(x) 区间加和的性质
so 看代码 和 公式 应该差不多能理解的

// sin(x + v) = sinx*cosv+sinvcosx

// cos(x + v) = cosx*cosv-sinx*sinv

// sin(x1 + v) + sin(x2 + v) = cosv*(sinx1+sinx2) + sinv*(cosx1+cosx2)

// cos(x1 + v) + cos(x1 + v) = cosv*(cosx1+cosx2) - sinv*(sinx1+sinx2)

#include<bits/stdc++.h>

using namespace std;

const int N = +;

#define ls rt<<1

#define rs rt<<1|1

typedef long long ll;

ll val[N], lz[N<<];

double ssin[N<<],ccos[N<<];

void up(int rt) {

    ssin[rt] = ssin[ls] + ssin[rs];

    ccos[rt] = ccos[ls] + ccos[rs];

}

void down(int rt) {

    if(lz[rt]) {

        ll v = lz[rt];

        lz[ls] += v;

        lz[rs] += v;

        double tsin=ssin[ls], tcos=ccos[ls];

        ssin[ls]=tsin*cos(v) + tcos*sin(v);

        ccos[ls]=tcos*cos(v) - tsin*sin(v);

        tsin=ssin[rs],tcos=ccos[rs];

        ssin[rs]=tsin*cos(v) + tcos*sin(v);

        ccos[rs]=tcos*cos(v) - tsin*sin(v);

        lz[rt]=;

    }

}

void build(int rt,int l,int r) {

    if(l==r) {

        ssin[rt]=sin(val[l]);

        ccos[rt]=cos(val[l]);

        return ;

    }

    int m = (l+r)/;

    build(ls,l,m);

    build(rs,m+,r);

    up(rt);

}

void update(int rt,int l,int r,int L,int R,ll v) {

    if(L <= l && r <= R) {

        lz[rt] += v;

        double tsin=ssin[rt], tcos=ccos[rt];

        ssin[rt]=tsin*cos(v) + tcos*sin(v);

        ccos[rt]=tcos*cos(v) - tsin*sin(v);

        return ;

    }

    down(rt);

    int m = (l+r)/;

    if(L <= m)

        update(ls,l,m,L,R,v);

    if(m < R)

        update(rs,m+,r,L,R,v);

    up(rt);

}

double query(int rt,int l,int r,int L,int R) {

    if(L<=l && r<=R) {

        return ssin[rt];

    }

    down(rt);

    int m = (l+r)/;

    double res = ;

    if(L <= m)

        res += query(ls,l,m,L,R);

    if(m < R)

        res += query(rs,m+,r,L,R);

    return res;

}

int n,m;

int main ()

{

    //freopen("in.txt","r",stdin);

    while (scanf("%d",&n)!=EOF) {

        memset(lz,,sizeof(lz));

        for(int i=;i<=n;i++) {

            scanf("%lld", &val[i]);

        }

        build(,,n);

        scanf("%d", &m);

        while (m--){

            int op,l,r;

            scanf("%d %d %d",&op,&l,&r);

            if(op==) {

                ll v; scanf("%lld",&v);

                update(,,n,l,r,v);

            }else {

                printf("%.1f\n",query(,,n,l,r));

            }

        }

    }

    return ;

}