线段树MLE求问原因
查看原帖
线段树MLE求问原因
338786
mushroom_knight楼主2021/2/16 10:50

RT,请问为何这份代码是MLE?

如果您没看出来具体在哪里,

也可以跟我说一下您觉得可能是哪里炸掉了。

谢谢。

(快读板子已省去)

const int si=2e5+10;
int n,m;
int a[si];
struct segment_tree{
    int l,r;
    double sum_cos,sum_sin;
    int lazytag;
    #define l(o) t[o].l
    #define r(o) t[o].r
    #define tag(o) t[o].lazytag
    #define sinv(o) t[o].sum_sin
    #define cosv(o) t[o].sum_cos
    #define lson(o) o>>1
    #define rson(o) o>>1|1
}t[si*4];

inline void build(int p,int l,int r){
    l(p)=l,r(p)=r;
    if(l==r){
        sinv(p)=sin(a[l]);
        cosv(p)=cos(a[l]);
        return;
    }
    int mid=(l+r)>>1;
    build(lson(p),l,mid);
    build(rson(p),mid+1,r);
    sinv(p)=sinv(lson(p))*cosv(rson(p))+sinv(rson(p))*cosv(lson(p));
    cosv(p)=cosv(lson(p))*cosv(rson(p))-sinv(lson(p))*sinv(rson(p));
}

inline void pushdown(int p){
    if(tag(p)){
        sinv(lson(p))=sinv(lson(p))*cos(tag(p))+sin(tag(p))*cosv(lson(p));
        cosv(lson(p))=cosv(lson(p))*cos(tag(p))-sinv(lson(p))*sin(tag(p));
        sinv(rson(p))=sinv(rson(p))*cos(tag(p))+sin(tag(p))*cosv(rson(p));
        cosv(rson(p))=cosv(rson(p))*cos(tag(p))-sinv(rson(p))*sin(tag(p));
        tag(lson(p))+=tag(p),tag(rson(p))+=tag(p);
        tag(p)=0;
    }
}

void update(int p,int l,int r,int v){
    int nl=l(p),nr=r(p);
    if(l<=nl&&nr<=r){
        sinv(p)=sinv(p)*cos(v)+sin(v)*cosv(p);
        cosv(p)=cosv(p)*cos(v)-sin(v)*sinv(p);
        tag(p)+=v;
        return;
    }
    pushdown(p);
    int mid=(nl+nr)>>1;
    if(l<=mid){
        update(lson(p),l,r,v);
    }
    if(r>mid){
        update(rson(p),l,r,v);
    }
    sinv(p)=sinv(lson(p))*cosv(rson(p))+sinv(rson(p))*cosv(lson(p));
    cosv(p)=cosv(lson(p))*cosv(rson(p))-sinv(lson(p))*sinv(rson(p));
}

double query(int p,int l,int r){
    int nl=l(p),nr=r(p);
    if(l<=nl&&nr<=r){
        return sinv(p);
    }
    pushdown(p);
    double res=0;
    int mid=(nr+nl)>>1;
    if(l<=mid){
        res+=query(lson(p),l,r);
    }
    if(r>mid){
        res+=query(rson(p),l,r);
    }
    return res;
}


int main(){
    #ifndef ONLINE_JUDGE
        freopen("out.txt","w",stdout);
    #endif
    read(n),read(m);
    for(register int i=1;i<=n;++i){
        read(a[i]);
    }
    build(1,1,n);
    while(m--){
        int op,x,y,k;
        read(op),read(x),read(y);
        if(op==1){
            read(k);
            update(1,x,y,k);
        }
        else{
            printf("%.1lf\n",query(1,x,y));
        }
    }
    return 0;
}
2021/2/16 10:50
加载中...