[省选联考 2025] 推箱子

zhangchengxiao LV 8 @ 2025-10-10 12:48:54

逆天 $O(N \sqrt{N} \log N)$ 可过

#include <bits/stdc++.h>
using namespace std;
#define mem(a, b) memset(a, b, sizeof(a))
#define int long long int
const int N = 2e5 + 5;
int c, T, a[N], b[N], t[N], n;
struct node { int i, b, t; } x[N];
int sumseq(int x, int l) { return (x + l - 1 + x) * l / 2; }

namespace blo {
    constexpr int SIZ = 150;
    int id[N], st[N], siz[N], tot, a[N], sum[N], tag[N];
    void init_id() {
        tot = 0;
        for (int i = 1; i <= n; ) {
            st[++tot] = i, tag[tot] = -1, sum[tot] = siz[tot] = 0;
            for (int j = 1; j <= SIZ && i <= n; j++, i++)
                id[i] = tot, sum[tot] += a[i], siz[tot]++;
        }
        // cout << "id: "; for (int i = 1; i <= n; i++) cout << id[i] << ' '; cout << '\n';
        // cout << "sum: "; for (int i = 1; i <= tot; i++) cout << sum[i] << ' '; cout << '\n';
    }
    void pushdown(int t) {
        if (tag[t] == -1) return;
        sum[t] = sumseq(tag[t], siz[t]);
        for (int i = st[t]; i <= st[t] + siz[t] - 1; i++) a[i] = tag[t]++;
        tag[t] = -1;
    }
    void update(int x, int l, int r) { // 将区间[l,r]修改为首项为x,公差为1的等差数列
        if (r < l) return;
        int lid = id[l], rid = id[r];
        pushdown(lid), pushdown(rid);
        if (lid == rid) {
            for (int i = l; i <= r; i++) sum[lid] += x - a[i], a[i] = x++;
            return;
        }
        for (int i = l; id[i] == lid; i++) sum[lid] += x - a[i], a[i] = x++;
        for (int t = lid + 1; t < rid; t++) tag[t] = x, sum[t] = sumseq(x, siz[t]), x += siz[t];
        for (int i = st[rid]; i <= r; i++) sum[rid] += x - a[i], a[i] = x++;
    }
    int query(int l, int r) {
        if (r < l) return 0;
        int lid = id[l], rid = id[r], res = 0;
        pushdown(lid), pushdown(rid);
        if (lid == rid) {
            for (int i = l; i <= r; i++) res += a[i];
            return res;
        }
        for (int i = l; id[i] == lid; i++) res += a[i];
        for (int t = lid + 1; t < rid; t++) res += sum[t];
        for (int i = r; id[i] == rid; i--) res += a[i];
        return res;
    }
    int find_last_le(int i, int b) { // 区间i~n，找到最后一个j满足a[j] < b[i] + (j - i)
        int l = 1, r = n;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            pushdown(id[mid]);
            if (a[mid] < b + (mid - i)) l = mid;
            else r = mid - 1;
        }
        return l;
    }
    int find_first_ge(int i, int b) { // 区间1~i，找到第一个j满足a[j] > b[i] - (i - j)
        int l = 1, r = n;
        while (l < r) {
            int mid = l + r >> 1;
            pushdown(id[mid]);
            if (a[mid] > b - (i - mid)) r = mid;
            else l = mid + 1;
        }
        return r;
    }
}
bool solve() {
    for (int i = 1; i <= n; i++) x[i] = {i, b[i], t[i]};
    sort(x + 1, x + n + 1, [](node a, node b) { return a.t < b.t; });
    for (int i = 1; i <= n; i++) blo::a[i] = a[i];
    blo::init_id();
    int tick = 0;
    for (int k = 1; k <= n; k++) {
        int i = x[k].i;
        a[i] = blo::query(i, i), b[i] = x[k].b;
        if (a[i] < b[i]) {
            int j = blo::find_last_le(i, b[i]);
            tick += sumseq(b[i], j - i + 1) - blo::query(i, j);
            blo::update(b[i], i, j);
        } else if (a[i] > b[i]) {
            int j = blo::find_first_ge(i, b[i]);
            tick += blo::query(j, i) - sumseq(b[i] - (i - j), i - j + 1);
            blo::update(b[i] - (i - j), j, i);
        }
        if (x[k].t < tick) return 0;
    }
    return 1;
}
main() {
    // freopen("move2.in", "r", stdin), freopen(".out", "w", stdout);
    ios::sync_with_stdio(0), cin.tie(0);
    for (cin >> c >> T; T; T--) {
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> t[i];
        cout << (solve() ? "Yes" : "No") << '\n';
    }
    return 0;
}

