题解：P5889 跳树

· · 题解

分析

题目总共的三种操作都很格式，每个点也没有什么特别之处，所以只需要考虑当前位置位移即可。二叉树的位移正好可以使用位运算实现：

综合起来，每一个点都进行运算的话，每一个回答都可以写成 (sum>>down)<<up|val，所以只需要维护区间的值即可。修改操作为单点修改，将一个操作修改为另一个操作。如果要暴力维护的话就是 \operatorname{O}(n^2) 的复杂度。所以考虑使用线段树维护，复杂度 \operatorname{O}(n\log n)。

合并操作

合并操作是这道题目第一大难题。

首先需要确定线段树中维护的东西：

观察可得，每向下跳一次并且跳在了右子节点上，偏差就会翻倍并且加上从相邻左子节点到目标右子节点的数量，即 val=val<<1|1，其实就是往右的下标。第一次，找到这一个或上的 1，之后不断这样操作即可。

同时，向上的数量永远可以抵消向下的数量，但是向下的数量不一定能够抵消向上的数量，所以就需要这一个 val 来平衡。

其他的没什么了，因为这一个合并操作满足可加性，并且题目中的需求是单点修改和区间查询，所以使用线段树来维护。

代码

#include<bits/stdc++.h>
#define MAXN 500001
#define push_up(root) tree[root]=merge(tree[root<<1],tree[root<<1|1])
#define debug(node) cout<<node.up<<" "<<node.down<<" "<<node.val<<endl
typedef long long ll;
using namespace std;
struct node{
    int up,down;
    ll val;
//  node()=default;
    node(int up=0,int down=0,ll val=0ll){
        this->up=up;
        this->down=down;
        this->val=val;
    }
}tree[MAXN<<2];
int m,q,op[MAXN];
inline node set_opt(int opt){
    if(opt==1){
        return node(1,0,0ll);
    }else if(opt==2){
        return node(1,0,1ll);
    }
    return node(0,1,0ll);
}
inline node merge(node lson,node rson){
    node result;
    result.val=(lson.val>>rson.down)<<rson.up|rson.val;
    result.down=lson.down+max(rson.down-lson.up,0);
    result.up=rson.up+max(lson.up-rson.down,0);
    return result;
}
inline void build(int root,int l,int r){
    if(l==r){
        tree[root]=set_opt(op[l]);
//      debug(tree[root]);
        return;
    }
    int mid=(l+r)>>1;
    build(root<<1,l,mid);
    build(root<<1|1,mid+1,r);
    push_up(root); 
//  debug(tree[root]);
}
inline node query(int root,int l,int r,int L,int R){
    if(L<=l&&r<=R){
        return tree[root];
    }
    int mid=(l+r)>>1;
    node result;
    if(L<=mid){
        result=merge(result,query(root<<1,l,mid,L,R));
    }
    if(mid<R){
        result=merge(result,query(root<<1|1,mid+1,r,L,R));
    }
//  debug(result);
    push_up(root);
    return result;
}
inline void change(int root,int pos,int l,int r,int opt){
    if(pos==l&&pos==r){
        tree[root]=set_opt(opt);
        return;
    }
    int mid=(l+r)>>1;
    if(pos<=mid){
        change(root<<1,pos,l,mid,opt);
    }else{
        change(root<<1|1,pos,mid+1,r,opt);
    }
    push_up(root);
}
int main(){
    scanf("%*d %d %d",&m,&q);
    for(int i=1;i<=m;++i){
        scanf("%d",&op[i]);
    }
    build(1,1,m);
    while(q--){
        int opt;
        scanf("%d",&opt);
        if(opt==1){
            ll s;
            int l,r;
            scanf("%lld %d %d",&s,&l,&r);
            node result=query(1,1,m,l,r);
//          debug(result);
            printf("%lld\n",max(1ll,s>>result.down)<<result.up|result.val);
        }else{
            int x,y;
            scanf("%d %d",&x,&y);
            change(1,x,1,m,y);
        }
    }
    return 0;
}
/*
3 5 4
1 2 3 3 1
1 3 4 5
1 2 2 4
2 3 1
1 1 2 3
*/