1 条题解

  • 0
    @ 2026-8-18 10:52:35
    #include <iostream>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    using namespace std;
    
    #define N 200005
    #define ls u<<1
    #define rs u<<1|1
    #define mid ((l+r)>>1)
    int n,m,a[N];
    double sinx[N<<2],cosx[N<<2];
    long long tag[N<<2];
    //sinx:区间正弦和, cosx:区间余弦和
    //tag: 区间懒标记
    
    void pushup(int u){ //上传
      sinx[u]=sinx[ls]+sinx[rs];
      cosx[u]=cosx[ls]+cosx[rs];
    }
    void pd(int u,double sinb,double cosb){
      double sina=sinx[u],cosa=cosx[u];
      sinx[u]=sina*cosb+cosa*sinb; //sin(a+b)
      cosx[u]=cosa*cosb-sina*sinb; //cos(a+b)
    }
    void pushdown(int u){ //下传
      if(!tag[u]) return;
      double sinb=sin(tag[u]),cosb=cos(tag[u]);
      pd(ls,sinb,cosb);
      pd(rs,sinb,cosb);
      tag[ls]+=tag[u];
      tag[rs]+=tag[u];
      tag[u]=0; //清空懒标记
    }
    void build(int u,int l,int r){ //建树
      if(l==r){
        sinx[u]=sin(a[l]);
        cosx[u]=cos(a[l]);
        return;
      }
      build(ls,l,mid);
      build(rs,mid+1,r);
      pushup(u);
    }
    void change(int u,int l,int r,int x,int y,int k){ //区修
      if(x<=l&&r<=y){
        pd(u,sin(k),cos(k));
        tag[u]+=k;
        return;
      }
      pushdown(u);
      if(x<=mid) change(ls,l,mid,x,y,k);
      if(y>mid) change(rs,mid+1,r,x,y,k);
      pushup(u);
    }
    double query(int u,int l,int r,int x,int y){ //区查
      if(x<=l&&r<=y) return sinx[u];
      pushdown(u);
      double res=0;
      if(x<=mid) res=query(ls,l,mid,x,y);
      if(y>mid) res+=query(rs,mid+1,r,x,y);
      return res;
    }
    int main(){
      scanf("%d",&n);
      for(int i=1;i<=n;++i)scanf("%d",&a[i]);
      build(1,1,n);
      scanf("%d",&m); int op,l,r,k;
      while(m--){
        scanf("%d%d%d",&op,&l,&r);
        if(op==1){
          scanf("%d",&k);
          change(1,1,n,l,r,k);
        }
        else printf("%.3lf\n",query(1,1,n,l,r));
      }
      return 0;
    }
    
    • 1

    C40 线段树+数学 [区间加区间 sin 和]

    信息

    ID
    12654
    时间
    1000ms
    内存
    150MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者