0
admin LV 10 SU @ 2026-5-12 0:27:30
P11833 [省选联考 2025] 推箱子题解

考完出来对答案，发现学校里就我一人用线段树做的这一题，记录一下。

upd 2025.3.5：修改了一点笔误，望管理员看到给通过一下。

upd 2025.3.8：发现原来式子锅了，改了，望通过。

思路

首先是基本的贪心思路：把所有限制按照时间从小到大排序，然后一个一个推一定不劣。证明是简单的，只需要考虑交换相邻顺序即可。

然后模拟这个过程，发现一定是把一段连续的箱子推到一段连续的位置上。如何计算所需的时间呢？我们不妨令 $pos_i$ 表示第 $i$ 个箱子现在所在的位置，假设我们现在要把第 $i$ 个箱子推到 $b_i$ 上，那么我们就有如下讨论：
- 如果 $pos_i=b_i$ ，那还推啥，无需花时间。
- 如果 $pos_i>b_i$ ，那么我们就需要把 $i$ 号箱子往左推，推到位置 $b_i$ ，中间碰到的箱子要一起推过去。所花的时间等于初始时所有移动了的箱子的位置之和减去最终箱子停下来的位置之和。
- 如果 $pos_i<b_i$ ，那么我们就需要把 $i$ 号箱子向右推，推到位置 $b_i$ ，中间碰到的箱子要一起推过去。所花的时间等于最终箱子停下来的位置之和减去初始时所有移动了的箱子的位置之和。
对于第二种情况来说，假设箱子 $j$ 不会在箱子 $i$ 被推到位时被推动（且 $j<i$ ），则一定有：
$pos_j<b_i-(i-j-1)$
这里的 $b_i-(i-j-1)$ 其实是假定 $j+1$ 到 $i$ 号箱子都被推动了时，连续的那一段位置的左端点是多少。我们给上式移一下项，就能得到：
$pos_j-j<b_i-i+1$
对于第三种情况来说，假设箱子 $j$ 不会在箱子 $i$ 被推到位时被推动（且 $i<j$ ），则一定有：
$pos_j>b_i+(j-i-1)$ $pos_j-j>b_i-i-1$
推得的方式与第二种情况类似。

不难发现， $pos_j-j$ 的值一定单调不降，把该值上线段树上二分就能够知道有那些箱子是会被移动的。我们额外维护出所有被移动了的箱子的位置之和就能够计算本次移动所消耗的时间。

现在问题出在如何在移动后更新 $pos_j-j$ 的值。由于所有被移动的箱子的 $pos$ 都会变相邻，而被移动的箱子的下标又一定相邻，所以所有被移动的箱子的 $pos_j-j$ 的值一定相等，线段树区间赋值成 $b_i-i$ 即可。

单次推一个箱子需要线段树二分加上区间赋值，则总时间复杂度为 $O(Tn\log n)$ 。

代码

