Links: https://ac.nowcoder.com/acm/contest/160/D
Source: Niuke.com

Sequence of integers
Time limit: C/C++ 2 seconds, 4 seconds for other languages
Space limit: C/C++ 262144K, other languages 524288K
64bit IO Format: %lld
Title Description
Gives an integer sequence a1,a2,...,an of length n for m operations, which are divided into two categories.
Operation 1: Give l,r,v, add V to al,al+1,...,ar respectively;
Action 2: Give l,r, and ask \sum\limits_{i=l}^{r}sin(a_i)
i=l
∑
r
​
sin(a
i
​
)
Enter a description:
The first line is an integer n
The next line contains n integers representing a1,a2,...,an
The next line is an integer m
Next m lines, each representing an operation, operation 1 being 1L R V and operation 2 being 2L R
Guarantee that 1 < n,m,ai,v < 200000; 1 < l < r < n, v is an integer
Output description:
For each operation 2, output a line to indicate the answer, and round off to reserve a decimal place
Ensure that the absolute value of the answer is greater than 0.1 and that the second decimal place after the exact value of the answer is not 4 or 5
Random data generation (n,m specified manually, the rest of the integers are selected evenly across the data range), and operation 2 that does not meet the criteria is removed
Example 1
input
copy
4
1 2 3 4
5
2 2 4
1 1 3 1
2 2 4
1 2 4 2
2 1 3
output
copy
0.3
-1.4
-0.3

Topic:

Ideas:

Maintaining a segment tree is certainly an idea, but sin(xi) does not satisfy interval additivity.

Convert

sin(x+v) = sin(x)cos(v) + cos(x)sin(v)

cos(x+v) = cos(x)cos(v) - sin(x)sin(v)

We only need to maintain sin(x) and cos(x) to easily get sin(x+v) and cos(x+v)

If complex numbers are introduced:

cos(x)+sin(x)i ( cos(v)+sin(v)i ) = cos(x)cos(v)-sin(x)sin(v)+cos(x)sin(v)+sin(x)*cos(v) = cos(x+v)+sin(x+v)i

(This section is quoted from) Uniontake's blog: https://blog.csdn.net/m0_38013346/article/details/81807711

See code for details:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <bits/stdc++.h>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define ALL(x) (x).begin(), (x).end()
#define dll(x) scanf("%I64d",&x)
#define xll(x) printf("%I64d\n",x)
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(&x)
#define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
inline void getInt(int* p);
const int maxn=200010;
const int inf=0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/

typedef complex<double> comd;
int a[maxn];

struct node
{
    comd val;
    comd add;
    int l,r;
}segment_tree[maxn<<2];
int n;
void pushup(int rt)
{
    segment_tree[rt].val=segment_tree[rt<<1].val+segment_tree[rt<<1|1].val;

}
void build(int rt,int l,int r)
{
    segment_tree[rt].add=comd(1,0);
    segment_tree[rt].l=l;
    segment_tree[rt].r=r;
    if(l==r)
    {
        segment_tree[rt].val=comd(cos(a[l]),sin(a[l]));
        return ;
    }
    int mid=(l+r)>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    pushup(rt);
}
void pushdown(int rt)
{
    if(segment_tree[rt].add!=comd(1,0))
    {
        segment_tree[rt<<1].add*=segment_tree[rt].add;
        segment_tree[rt<<1].val*=segment_tree[rt].add;
        segment_tree[rt<<1|1].add*=segment_tree[rt].add;
        segment_tree[rt<<1|1].val*=segment_tree[rt].add;
        segment_tree[rt].add=comd(1,0);
    }
}
void update(int rt,int l,int r,comd x)
{
    if(segment_tree[rt].l>=l&&segment_tree[rt].r<=r)
    {
        segment_tree[rt].val*=x;
        segment_tree[rt].add*=x;
        return ;
    }
    pushdown(rt);
    int mid=(segment_tree[rt].l+segment_tree[rt].r)>>1;
    if(mid>=l)
    {
        update(rt<<1,l,r,x);
    }
    if(mid<r)
    {
        update(rt<<1|1,l,r,x);
    }
    pushup(rt);

}
double ask(int rt,int l,int r)
{
    if(segment_tree[rt].l>=l&&segment_tree[rt].r<=r)
    {
        return segment_tree[rt].val.imag();
    }
    double res=0.0;
    pushdown(rt);
    int mid=(segment_tree[rt].l+segment_tree[rt].r)>>1;
    if(mid>=l)
    {
        res+=ask(rt<<1,l,r);
    }
    if(mid<r)
    {
        res+=ask(rt<<1|1,l,r);
    }
    return res;
}
int main()
{
    //freopen("D:\\common_text\\code_stream\\in.txt","r",stdin);
    //freopen("D:\\common_text\\code_stream\\out.txt","w",stdout);

    gbtb;
    cin>>n;
    repd(i,1,n)
    {
        cin>>a[i];
    }
    build(1,1,n);
    int m;
    cin>>m;
    int op,l,r;
    int x;
    while(m--)
    {
        cin>>op>>l>>r;
        if(op==1)
        {
            cin>>x;
            update(1,l,r,comd(cos(x),sin(x)));
        }else
        {
            cout<<fixed<<setprecision(1)<<ask(1,l,r)<<endl;
        }
    }


    return 0;
}

inline void getInt(int* p) {
    char ch;
    do {
        ch = getchar();
    } while (ch == ' ' || ch == '\n');
    if (ch == '-') {
        *p = -(getchar() - '0');
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 - ch + '0';
        }
    }
    else {
        *p = ch - '0';
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 + ch - '0';
        }
    }
}