题解：P11833 [省选联考 2025] 推箱子

LastKismet · 2025-03-09 10:50:31 · 题解

做法简介

平衡树+线段树把纯暴力做法优化到单 \log。与 ODT 做法类似。

思路

首先是一个很显然的贪心，由于一个点固定后必然不会在被推动（相对位置一定），所以 t 小的先推必然最优。

最暴力的解法就是每次找一路上会碰上的所有箱子然后一起移动，显然可以卡到 O(n^2)。

然后我们考虑对这个暴力的暴力的优化：维护连续段。

之所以会这么想，显然是因为上面影响复杂度的大头就是每次要遍历后续所有箱子。这个优化看起来很对的原因是，这些箱子推完后必然变成一个连续段，并且它不会往回推，只会向前分裂然后前进。

复杂度证明

这个算法的复杂度看起来很伪，但你会发现，由于被推之后就固定，所以存在下面的性质：

1. 每个点只会（以它为其所在连续段起点）被加入连续段一次。
2. 每个点只会（以它为分裂出的第一个点）被分离连续段一次。

对于第一个性质，是因为推完一次之后，这个连续段的起点就已经固定了，并且整个段只能单向移动，所以不会被加入多次。

对于第二个性质也是类似，因为以它为首节点分裂连续段唯一的情况就是它要往后移。它显然只需要移动一次，然后就固定了。

因此，我们只需要考虑 O(\log n) 处理连续段的合并与分裂即可。

实现

基本

由于我们要维护连续段，所以我们应当给每个连续段编号，并维护一个连续段序列。

每次合并与分离时，这个序列会发生变化。所以，不管正常人会想到什么，考虑使用平衡树维护这个序列。

然后首先考虑一个连续段应当储存什么信息，你发现，你需要知道这个连续段内所有箱子的编号与坐标。

然后你发现这是一个连续段，所以你只需要考虑维护左右端点的位置信息与节点编号即可。之所以一起维护左右两侧是因为要支持可能来自两侧的合并。

为了方便，我们显然要维护尽量少的信息，这里我考虑的是维护左端点编号与左右端点位置。

操作

我们从头开始模拟推一个箱子的过程。

找所在连续段

你显然可以在平衡树上二分来解决这个问题，但考场的时候显然需要越快越好，所以我的考场代码中额外维护了一棵线段树，来支持区间修改与单点查询……

分裂

假如当前点不是所在连续段的第一个点，那么就应当分裂这个连续段。

看到分裂，又看到平衡树，也许你会想到在平衡树上直接分裂节点。但，我的平衡树里维护的是连续段编号序列而不是箱子。

所以我们新建一个节点，更新原连续段与新连续段的信息。

这里多说一句，如果你每次都给一个新编号的话，那么总节点数也就是 2n，但我考场上显然没有想这么多，所以回收利用了废弃编号，使节点数卡死在 n。

好然后考虑把这个点插入到序列中去。

我的平衡树写的是 FHQ-Treap，想必各位也许有更简洁的办法实现把某个节点插入到某个节点的后面，但我的实现是：

获取原来连续段所在的 rnk，然后以这个 rnk 为边界把整个序列分成两截，然后把新节点放到中间，重新 merge 成一个序列。

好，那么我们就分裂出了一个连续段。

移动

从这个点开始暴力往后移……

我们首先获取新连续段的 rnk，然后从这个 rnk 开始往边界移动（看你往哪里移），然后一路上暴力合并遇到的连续段，不用合并了就停止。

至于如何遍历，我们遍历 rnk，然后 getval 即可获取当前连续段的编号。O(\log n)，合理。

合并

考虑记录下最后一个需要合并的节点，然后更新新的连续段的信息。

新的连续段一侧位置显然就是 b_i，另一侧，可以根据最后的连续段到新连续段的所有节点总数得到。考虑编号连续的性质，我们只需要获取最后连续段最后节点的编号，即可得知有多少节点。

然后如何合并呢，我们直接把新节点的后一个节点到最后一个要被合并的节点在序列里删除即可。

然后我们原来新建的连续段就代表了合并完的连续段。

然后在线段树里区间覆盖一下。。。（好蠢）

获取耗时

你发现我们是暴力遍历可以被移动的连续段，所以就每到一个连续段，如果要被移动，更新一遍答案即可。

