单点修改直接改下去,区间修改懒标记

sin(a+w)=sina* cosw - cosa* sinw
cos(a+w)=cosa* cosw - sina* sinw

线段树做题方式:
先判断是否是线段树(边改边查,区间修改...)
再思考tr[N]维护什么
若单点修改,则无懒标记
区间修改,ly[N]为待操作数(再思考待操作数是什么)

注意:变量在操作后会改变值,不能乘当前的变量,要乘原来的

#include<bits/stdc++.h>
using namespace std;
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define low(x) x&(-x)
int const N=2e5+7;
int n,m,az[N];
double trs[N<<2],trc[N<<2];
double ly[N<<2];
double a,b,c,d;
void bulid(int p,int l,int r){
    if(l==r) {
        trs[p]=sin(az[l]),trc[p]=cos(az[l]);
        return ;
    }
    int mid=(l+r)>>1;
    bulid(p*2,l,mid);
    bulid(p*2+1,mid+1,r);
    trs[p]=trs[p*2]+trs[p*2+1];
    trc[p]=trc[p*2]+trc[p*2+1];    
}
void pushdown(int p){
    ly[p*2]+=ly[p];ly[p*2+1]+=ly[p];
    a=trs[p*2];b=trs[p*2+1];c=trc[p*2];d=trc[p*2+1];
    trs[p*2]=a*cos(ly[p])+c*sin(ly[p]);
    trs[p*2+1]=b*cos(ly[p])+d*sin(ly[p]);
    trc[p*2]=c*cos(ly[p])-sin(ly[p])*a;
    trc[p*2+1]=cos(ly[p])*d-sin(ly[p])*b;
    ly[p]=0;
}
void add(int p,int l,int r,int x,int y,int w){
    if(x<=l&&r<=y){
        ly[p]+=w;
        a=trs[p];b=trc[p];
        trs[p]=a*cos(w)+b*sin(w);
        trc[p]=b*cos(w)-a*sin(w);
        return ;
    }
    if(ly[p]) pushdown(p);
    int mid=(l+r) >> 1;
    if(x<=mid) add(p*2,l,mid,x,y,w);
    if(y>=mid+1) add(p*2+1,mid+1,r,x,y,w);
    trs[p]=trs[p*2]+trs[p*2+1];
    trc[p]=trc[p*2]+trc[p*2+1];
}
double ask(int p,int l,int r,int x,int y){
    if(x<=l&&r<=y) return trs[p];
    if(ly[p]) pushdown(p);
    double res=0;
    int mid=(l+r) >> 1;
    if(x<=mid) res+=ask(p*2,l,mid,x,y);
    if(y>=mid+1) res+=ask(p*2+1,mid+1,r,x,y);
    return res;
}
int main(){
    cin >> n;
    for(int i=1;i<=n;++i) cin >> az[i];
    bulid(1,1,n);
    cin >> m;
    int op,l,r,w;
    double z=0;
    while(m--){
        cin >> op;
        if(op==1){
            cin >> l >> r >> w;
            add(1,1,n,l,r,w);
        }
        else{
            cin >> l >> r;
            z=ask(1,1,n,l,r);
            printf("%.1lf\n",z);
        }
    }
    return 0;    
}
线段树和数状数组经典例题 文章被收录于专栏

线段树和数状数组经典例题

全部评论

相关推荐

点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务