社论：P14348 [JOISC 2019] 穿越时空 Bitaro / Bitaro, who Leaps through Time

Jordan_Pan · 2025-11-25 08:56:29 · 题解

0

被神秘双半群构造吓哭了，我怎么只会汤包了的无脑做法。（但是本质相同？）

qoj 代码长度倒四，但是两个 \log 最优解 hyw？

1

感性理解一下，走回头路一定是不优的。

然后就可以 O(qn) 的贪心，每次如果不在合法区间内，就走到更近的那个区间端点。

不妨把询问分成 l<r 和 l>r 两种，后者只需要把前者反过来做就好了。于是只考虑从左往右走。

令 L_i\leftarrow L_i-i+1,R_i\leftarrow R_i-i 以忽略从 i 到 i+1 需要的 1 单位时间，并且给 R_i 额外减了 1 这样只有在区间内的位置才能走过去。

手动模拟以下这个过程，发现把整个值域从 l 到 r 的过程，一定是左右端点不断被缩减，中间的位于当前所有经过的区间交集内的位置不变；直到交集为空，整个值域被压缩成一个点。

如图，竖线为题目给的区间，横线为路径，其中红色的需要代价。在第四条竖线处，所有起点都被压缩到了一个点上。

于是可以考虑弹飞绵羊，对序列分块，修改时整块倒过来做区间加等差数列计算代价，复杂度大概是根号 log。

然后我们发现，在这个压成一个点的分界点之前的代价是好算的，就是走到区间交集；压成一个点之后的代价可以直接算这个点的走的代价。

于是我们在线段树上模拟这个过程。

2

具体地，对于节点 [L,R]，记 pos 为使得值域被压缩成一个点的位置（即区间区间 [L,pos-1] 的交集不为空，而 [L,pos] 的交集为空），[l,r] 为区间区间 [L,pos-1] 的交集，还有从 pos 走到 R 的代价，以及走完后的位置。

我们设计一个函数 calc(p,x) 为位置 p 走过 x 需要的代价，可以拆成三个部分：压缩前，从 pos-1 到 pos，压缩后，加在一起。

线段树拆出来 O(\log n) 个区间分别做这个函数，位置的变化是简单的。

于是现在只需要写出来 Pushup() 就做完这个题了。

这里我分了三类讨论：左子结点的区间交集为空（即已经能够压缩），左子结点的区间交集不为空并且左右子结点的 [l,r] 有交，左子结点的区间交集不为空并且左右子结点的 [l,r] 无交。

对于最后一种情况需要求出新的 pos，我使用了二分解决。可能有更牛的求法但是能过。

所以复杂度为 O(n\log^2n)。

3

反过来的部分把整个线段树复制了一遍，代码长度 4k。

:::info[代码]