首先我们可以知道当前连续段应当去往的位置，然后把首节点的移动乘以这个段的长度即可。每个节点移动的步数都是一样的。

代码

主要代码

void solve(){
    cin>>n;
    seg.build();fre.clear();
    rep(i,1,n)cin>>bs[i].a>>bs[i].b>>bs[i].t;
    sort(bs+1,bs+1+n,[](box a,box b){return a.a<b.a;});
    rep(i,1,n)trn[i]=i;
    sort(trn+1,trn+1+n,[&](int a,int b){return bs[a].t<bs[b].t;});
    rep(i,1,n)qs[i].l=qs[i].r=bs[i].a,qs[i].lid=i;
    rep(i,1,n)fhq.newnode(i,i);
    root=0;
    rep(i,1,n)root=fhq.merge(root,i);
    tim=0;
    rep(i,1,n){
        int now=trn[i];
        int nqj=seg.query(now);
        if(bs[now].b<qs[nqj].l+now-qs[nqj].lid){
            int x;
            int rt1,rt2,rt3;
            if(qs[nqj].lid+qs[nqj].r-qs[nqj].l-now>0){
                x=fre.back();fre.pop_back();
                fhq.newnode(x,x);
                qs[x].l=qs[nqj].l,qs[x].r=qs[nqj].l+now-qs[nqj].lid,qs[x].lid=qs[nqj].lid;
                qs[nqj].l=qs[x].r+1;qs[nqj].lid=now+1;
                fhq.split(root,fhq.rank(nqj)-1,rt1,rt2);
                root=fhq.merge(fhq.merge(rt1,x),rt2);
            }else x=nqj;
            int rnk=fhq.rank(x);
            int lb=bs[now].b-(qs[x].r-qs[x].l),lst=rnk;
            tim+=ll(qs[x].r-bs[now].b)*(qs[x].r-qs[x].l+1);
            per(i,lst-1,1){
                int j=fhq.getval(root,i);
                if(qs[j].r>=lb){
                    tim+=ll(qs[j].r-(lb-1))*(qs[j].r-qs[j].l+1);
                    lb-=qs[j].r-qs[j].l+1;
                    lst=i;
                    fre.pub(j);
                }else break;
            }
            int y=fhq.getval(root,lst);
            if(lst<rnk){
                fhq.split(root,rnk-1,rt1,rt3);
                fhq.split(rt1,lst-1,rt1,rt2);
                root=fhq.merge(rt1,rt3);
            }
            qs[x].l=bs[now].b-(now-qs[y].lid);qs[x].r=bs[now].b;qs[x].lid=qs[y].lid;
            seg.change(qs[x].lid,qs[x].lid+qs[x].r-qs[x].l,x);
        }else if(bs[now].b>qs[nqj].l+now-qs[nqj].lid){
            int x;
            int rt1,rt2,rt3;
            if(now-qs[nqj].lid>0){
                x=fre.back();fre.pop_back();
                fhq.newnode(x,x);
                qs[x].l=qs[nqj].l+now-qs[nqj].lid,qs[x].r=qs[nqj].r,qs[x].lid=now;
                qs[nqj].r=qs[x].l-1;
                fhq.split(root,fhq.rank(nqj),rt1,rt2);
                root=fhq.merge(fhq.merge(rt1,x),rt2);
            }else x=nqj;
            int rnk=fhq.rank(x);
            int rb=bs[now].b+qs[x].r-qs[x].l,lst=rnk;
            tim+=ll(bs[now].b-qs[x].l)*(qs[x].r-qs[x].l+1);
            rep(i,lst+1,fhq.ns[root].siz){
                int j=fhq.getval(root,i);
                if(qs[j].l<=rb){
                    tim+=ll(rb+1-qs[j].l)*(qs[j].r-qs[j].l+1);
                    rb+=qs[j].r-qs[j].l+1;
                    lst=i;
                    fre.pub(j);
                }else break;
            }
            int y=fhq.getval(root,lst);
            if(lst>rnk){
                fhq.split(root,rnk,rt1,rt2);
                fhq.split(rt2,lst-rnk,rt2,rt3);
                root=fhq.merge(rt1,rt3);
            }
            qs[x].r=bs[now].b+(qs[y].lid+qs[y].r-qs[y].l-now);qs[x].l=bs[now].b;
            seg.change(qs[x].lid,qs[x].lid+qs[x].r-qs[x].l,x);
        }
        if(tim>bs[now].t){
            cout<<"No\n";
            return;
        }
    }
    cout<<"Yes\n";
}

