自动搬运

查看原文

来自洛谷，原作者为

	jinminghao 1e18

搬运于2025-08-24 23:17:13，当前版本为作者最后更新于2025-06-15 14:21:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先，我们发现在线去找每个人能够拿到和掉在地上的烤肉比较难实现，所以我们可以把每个询问离线下来，然后枚举所有的烤肉，把每一块烤肉分给某个人。

对于第 $i$ 块烤肉，我们需要找出一个人，使这个人的任意一个签子与这块肉产生交集，且这个人在所有签子与这块肉产生交集的人中访问时间最早。

我们先把 $a$ 数组与 $b$ 数组分别从小到大排序，当我们枚举到第 $i$ 块烤肉时，我们分别二分出 $a$ 数组和 $b$ 数组第一个大于等于 $s_i$ 且 小于 $e_i$ 的位置，这样我们对于 $a$ 数组和 $b$ 数组分别得到两个区间，紧接着我们求出这两个区间中编号（指排队领肉的顺序）最小的数的编号就是这块肉被谁叉走的，最后我们再判断一下这个人能不能叉走这块肉就行。

代码：

#include<cstdio>
#include<algorithm>
#include<cmath>
#define min(a,b) (a<b?a:b)
#define int long long
using namespace std;
const int N=3e5+10;
struct Node{
	int val,id;
	bool operator<(const Node &x)const{
		return val<x.val;
	}
}a[N],b[N];
int s[N],e[N],w[N],ans[N],sl1[N],sl2[N],st1[N][20],st2[N][20],n,m;
void init(int (&st)[N][20]){
	for(int j=1;(1<<j)<=m;j++){
		for(int i=1;i<=m-(1<<j)+1;i++){
			st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);
		}
	}
}
int query(int l,int r,int (&st)[N][20]){
	if(l>r) swap(l,r);
	int k=log2(r-l+1);
	return min(st[l][k],st[r-(1<<k)+1][k]);
}
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld%lld",&s[i],&e[i],&w[i]);
	}
	for(int i=1;i<=m;i++){
		scanf("%lld%lld",&a[i].val,&b[i].val);
		a[i].id=b[i].id=i;
	}
	sort(a+1,a+m+1);
	sort(b+1,b+m+1);
	for(int i=1;i<=m;i++){
		st1[i][0]=a[i].id;
		st2[i][0]=b[i].id;
		sl1[a[i].id]=i;
		sl2[b[i].id]=i;
	}
	init(st1);
	init(st2);
	for(int i=1;i<=n;i++){
		if(s[i]>e[i]) swap(s[i],e[i]);
		int l=1,r=m,res1=-1;
		while(l<=r){
			int mid=l+r>>1;
			if(s[i]<=a[mid].val&&a[mid].val+1<=e[i]){
				res1=mid;
				r=mid-1;
			}else if(a[mid].val<s[i]){
				l=mid+1;
			}else{
				r=mid-1;
			}
		}
		l=1,r=m;
		int res2=-1;
		while(l<=r){
			int mid=l+r>>1;
			if(s[i]<=a[mid].val&&a[mid].val+1<=e[i]){
				res2=mid;
				l=mid+1;
			}else if(a[mid].val<s[i]){
				l=mid+1;
			}else{
				r=mid-1;
			}
		}
		l=1,r=m;
		int ret1=-1;
		while(l<=r){
			int mid=l+r>>1;
			if(s[i]<=b[mid].val&&b[mid].val+1<=e[i]){
				ret1=mid;
				r=mid-1;
			}else if(b[mid].val<s[i]){
				l=mid+1;
			}else{
				r=mid-1;
			}
		}
		l=1,r=m;
		int ret2=-1;
		while(l<=r){
			int mid=l+r>>1;
			if(s[i]<=b[mid].val&&b[mid].val+1<=e[i]){
				ret2=mid;
				l=mid+1;
			}else if(b[mid].val<s[i]){
				l=mid+1;
			}else{
				r=mid-1;
			}
		}
		int t=0x7f7f7f7f;
		int flag=0;
		if(~res1) t=query(res1,res2,st1),flag=1;
		if(~ret1){
			int h=query(ret1,ret2,st2);
			if(h<t){
				t=h;
				flag=2;
			}
		}
		if(t!=0x7f7f7f7f){
			int le=a[sl1[t]].val,ri=b[sl2[t]].val;
			if(le+1>s[i]&&ri+1<=e[i]){
				ans[t]+=w[i];
			}
		}
	}
	for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
	return 0;
}