LuoguP5889 跳树线段树

可以将跳左/右/父亲抽象成二进制的形式.

跳左：x<<1

跳右：x<<1|1

父亲：x>>1

但是题中说如果跳到根节点之后再跳父亲编号仍然不变比较不好处理.

但是我们发现一个性质：令 $fl$ 表示一个区间能跳到最靠上的祖先，$path$ 表示跳到该祖先后向下跳的路径，答案一定可以表示成 max(1,x>>fl)<<l+path.

考虑 fl 上一次跳到根节点的时刻是 fl'，则发现 fl' 到 fl 之间向上跳的多于向下跳的，所以在 fl 时刻一定是最靠上的时刻.

分析出这个后一切就简单了，用线段树合并这个信息就行了.

code:

#include <cstdio> 
#include <cstring> 
#include <algorithm>      
#define N 500008   
#define ll long long 
#define lson now<<1   
#define rson now<<1|1   
#define setIO(s) freopen(s".in","r",stdin)  
using namespace std; 
struct data {     
    int fl,l;  
    ll path;         
    data() { fl=l=path=0; }       
    data operator+(const data b) const {  
        data c;  
        if(b.fl<=l) {   
            c.fl=fl;   
            c.l=l-b.fl+b.l; 
            c.path=((path>>b.fl)<<b.l)+b.path;    
        }
        else {    
            c.fl=fl-l+b.fl;   
            c.l=b.l;  
            c.path=b.path;  
        }
        return c;  
    }
    void init(int t) {
        if(t==1) { 
            l=1,fl=path=0; 
        }  
        if(t==2) {    
            l=path=1,fl=0; 
        }   
        if(t==3) {  
            fl=1,l=path=0; 
        }
    }
}s[N<<2];   
void build(int l,int r,int now) {   
    if(l==r) {    
        int x;  
        scanf("%d",&x);     
        s[now].init(x);  
        return; 
    } 
    int mid=(l+r)>>1;   
    build(l,mid,lson); 
    build(mid+1,r,rson);  
    s[now]=s[lson]+s[rson];      
}           
void update(int l,int r,int now,int p,int v) {  
    if(l==r) { 
        s[now].init(v);  
        return; 
    }  
    int mid=(l+r)>>1;  
    if(p<=mid)  update(l,mid,lson,p,v);  
    else update(mid+1,r,rson,p,v);  
    s[now]=s[lson]+s[rson];  
}    
data query(int l,int r,int now,int L,int R) { 
    if(l>=L&&r<=R)  
        return s[now];  
    int mid=(l+r)>>1;  
    if(L<=mid&&R>mid){
        return query(l,mid,lson,L,R)+query(mid+1,r,rson,L,R);  
    }
    else if(L<=mid){
        return query(l,mid,lson,L,R);  
    }
    else{
        return query(mid+1,r,rson,L,R);  
    }
}
int main() {  
    // setIO("input"); 
    int n,m,q,x,y,z; 
    scanf("%d%d%d",&n,&m,&q);  
    n=m,build(1,n,1);   
    for(int i=1;i<=q;++i) {   
        scanf("%d",&z);   
        if(z==1) {  
            ll s;   
            int l,r;   
            scanf("%lld%d%d",&s,&l,&r); 
            data p=query(1,n,1,l,r); 
            s>>=p.fl;  
            if(!s) s=1;      
            s<<=p.l;    
            s+=p.path;  
            printf("%lld\n",s);   
        }  
        if(z==2) {      
            scanf("%d%d",&x,&y);  
            update(1,n,1,x,y);    
        }
    }      
    return 0; 
}

LuoguP5889 跳树 线段树

推荐阅读

LuoguP5889 跳树线段树