完整代码

#include<bits/stdc++.h>
using namespace std;

#define rep(i,x,y) for(int i=(x);i<=(y);i++)
#define repl(i,x,y) for(int i=(x);i<(y);i++)
#define per(i,x,y) for(int i=(x);i>=(y);i--)
#define pub push_back
#define fir first
#define sec second
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
typedef pair<ll,ll> pll;
template<typename T>
using vec=vector<T>;
template<typename T>
using grheap=priority_queue<T>;
template<typename T>
using lrheap=priority_queue<T,vector<T>,greater<T>>;
#define file(s) freopen(#s".in","r",stdin);freopen(#s".out","w",stdout)

const int N=2e5+5;

mt19937 rnd(time(0));

int n;
ll tim;
struct box{
    ll a,b,t;
}bs[N];
int trn[N];

int root;
struct FHQ{
    struct node{
        int pri,val;
        int fa;
        int lson,rson;
        int siz;
    }ns[N];
    void update(int x){
        if(ns[x].lson)ns[ns[x].lson].fa=x;
        if(ns[x].rson)ns[ns[x].rson].fa=x;
        ns[x].siz=ns[ns[x].lson].siz+1+ns[ns[x].rson].siz;
    }
    int newnode(int x,int val){
        ns[x].pri=rnd();
        ns[x].val=val;
        ns[x].siz=1;
        ns[x].fa=ns[x].lson=ns[x].rson=0;
        return x;
    }
    int merge(int a,int b){
        if(!a)return b;
        if(!b)return a;
        if(ns[a].pri>ns[b].pri){
            ns[a].rson=merge(ns[a].rson,b);
            update(a);
            return a;
        }else{
            ns[b].lson=merge(a,ns[b].lson);
            update(b);
            return b;
        }
    }
    void split(int x,int k,int &rt1,int &rt2){
        if(!x){
            rt1=rt2=0;
            return;
        }
        if(ns[ns[x].lson].siz>=k){
            split(ns[x].lson,k,rt1,ns[x].lson);
            ns[rt1].fa=0;
            rt2=x;
        }else{
            split(ns[x].rson,k-ns[ns[x].lson].siz-1,ns[x].rson,rt2);
            ns[rt2].fa=0;
            rt1=x;
        }
        update(x);
    }
    int getval(int x,int k){
        if(ns[ns[x].lson].siz>=k)return getval(ns[x].lson,k);
        else if(ns[ns[x].lson].siz==k-1)return ns[x].val;
        else return getval(ns[x].rson,k-ns[ns[x].lson].siz-1);
    }
    int rank(int x){
        int res=ns[ns[x].lson].siz+1;
        while(ns[x].fa){
            if(x==ns[ns[x].fa].rson)res+=ns[ns[ns[x].fa].lson].siz+1;
            x=ns[x].fa;
        }
        return res;
    }
}fhq;

struct segment{
    int dat[N<<2],laz[N<<2];
    void pushdown(int x){
        if(!laz[x])return;
        dat[x<<1]=dat[x<<1|1]=laz[x];
        laz[x<<1]=laz[x<<1|1]=laz[x];
        laz[x]=0;
    }
    void build(int x=1,int l=1,int r=n){
        laz[x]=0;
        if(l==r){
            dat[x]=l;
            return;
        }
        int m=l+r>>1;
        build(x<<1,l,m);
        build(x<<1|1,m+1,r);
    }
    void change(int lq,int rq,int v,int x=1,int l=1,int r=n){
        if(lq<=l&&r<=rq){
            dat[x]=laz[x]=v;
            return;
        }
        int m=l+r>>1;
        pushdown(x);
        if(lq<=m)change(lq,rq,v,x<<1,l,m);
        if(m<rq)change(lq,rq,v,x<<1|1,m+1,r);
    }
    int query(int k,int x=1,int l=1,int r=n){
        if(l==r)return dat[x];
        int m=l+r>>1;
        pushdown(x);
        if(k<=m)return query(k,x<<1,l,m);
        else return query(k,x<<1|1,m+1,r); 
    }
}seg;

struct qj{
    int l,r;
    int lid;
}qs[N];
vec<int> fre;

