zcmimi's blog

查看原题

点击跳转

记录每段区间操作后:

向上k级祖先,向下d级孩子,该层向右的第i个孩子

线段树维护即可

#include<bits/stdc++.h>
const int N=500011;
#define ls rt<<1
#define rs rt<<1|1
typedef long long ll;
struct node{
    int k,d;ll i;//k级祖先,祖先的d代孩子,到终点后在该层加上i
    node operator+(const node&x)const{
        if(!x.k&&!x.d)return *this;
        if(!k&&!d)return x;
        if(d>x.k)return node{k,d-x.k+x.d,((i>>x.k)<<x.d)+x.i};
        else return node{k+x.k-d,x.d,x.i};
    }
}s[N<<2],typ[3]={node{0,1,0},node{0,1,1},node{1,0,0}};
void build(int l,int r,int rt){
    if(l==r){
        int v;scanf("%d",&v);
        s[rt]=typ[v-1];
        return;
    }
    int m=l+r>>1;
    build(l,m,ls),build(m+1,r,rs);
    s[rt]=s[ls]+s[rs];
}
void upd(int p,int v,int l,int r,int rt){
    if(l==r)return s[rt]=typ[v-1],void();
    int m=l+r>>1;
    if(p<=m)upd(p,v,l,m,ls);
    else upd(p,v,m+1,r,rs);
    s[rt]=s[ls]+s[rs];
}
node ask(int L,int R,int l,int r,int rt){
    if(L<=l&&r<=R)return s[rt];
    int m=l+r>>1;
    if(L>m)return ask(L,R,m+1,r,rs);
    else if(R<=m)return ask(L,R,l,m,ls);
    else return ask(L,m,l,m,ls)+ask(m+1,R,m+1,r,rs);
}
int main(){
    int n,m,q,opt,x,y,z,v;ll s;
    scanf("%d%d%d",&n,&m,&q);
    build(1,m,1);
    while(q--){
        scanf("%d",&opt);
        if(opt==1){
            scanf("%lld%d%d",&s,&x,&y);
            node res=ask(x,y,1,m,1);
            printf("%lld\n",(std::max(1ll,s>>res.k)<<res.d)+res.i);
        }
        else scanf("%d%d",&x,&v),upd(x,v,1,m,1);
    }
}
LG 5889 跳树
comment评论
Search
search