这份代码通过了考场上所有的大样例（虽然这题的大样例有点水就是了）。
```
#include <iostream>
#include <algorithm>
#define ll long long
#define lc (x<<1)
#define rc ((x<<1)|1)
#define mid ((l+r)>>1)
using namespace std;
const ll N=2e5+10;
const ll V=1e9+10;
struct node{
	ll a,b,t,id;
}bl[N];
inline bool cmp(node x,node y){return x.t<y.t;}
ll n,sum[N<<2],tag[N<<2],minn[N<<2],maxx[N<<2];
void push_up(ll x){
	sum[x]=sum[lc]+sum[rc];
	minn[x]=min(minn[lc],minn[rc]);
	maxx[x]=max(maxx[lc],maxx[rc]);
}
void push_down(ll x,ll l,ll r){
	if(tag[x]==-114514) return;
	tag[lc]=tag[rc]=tag[x];
	minn[lc]=minn[rc]=tag[x];
	maxx[lc]=maxx[rc]=tag[x];
	sum[lc]=tag[x]*(mid-l+1);
	sum[rc]=tag[x]*(r-mid);
	tag[x]=-114514;
}
void build(ll x,ll l,ll r){
	tag[x]=-114514;
	if(l==r){
		if(!l) sum[x]=minn[x]=maxx[x]=-114;
		else if(l>n) sum[x]=minn[x]=maxx[x]=V;
		else sum[x]=minn[x]=maxx[x]=bl[l].a-l;
		return;
	}
	build(lc,l,mid);build(rc,mid+1,r);
	push_up(x);
}
void chg(ll x,ll l,ll r,ll L,ll R,ll v){
	if(L<=l&&r<=R){
		sum[x]=v*(r-l+1);
		tag[x]=maxx[x]=minn[x]=v;
		return;
	}
	push_down(x,l,r);
	if(L<=mid) chg(lc,l,mid,L,R,v);
	if(R>mid) chg(rc,mid+1,r,L,R,v);
	push_up(x);
}
ll getMD(ll x,ll l,ll r,ll rank){
	if(l==r) return l;
	push_down(x,l,r);
	if(rank<=minn[rc]) return getMD(lc,l,mid,rank);
	return getMD(rc,mid+1,r,rank);
}
ll getOT(ll x,ll l,ll r,ll rank){
	if(l==r) return l;
	push_down(x,l,r);
	if(rank<maxx[lc]) return getOT(lc,l,mid,rank);
	return getOT(rc,mid+1,r,rank);
}
ll query(ll x,ll l,ll r,ll L,ll R){
	if(L<=l&&r<=R) return sum[x];
	push_down(x,l,r);
	ll ret=0;
	if(L<=mid) ret+=query(lc,l,mid,L,R);
	if(R>mid) ret+=query(rc,mid+1,r,L,R);
	return ret;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	ll c,T;cin>>c>>T;
	while(T--){
		cin>>n;
		for(ll i=1;i<=n;i++){cin>>bl[i].a>>bl[i].b>>bl[i].t;bl[i].id=i;}
		build(1,0,n+1);
		sort(bl+1,bl+1+n,cmp);
		ll now=0;
		for(ll i=1;i<=n;i++){
			ll pos=query(1,0,n+1,bl[i].id,bl[i].id)+bl[i].id;
			if(pos==bl[i].b){
				if(now>bl[i].t) goto endthesol;
				continue;
			}
			ll L,R,calc;
			if(pos>bl[i].b){
				L=getMD(1,0,n+1,bl[i].b-bl[i].id+1);
				R=bl[i].id-L-1;
				calc=query(1,0,n+1,L+1,bl[i].id)+(L+1+bl[i].id)*(bl[i].id-L)/2;
				now+=calc-(2*bl[i].b-R)*(R+1)/2;
				if(now>bl[i].t) goto endthesol;
				chg(1,0,n+1,L+1,bl[i].id,bl[i].b-bl[i].id);
			}
			else{
				L=getOT(1,0,n+1,bl[i].b-bl[i].id-1);
				R=L-bl[i].id-1;
				calc=query(1,0,n+1,bl[i].id,L-1)+(bl[i].id+L-1)*(L-bl[i].id)/2;
				now+=(2*bl[i].b+R)*(R+1)/2-calc;
				if(now>bl[i].t) goto endthesol;
				chg(1,0,n+1,bl[i].id,L-1,bl[i].b-bl[i].id);
			}
		}
		cout<<"Yes\n";
		continue;
		endthesol:;
		cout<<"No\n";
	}
	return 0;
} 
```

ID

2348

时间

2000ms

内存

512MiB

难度

标签

递交数

已通过

上传者

Hydro

2 条题解

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

思路

代码

信息

状态

开发

支持

关于

2 条题解

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

思路

代码

[省选联考 2025] 推箱子

信息

状态

开发

支持

关于

还没有账户？

登录

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