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

· · 题解

大力宣传除了排序外线性做法！不用线段树等高级 ds！

首先注意到特殊性质 a_i<b_i，推一下可以发现可以按 [a_i<b_i] 把序列剖成若干连续段，每一段几乎是独立的，相当于这个特殊性质和题目等价。理由是若 a_i<b_i<b_{i+1}<a_{i+1} 或 b_i<a_{i}<a_{i+1}<b_{i+1} 的时候两边推的过程不会相交。

显然可以按 t 排序。可以只考虑每个特殊 T 时刻的时候所有箱子的位置 c_i，如果有 c_i 递增且 \sum|a_i-c_i|\le T，则显然存在一个推箱子的方案。所以我们直接考虑每个特殊时刻需要移动所有箱子的总距离。为了让上面的东西独立，我们对每个连续段设计若干个限制：二元组序列 \{(t_i,d_i)\} 表示 t_i 时刻前这一段需要做 d_i 个操作。

考虑 T 时刻内所有需要归位的箱子为集合 S。不妨设本段 a_i<b_i。设 x,y 是 S 中两个相邻的元素，可以认为 [x,y-1] 之间的箱子都只受 x 影响。可以发现 x 影响的箱子一定是这个区间的一段长度为 l 的前缀，如果可以求出这段前缀，就可以推出这一段箱子在时间内最终位置是 b_x,b_{x}+1,\dots,b_x+l-1。此时贡献的计算关于所有相邻的 (x,y) 对独立。直接把 \sum_{i=0}^{l-1} b_x+i-a_{i+x} 加起来就可以得到此时的 d_i 了。暴力做得到平方做法。

上面这个东西也可以理解为，我们从右往左依次移动，把 y 移动好了之后，x 要考虑的就只有 <y 的了。

这个东西是很好优化到线性的。从小到大枚举 t，受影响的相邻对 (x,y) 最多只会有两次变化：一次是加入一个新点，直接算一下这个点和它下一个点之间的贡献；再修改一下它和上一个点之间的贡献即可。

考虑如何快速求出上面说的一段前缀。箱子 i 受 x 的影响当且仅当 b_x+(i-x)\ge a_i，移项得到 a_i-i\le b_x-x。注意到 a_i 严格递增，所以 {a_i-i} 不降，在一开始直接预处理出最大的 f_x=i 表示 i 会受 x 影响。算贡献的时候相当于 [x,\min(y-1,f_x)] 的箱子会受影响，预处理 a 的前缀和容易 O(1) 计算贡献。

插入一个点之后求出上一个和下一个点也可以单调栈预处理，就做到了线性处理一个段（除了按 t 排序）。

考虑合并若干个段的限制。我们不妨认为一个点可以做多次操作。设限制序列中相邻两项 (t_{i-1},d_{i-1}),(t_i,d_i)，说人话就是认为在 t_i 时刻做 d_i-d_{i-1} 次操作。所以直接把 (t_i,d_i-d_{i-1}) 放到一起排序，然后再整体考虑 t_i 时间前是否做得完前 \sum_{j\le i}d_j 次操作，即判断 \forall i, \sum_{j\le i}d_j\le t_i。

总时间复杂度除了排序外线性。非常好写。

考场代码：

#include<bits/stdc++.h>
#define MOD 998244353
#define int long long
#define REP(i,a,n) for(int i=a;i<(int)(n);++i)
#define pii pair<int,int>
#define pb push_back
#define all(v) v.begin(),v.end()
using namespace std;
int read(){
    int res=0;char c=getchar();
    while(c<48||c>57)c=getchar();
    do res=(res<<1)+(res<<3)+(c^48),c=getchar();while(c>=48&&c<=57);
    return res;
}
int qpow(int a,int b,int m=MOD){
    int res=1;
    while(b)res=b&1? res*a%MOD:res,a=a*a%MOD,b>>=1;
    return res;
}
struct boxes{
    int a,b,t;
};
int ID;
vector<pii>solve(vector<boxes>a){
    int n=a.size();
    if(a[0].a>a[0].b){
        REP(i,0,n)a[i].a*=-1,a[i].b*=-1;
        reverse(all(a));
    }
    vector<pii>st;
    REP(i,0,n)st.pb({a[i].t,i});
    sort(all(st));
    vector<int>nxt(n);
    int x=0;
    REP(i,0,n){
        while(x+1<n&&a[x+1].a-(x+1)<a[i].b-i)++x;
        nxt[i]=x;
    }
    vector<int>s(n+1,0);
    REP(i,0,n)s[i+1]=s[i]+a[i].a;
    vector<int>f1(n,n),f2(n,-1);
    stack<int>S;
    REP(i,0,n){
        while(!S.empty()&&a[S.top()].t>a[i].t)S.pop();
        f1[i]=S.empty()? -1:S.top();
        S.push(i);
    }
    while(!S.empty())S.pop();
    for(int i=n-1;i>=0;--i){
        while(!S.empty()&&a[S.top()].t>=a[i].t)S.pop();
        f2[i]=S.empty()? n:S.top();
        S.push(i);
    }
    vector<pii>ret;
    int cur=0;
    REP(_,0,st.size()){
        int i=st[_].second,T=st[_].first;
        nxt[i]=min(nxt[i],f2[i]-1);
        cur+=(a[i].b*2+nxt[i]-i)*(nxt[i]-i+1)/2-s[nxt[i]+1]+s[i];
        if(f1[i]!=-1){
            int x=f1[i];
            if(nxt[x]>=i){
                cur-=(a[x].b*2+nxt[x]-x)*(nxt[x]-x+1)/2-s[nxt[x]+1]+s[x];
                nxt[x]=i-1;
                cur+=(a[x].b*2+nxt[x]-x)*(nxt[x]-x+1)/2-s[nxt[x]+1]+s[x];
            }
        }
        ret.pb({T,cur});
    }
    return ret;
}
int n;
int a[200005],b[200005],t[200005];
void Main(){
    n=read();
    REP(i,0,n)a[i]=read(),b[i]=read(),t[i]=read();
    vector<pii>R;
    vector<int>v;
    REP(i,0,n)if(a[i]!=b[i]){
        int x=i;
        while(x+1<n&&(a[x+1]<b[x+1])==(a[x]<b[x]))++x;
        vector<boxes>T;
        REP(j,i,x+1)T.pb({a[j],b[j],t[j]});
        vector<pii>s=solve(T);
        for(int j=s.size()-1;j;--j)s[j].second-=s[j-1].second;
        for(auto j:s)R.pb(j);
        i=x;
    }
    sort(all(R));
    REP(i,1,R.size())R[i].second+=R[i-1].second;
    REP(i,0,R.size())if(R[i].second>R[i].first){
        cout<<"No\n";
        return;
    }
    cout<<"Yes\n";
}
signed main(){
    freopen("move.in","r",stdin);
    freopen("move.out","w",stdout);
    int tc=1;
    ID=read();tc=read();
    while(tc--)Main();
    return 0;
}