自动搬运

查看原文

来自洛谷，原作者为

	yywlp 快递组万岁！！！

搬运于2025-08-24 22:59:36，当前版本为作者最后更新于2024-06-19 17:12:35，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

简单题，有上一问的基础非常容易。

这里每个要条件需要达成最少 $k_i$ 次，似乎不能直接简单往回走了，这里还需要回头再回头，有点懵。

但是参考一下上一题：走到最后再往回。那这个是不是每次都走到最前面再往后呢？没错！我们开个结构体将条件按 $y_i$ 排序，对于第一个条件会发现，这个条件需要在 $\le y_i$ 的某个位置转 $k_i-1$ 次，那我肯定每次都走到最前面再转更好，反正这 $k_i-1$ 次无论如何都是要转的，如果在后面提前转了肯定会亏。而对于 $x_i$ 最大的条件就如同上一题，肯定是走到最后再一起转，所以我们再开个结构体把条件按 $x_i$ 排序。

前一个从前往后扫维护最前面的 $y_i$，后一个从后往前扫维护最后面的 $x_i$，然后再记 $k$ 表示重复了几次，满足当前条件的 $k_i$ 就往后或往前调扫描线，每次看当前应该还要重复几次，乘上前缀最小值 $+$ 后缀最小值就行。

记得开 long long，因为这个 WA 了好几次QAQ。

时间复杂度在排序 $\mathcal O(m\log m+n)$。

Code

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int M=2e5+10;
int n,m;
int a[M],mnh[M],mnq[M];
struct NODE{
	int x,y,k,id;
}n1[M],n2[M];
bool cmpx(const NODE&A,const NODE&B){
	if(A.x==B.x)return A.y<B.y;
	return A.x<B.x;
}
bool cmpy(const NODE&A,const NODE&B){
	if(A.y==B.y)return A.k>B.k;
	return A.y<B.y;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=m;i++)scanf("%d%d%d",&n1[i].x,&n1[i].y,&n1[i].k),n2[i]=n1[i],n1[i].id=n2[i].id=i;
	sort(n1+1,n1+m+1,cmpx);
	sort(n2+1,n2+m+1,cmpy);
	mnh[n]=a[n];
	for(int i=n-1;i>=1;i--)mnh[i]=min(mnh[i+1],a[i]);
	mnq[1]=a[1];
	for(int i=2;i<=n;i++)mnq[i]=min(mnq[i-1],a[i]);
	int l=1,r=m,k=0;
	LL ans=0;
	while(r>=1){
		int nr=n1[r].k-k,nl=n2[l].k-k;
		int nk=min(nl,nr);
        ans+=1ll*nk*mnh[n1[r].x]+1ll*nk*mnq[n2[l].y];
		k+=nk;
		while(n1[r].k<=k&&r>=1)r--;
		while(n2[l].k<=k&&l<=m)l++;
	}
	ans-=mnq[n2[1].y];
	cout<<ans<<endl;
	return 0;
}