【洛谷P5889】跳树 | Mrsrz's blog

线段树。

题目大意：

给定一棵 $2^n-1$ 个结点的满二叉树。有三种指令：

1. 从当前结点跳到左儿子。保证存在。
2. 从当前结点跳到右儿子。保证存在。
3. 从当前结点跳到父亲。若不存在则忽略本次操作。

给定一个指令序列，有两个操作：

1. 给定起点 $s$ 和 $l,r$，要求从 $s$ 出发，依次执行 $l\sim r$ 指令。求最后到达的点。
2. 修改指令序列中的一条指令。

题解：

由于保证 $1$ 和 $2$ 操作必定合法，因此任意时刻，从一个点出发，有用的向下跳操作不超过 $n$ 次。

我们对一段区间，维护 $t$ 表示这段区间的前面会往上跳多少步，再维护二进制集合 $S$ 表示向上跳完 $t$ 步后，向下跳的操作集合。

合并两端区间可以直接 $O(1)$ 完成。

于是我们可以用线段树维护这个信息，并支持单点修改、区间查询。

时间复杂度 $O((q+m)\log m+qn)$。

Code：

#include<cstdio>
#include<cctype>
using namespace std;
const int N=5e5+5;
char buf[(int)1e8],*ss=buf;
char bwf[(int)3e7],*ww=bwf;
inline int init(){buf[fread(buf,1,(int)1e8-1,stdin)]='\n';fclose(stdin);return 0;}
const int __START__=init();
inline int readint(){
    int d=0;
    while(!isdigit(*ss))++ss;
    while(isdigit(*ss))d=d*10+(*ss++^'0');
    return d;
}
struct data{
    int zt,len,yw;
}d[N<<2];
int n,m,q;
data x;
inline data merge(const data&a,const data&b){
    return(b.yw>=a.len)?(data){b.zt,b.len,a.yw+b.yw-a.len}
    :(data){(a.zt>>b.yw<<b.len)|b.zt,a.len-b.yw+b.len,a.yw};
}
void build(int l,int r,int o){
    if(l==r){
        switch(readint()){
            case 1:d[o]=(data){0,1,0};break;
            case 2:d[o]=(data){1,1,0};break;
            case 3:d[o]=(data){0,0,1};break;
        }
    }else{
        const int mid=l+r>>1;
        build(l,mid,o<<1);
        build(mid+1,r,o<<1|1);
        d[o]=merge(d[o<<1],d[o<<1|1]);
    }
}
void query(int l,int r,int o,const int&L,const int&R){
    if(L<=l&&r<=R)x=merge(x,d[o]);else{
        const int mid=l+r>>1;
        if(L<=mid)query(l,mid,o<<1,L,R);
        if(mid<R)query(mid+1,r,o<<1|1,L,R);
    }
}
void modify(int l,int r,int o,const int&pos,const int&x){
    if(l==r){
        switch(x){
            case 1:d[o]=(data){0,1,0};break;
            case 2:d[o]=(data){1,1,0};break;
            case 3:d[o]=(data){0,0,1};break;
        }
    }else{
        const int mid=l+r>>1;
        if(pos<=mid)modify(l,mid,o<<1,pos,x);else modify(mid+1,r,o<<1|1,pos,x);
        d[o]=merge(d[o<<1],d[o<<1|1]);
    }
}
inline void write(int x){if(x<10)*ww++=x^'0';else write(x/10),*ww++=x%10^'0';}
int main(){
    n=readint(),m=readint(),q=readint();
    build(1,m,1);
    while(q--){
        int op=readint();
        if(op==1){
            x=(data){0};
            int s=readint(),l=readint(),r=readint();
            query(1,m,1,l,r);
            while(s!=1&&x.yw)--x.yw,s>>=1;
            for(int i=x.len-1;~i;--i)
            if(x.zt>>i&1)s=s<<1|1;else s=s<<1;
            write(s),*ww++='\n';
        }else{
            int x=readint(),p=readint();
            modify(1,m,1,x,p);
        }
    }
    fwrite(bwf,1,ww-bwf,stdout);
    return 0;
}