TLE90pts求助卡常

帮 @xsyyds 求助 LCT 卡常。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=1e6+10;
int fa[N],tree[N][2];
bool lazy[N];
long long maxx[N],val[N],lazy1[N],lazy2[N];
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
bool nroot(int x){
    return tree[fa[x]][1]==x^tree[fa[x]][0]==x;
}
void pushup(int x){
    maxx[x]=val[x];
    if(tree[x][1])maxx[x]=max(maxx[x],maxx[tree[x][1]]);
    if(tree[x][0])maxx[x]=max(maxx[x],maxx[tree[x][0]]);
}
void pushdown(int x){
    if(lazy[x]){
        swap(tree[x][0],tree[x][1]);
        lazy[tree[x][1]]^=1;
        lazy[tree[x][0]]^=1;
        lazy[x]=0;
    }       
    if(lazy1[x]!=-1e15){
        if(tree[x][1])val[tree[x][1]]=lazy1[x],maxx[tree[x][1]]=lazy1[x];
        if(tree[x][0])val[tree[x][0]]=lazy1[x],maxx[tree[x][0]]=lazy1[x];
        lazy1[tree[x][1]]=lazy1[tree[x][0]]=lazy1[x];
        lazy2[tree[x][1]]=lazy2[tree[x][0]]=0;
        lazy1[x]=-1e15;
    }
    if(lazy2[x]){
        if(tree[x][1])val[tree[x][1]]+=lazy2[x],maxx[tree[x][1]]+=lazy2[x];
        if(tree[x][0])val[tree[x][0]]+=lazy2[x],maxx[tree[x][0]]+=lazy2[x];
        lazy2[tree[x][1]]+=lazy2[x];
        lazy2[tree[x][0]]+=lazy2[x];
        lazy2[x]=0;
    }
}
void pushall(int x){
    if(nroot(x))pushall(fa[x]);
    pushdown(x);
}
void rotate(int x){
    int y=fa[x],z=fa[y],k=tree[y][1]==x,w=tree[x][!k];
    if(nroot(y))tree[z][tree[z][1]==y]=x;tree[x][!k]=y,tree[y][k]=w;
    if(w)fa[w]=y;fa[y]=x,fa[x]=z;
    pushup(y);
}
void splay(int x){
    pushall(x);
    while(nroot(x)){
        int y=fa[x],z=fa[y];
        if(nroot(y))rotate(tree[y][0]==x^tree[z][0]==y?x:y);
        rotate(x);
    }
    pushup(x);
}
void access(int x){
    for(int y=0;x;x=fa[y=x])
        splay(x),tree[x][1]=y,pushup(x);
}
inline void makeroot(int x){
    access(x);
    splay(x);
    lazy[x]^=1;
}
inline void split(int x,int y){
    makeroot(x);
    access(y);
    splay(y);
}
signed main(){
    int n(read()),m(read());
    for(int i=1;i<=n;++i){
        maxx[i]=val[i]=read();
        lazy[i]=-1e15;
        if(i==1)continue;
        fa[i-1]=i;
    }
    for(int i=1;i<=m;++i){
        int tt(read()),a(read()),b(read());
        if(tt==1){
            int c(read());
            split(a,b);
            lazy2[b]=0;
            lazy1[b]=c;
            maxx[b]=c;
            val[b]=c;
        }
        else if(tt==2){
            int c(read());
            split(a,b);
            lazy2[b]+=c;
            maxx[b]+=c;
            val[b]+=c;
        }
        else{
            split(a,b);
            printf("%lld\n",maxx[b]);
        }
    }
    return 0;
}