牛课整数序列（数学）

迷南。 2022-05-16 08:36 156阅读 0赞

[传送门][Link 1]

膜拜牛课上的大佬orz。看了他们的代码之后，发现好巧妙。

求![\\sum sin][sum sin]，我们可以用复数来计算，（cos）+（sin）i，这样的形式，然后用线段树更新查询，对于求和，我们直接对复数相加，然后输出复数的虚部。对于更新，是对复数相乘。 复数相乘是（a+bi）\*（c+di）=（ac-bd）+（ad+bc）i， 正好是cos和sin的和角公式。

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    typedef unsigned int ui;
    const ll INF=0x3f3f3f3f3f3f3f3f;
    const int N=2e5+10;
    typedef complex<double> dcom;
    dcom tree[N<<2], lazy[N<<2];
    int n, m;
    int a[N];
    
    void push_up(int rt){
        tree[rt]=tree[rt<<1]+tree[rt<<1|1];
    }
    
    void build(int rt, int l, int r){
        lazy[rt]=(dcom){1,0};
        if(l==r){
            tree[rt]=dcom(cos(a[l]), sin(a[l]));
            return;
        }
        int mid=(l+r)>>1;
        build(rt<<1, l, mid);
        build(rt<<1|1, mid+1, r);
        push_up(rt);
    }
    
    inline void push_down(int rt){
        tree[rt<<1]*=lazy[rt];
        tree[rt<<1|1]*=lazy[rt];
        lazy[rt<<1]*=lazy[rt];
        lazy[rt<<1|1]*=lazy[rt];
        lazy[rt]=(dcom){1,0};
    }
    
    void upd(int rt, int l, int r, int L, int R, dcom val){
        if(L<=l && r<=R){
            tree[rt]*=val;
            lazy[rt]*=val;
            return;
        }
        if(lazy[rt]!=(dcom){1,0})
            push_down(rt);
        int mid=(l+r)>>1;
        if(L<=mid)
            upd(rt<<1, l, mid, L, R, val);
        if(mid<R)
            upd(rt<<1|1, mid+1, r, L, R, val);
        push_up(rt);
    }
    
    dcom query(int rt, int l, int r, int L, int R){
        if(L<=l && r<=R){
            return tree[rt];
        }
        if(lazy[rt]!=(dcom){1,0})
            push_down(rt);
        int mid=(l+r)>>1;
        dcom ret=(dcom){1,0};
        if(L<=mid)
            ret+=query(rt<<1, l, mid, L, R);
        if(mid<R)
            ret+=query(rt<<1|1, mid+1, r, L, R);
        return ret;
    }
    
    int main(){
        scanf("%d", &n);
        for(int i=1; i<=n; i++)
            scanf("%d", a+i);
        build(1, 1, n);
    
        scanf("%d", &m);
        while(m--){
            int o, l, r, v;
            scanf("%d%d%d", &o, &l, &r);
            if(o==1){
                scanf("%d", &v);
                upd(1, 1, n, l, r, dcom(cos(v), sin(v)));
            }
            else{
                dcom tmp=query(1, 1, n, l, r);
                printf("%.1lf\n", tmp.imag());
            }
    
        }
    
        return 0;
    }

[Link 1]: https://www.nowcoder.com/acm/contest/160/D
[sum sin]: https://private.codecogs.com/gif.latex?%5Csum%20sin