[省选联考 2025] 推箱子

题目链接：

推箱子

题目分析：

首先根据题目的性质：ai与bi单调递增，我们可以得出，在任意时刻，箱子的相对顺序是不会改变的，即不存在某个箱子为了到达目标位置出现了跨越其他箱子的情况。
贪心的想，一定是先推时间紧迫的箱子是最优的。
那么假设现在要推第K个箱子，并且目标位置为B，需要向左推动，那么如果某些箱子会因为此次推移被移动，那么这些箱子最终的位置一定为B-k,B-k+1，…，B（其中k为会有k个箱子因为此次推移被推动）。那么k如何求出呢。
假设箱子j不会因此次推动移动，那么一定有
$po{s}_j<b_i-(i-j-1)$ 移项可得 $po{s}_j-j<b_i-i+1$
如果目标位置应向右推动，那么一定有
$po{s}_j-j>b_i-i-1$
容易发现$po{s}_j-j$一定单调不增，那么很方便就可以在线段树是二分得出那些箱子会因为此次推动而移动，具体是要维护区间最大值和区间最小值。
对于推动结束的时候，不难发现所有的被推动箱子的$po{s}_j-j$的值都变为了$b_i-i$，这个操作可以用线段树区间覆盖实现。
现在的问题是如何求出推动的时间，每个箱子的移动时间很明显为初始位置减去目标位置，对于初始位置，在我们求得推动区间后，可以通过线段树区间求和求出被推动的箱子的$po{s}_j-j$的和，由于下标是一个等差数列，我们通过等差数列求和公式就可以求出还原出$po{s}_j$的和。同样的每个箱子被推到的位置同样是一个等差数列，位置和可以通过等差数列求和公式求得。那么推动时间即为两个和的差值。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#define int long long 
using namespace std;
const int maxm=2e5+100;
struct pnode{int a,b,t,id;
}p[maxm];
int n;
bool comp(pnode f,pnode g){return f.t<g.t;
}
struct node{int maxi[maxm*4],mini[maxm*4],sum[maxm*4];int tag[maxm*4],len[maxm*4];void pushup(int o){maxi[o]=max(maxi[(o<<1)],maxi[(o<<1)|1]);mini[o]=min(mini[(o<<1)],mini[(o<<1)|1]);sum[o]=sum[(o<<1)]+sum[(o<<1)|1];}void col(int o,int val){tag[o]=maxi[o]=mini[o]=val;sum[o]=val*len[o];}void pushdown(int o){if(tag[o]!=-1){col((o<<1),tag[o]);col((o<<1)|1,tag[o]);tag[o]=-1;}}void build(int o,int l,int r){tag[o]=-1;len[o]=r-l+1;maxi[o]=mini[o]=sum[o]=0;if(l>=r){maxi[o]=mini[o]=sum[o]=p[l].a-l;return;}int mid=(l+r)>>1;build((o<<1),l,mid),build((o<<1)|1,mid+1,r);pushup(o);}void modify(int o,int l,int r,int ql,int qr,int val){if(ql<=l&&r<=qr){col(o,val);return;}pushdown(o);int mid=(l+r)>>1;if(ql<=mid) modify((o<<1),l,mid,ql,qr,val);if(qr>mid) modify((o<<1)|1,mid+1,r,ql,qr,val);pushup(o); }int getl(int o,int l,int r,int val){if(l>=r) return l;pushdown(o);int mid=(l+r)>>1;if(mini[(o<<1)|1]>=val) return getl((o<<1),l,mid,val);else return getl((o<<1)|1,mid+1,r,val); }int getr(int o,int l,int r,int val){if(l>=r) return l;pushdown(o);int mid=(l+r)>>1;if(maxi[(o<<1)]>val) return getr((o<<1),l,mid,val);else return getr((o<<1)|1,mid+1,r,val); }int asksum(int o,int l,int r,int ql,int qr){if(ql<=l&&r<=qr) return sum[o];pushdown(o);int mid=(l+r)>>1;int p1=0,p2=0;if(ql<=mid) p1=asksum((o<<1),l,mid,ql,qr);if(qr>mid) p2=asksum((o<<1)|1,mid+1,r,ql,qr);return p1+p2; } 
}st;
bool work(){scanf("%lld",&n);p[0].a=-100,p[n+1].a=1e18;for(int i=1;i<=n;i++){scanf("%lld%lld%lld",&p[i].a,&p[i].b,&p[i].t);p[i].id=i; }st.build(1,0,n+1);sort(p+1,p+n+1,comp);int nowt=0;for(int i=1;i<=n;i++){int nowpos=st.asksum(1,0,n+1,p[i].id,p[i].id)+p[i].id;//printf("%lld %lld\n",nowpos,p[i].id); if(nowpos==p[i].b){if(nowt>p[i].t) return 0;}else if(nowpos>p[i].b){int l=st.getl(1,0,n+1,p[i].b-p[i].id+1);int num=p[i].id-l-1;int sum=st.asksum(1,0,n+1,l+1,p[i].id)+(l+1+p[i].id)*(p[i].id-l)/2;nowt+=sum-(2*p[i].b-num)*(num+1)/2;//printf("L:%lld %lld %lld\n",l,num,sum); if(nowt>p[i].t) return 0;st.modify(1,0,n+1,l+1,p[i].id,p[i].b-p[i].id);}else{int r=st.getr(1,0,n+1,p[i].b-p[i].id-1);int num=r-p[i].id-1;int sum=st.asksum(1,0,n+1,p[i].id,r-1)+(p[i].id+r-1)*(r-p[i].id)/2;nowt+=(2*p[i].b+num)*(num+1)/2-sum;//printf("R:%lld %lld %lld\n",r,num,sum); if(nowt>p[i].t) return 0;st.modify(1,0,n+1,p[i].id,r-1,p[i].b-p[i].id);} }return 1; 
} 
signed main(){//freopen("1.txt","r",stdin); int c,T;scanf("%lld%lld",&c,&T);while(T--){if(work()) puts("Yes");else puts("No"); } return 0;
}