void solve(){
    cin>>n;
    seg.build();fre.clear();
    rep(i,1,n)cin>>bs[i].a>>bs[i].b>>bs[i].t;
    sort(bs+1,bs+1+n,[](box a,box b){return a.a<b.a;});
    rep(i,1,n)trn[i]=i;
    sort(trn+1,trn+1+n,[&](int a,int b){return bs[a].t<bs[b].t;});
    rep(i,1,n)qs[i].l=qs[i].r=bs[i].a,qs[i].lid=i;
    rep(i,1,n)fhq.newnode(i,i);
    root=0;
    rep(i,1,n)root=fhq.merge(root,i);
    tim=0;
    rep(i,1,n){
        int now=trn[i];
        int nqj=seg.query(now);
        if(bs[now].b<qs[nqj].l+now-qs[nqj].lid){
            int x;
            int rt1,rt2,rt3;
            if(qs[nqj].lid+qs[nqj].r-qs[nqj].l-now>0){
                x=fre.back();fre.pop_back();
                fhq.newnode(x,x);
                qs[x].l=qs[nqj].l,qs[x].r=qs[nqj].l+now-qs[nqj].lid,qs[x].lid=qs[nqj].lid;
                qs[nqj].l=qs[x].r+1;qs[nqj].lid=now+1;
                fhq.split(root,fhq.rank(nqj)-1,rt1,rt2);
                root=fhq.merge(fhq.merge(rt1,x),rt2);
            }else x=nqj;
            int rnk=fhq.rank(x);
            int lb=bs[now].b-(qs[x].r-qs[x].l),lst=rnk;
            tim+=ll(qs[x].r-bs[now].b)*(qs[x].r-qs[x].l+1);
            per(i,lst-1,1){
                int j=fhq.getval(root,i);
                if(qs[j].r>=lb){
                    tim+=ll(qs[j].r-(lb-1))*(qs[j].r-qs[j].l+1);
                    lb-=qs[j].r-qs[j].l+1;
                    lst=i;
                    fre.pub(j);
                }else break;
            }
            int y=fhq.getval(root,lst);
            if(lst<rnk){
                fhq.split(root,rnk-1,rt1,rt3);
                fhq.split(rt1,lst-1,rt1,rt2);
                root=fhq.merge(rt1,rt3);
            }
            qs[x].l=bs[now].b-(now-qs[y].lid);qs[x].r=bs[now].b;qs[x].lid=qs[y].lid;
            seg.change(qs[x].lid,qs[x].lid+qs[x].r-qs[x].l,x);
        }else if(bs[now].b>qs[nqj].l+now-qs[nqj].lid){
            int x;
            int rt1,rt2,rt3;
            if(now-qs[nqj].lid>0){
                x=fre.back();fre.pop_back();
                fhq.newnode(x,x);
                qs[x].l=qs[nqj].l+now-qs[nqj].lid,qs[x].r=qs[nqj].r,qs[x].lid=now;
                qs[nqj].r=qs[x].l-1;
                fhq.split(root,fhq.rank(nqj),rt1,rt2);
                root=fhq.merge(fhq.merge(rt1,x),rt2);
            }else x=nqj;
            int rnk=fhq.rank(x);
            int rb=bs[now].b+qs[x].r-qs[x].l,lst=rnk;
            tim+=ll(bs[now].b-qs[x].l)*(qs[x].r-qs[x].l+1);
            rep(i,lst+1,fhq.ns[root].siz){
                int j=fhq.getval(root,i);
                if(qs[j].l<=rb){
                    tim+=ll(rb+1-qs[j].l)*(qs[j].r-qs[j].l+1);
                    rb+=qs[j].r-qs[j].l+1;
                    lst=i;
                    fre.pub(j);
                }else break;
            }
            int y=fhq.getval(root,lst);
            if(lst>rnk){
                fhq.split(root,rnk,rt1,rt2);
                fhq.split(rt2,lst-rnk,rt2,rt3);
                root=fhq.merge(rt1,rt3);
            }
            qs[x].r=bs[now].b+(qs[y].lid+qs[y].r-qs[y].l-now);qs[x].l=bs[now].b;
            seg.change(qs[x].lid,qs[x].lid+qs[x].r-qs[x].l,x);
        }
        if(tim>bs[now].t){
            cout<<"No\n";
            return;
        }
    }
    cout<<"Yes\n";
}

int main(){
    // file(move);
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int c,t;cin>>c>>t;
    while(t--)solve();
    return 0;
}