#include<bits/stdc++.h>
constexpr int rSiz=1<<21;
char rBuf[rSiz],*p1=rBuf,*p2=rBuf;
#define gc() (p1==p2&&(p2=(p1=rBuf)+fread(rBuf,1,rSiz,stdin),p1==p2)?EOF:*p1++)
template<class T>void rd(T&x){
    char ch=gc();
    for(;ch<'0'||ch>'9';ch=gc());
    for(x=0;ch>='0'&&ch<='9';ch=gc())
        x=(x<<1)+(x<<3)+(ch^48);
}
constexpr int _=3e5+5,inf=2e9;
int n,q;
int C(int x,int l,int r){
    if(x>r)return r;
    else if(x<l)return l;
    else return x;
}
#define mid ((l+r)>>1)
struct D1{
    int a[_],b[_];
    struct node{int l,r,pos,y;long long val;}t[_<<2];
    long long calc(int p,node x){
        return std::max(p-x.r,0)+(x.pos?std::max(C(p,x.l,x.r)-b[x.pos],0):0)+x.val;
    }
    void Pup(int x,int l,int r){
        node ls=t[x<<1],rs=t[x<<1|1];
        if(ls.pos){
            t[x].l=ls.l;t[x].r=ls.r;t[x].pos=ls.pos;
            if(rs.pos)t[x].y=rs.y;
            else t[x].y=C(ls.y,rs.l,rs.r);
            t[x].val=ls.val+calc(ls.y,rs);
        }
        else if(ls.r<rs.l||ls.l>rs.r){
            t[x].l=ls.l;t[x].r=ls.r;
            for(int y=(x<<1|1),L=mid+1,R=r;;){
                if(L==R){t[x].pos=L;break;}
                if(t[y<<1].r<ls.l||t[y<<1].l>ls.r)R=(L+R)>>1,y<<=1;
                else{
                    t[x].l=std::max(t[x].l,t[y<<1].l);
                    t[x].r=std::min(t[x].r,t[y<<1].r);
                    L=((L+R)>>1)+1,y=y<<1|1;
                }
            }
            int w=C(t[x].l,a[t[x].pos],b[t[x].pos]);
            t[x].val=calc(w,rs);
            if(rs.pos)t[x].y=rs.y;
            else t[x].y=C(w,rs.l,rs.r);
        }
        else{
            t[x].l=std::max(ls.l,rs.l);
            t[x].r=std::min(ls.r,rs.r);
            t[x].pos=rs.pos;t[x].y=rs.y;t[x].val=rs.val;
        }
    }
    void Chg(int x,int l,int r,int w){
        if(l==r)return t[x]={a[w],b[w],0,0,0},void();
        if(w<=mid)Chg(x<<1,l,mid,w);
        else Chg(x<<1|1,mid+1,r,w);
        Pup(x,l,r);
    }
    int pos;long long ans;
    void Qry(int x,int l,int r,int L,int R){
        if(L<=l&&r<=R){
            ans+=calc(pos,t[x]);
            if(t[x].pos)pos=t[x].y;
            else pos=C(pos,t[x].l,t[x].r);
            return;
        }
        if(L<=mid)Qry(x<<1,l,mid,L,R);
        if(R>mid)Qry(x<<1|1,mid+1,r,L,R);
    }
    void Upd(int x,int l,int r){
        a[x]=l+n-x+1,b[x]=r+n-x;
        Chg(1,1,n,x);
    }
    long long Ask(int l,int r,int x,int y){
        x=x+n-l+1;y=y+n-r+1;
        pos=x;ans=0;
        Qry(1,1,n,l,r-1);
        return ans+std::max(pos-y,0);
    }
}D1;
struct D2{
    int a[_],b[_];
    struct node{int l,r,pos,y;long long val;}t[_<<2];
    long long calc(int p,node x){
        return std::max(p-x.r,0)+(x.pos?std::max(C(p,x.l,x.r)-b[x.pos],0):0)+x.val;
    }
    void Pup(int x,int l,int r){
        node ls=t[x<<1],rs=t[x<<1|1];
        if(ls.pos){
            t[x].l=ls.l;t[x].r=ls.r;t[x].pos=ls.pos;
            if(rs.pos)t[x].y=rs.y;
            else t[x].y=C(ls.y,rs.l,rs.r);
            t[x].val=ls.val+calc(ls.y,rs);
        }
        else if(ls.r<rs.l||ls.l>rs.r){
            t[x].l=ls.l;t[x].r=ls.r;
            for(int y=(x<<1|1),L=mid+1,R=r;;){
                if(L==R){t[x].pos=L;break;}
                if(t[y<<1].r<ls.l||t[y<<1].l>ls.r)R=(L+R)>>1,y<<=1;
                else{
                    t[x].l=std::max(t[x].l,t[y<<1].l);
                    t[x].r=std::min(t[x].r,t[y<<1].r);
                    L=((L+R)>>1)+1,y=y<<1|1;
                }
            }
            int w=C(t[x].l,a[t[x].pos],b[t[x].pos]);
            t[x].val=calc(w,rs);
            if(rs.pos)t[x].y=rs.y;
            else t[x].y=C(w,rs.l,rs.r);
        }
        else{
            t[x].l=std::max(ls.l,rs.l);
            t[x].r=std::min(ls.r,rs.r);
            t[x].pos=rs.pos;t[x].y=rs.y;t[x].val=rs.val;
        }
    }
    void Chg(int x,int l,int r,int w){
        if(l==r)return t[x]={a[w],b[w],0,0,0},void();
        if(w<=mid)Chg(x<<1,l,mid,w);
        else Chg(x<<1|1,mid+1,r,w);
        Pup(x,l,r);
    }
    int pos;long long ans;
    void Qry(int x,int l,int r,int L,int R){
        if(L<=l&&r<=R){
            ans+=calc(pos,t[x]);
            if(t[x].pos)pos=t[x].y;
            else pos=C(pos,t[x].l,t[x].r);
            return;
        }
        if(L<=mid)Qry(x<<1,l,mid,L,R);
        if(R>mid)Qry(x<<1|1,mid+1,r,L,R);
    }
    void Upd(int x,int l,int r){
        a[x]=l+n-x+1,b[x]=r+n-x;
        Chg(1,1,n,x);
    }
    long long Ask(int l,int r,int x,int y){
        x=x+n-l+1;y=y+n-r+1;
        pos=x;ans=0;
        Qry(1,1,n,l,r-1);
        return ans+std::max(pos-y,0);
    }
}D2;
int main(){
    rd(n),rd(q);
    for(int i=1,l,r;i<n;++i){
        rd(l),rd(r);
        D1.Upd(i,l,r);
        D2.Upd(n-i,l,r);
    }
    for(int op,x,y,l,r;q;--q){
        rd(op);
        if(op&1){
            rd(x),rd(l),rd(r);
            D1.Upd(x,l,r);
            D2.Upd(n-x,l,r);
        }
        else{
            rd(l),rd(x),rd(r),rd(y);
            long long ans;
            if(l==r)ans=std::max(x-y,0);
            else if(l<r)ans=D1.Ask(l,r,x,y);
            else ans=D2.Ask(n-l+1,n-r+1,x,y);
            printf("%lld\n",ans);
        }
    }
}

:::