自动搬运

查看原文

来自洛谷，原作者为

	Wuyanru NOI2025 rp++ 喵~ | 不拿10级勾不改签名 | 我猜我是没机会改签名了

搬运于2025-08-24 23:10:29，当前版本为作者最后更新于2025-02-24 19:14:07，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

小清新贪心。

题目链接。

题意

现在有 $n$ 个人和 $k$ 个健身器材。

第 $i$ 个人需要在 $[l_i,r_i]$ 中的任意一个时刻去健身房 $p_i$，一个健身房同一时刻只能有最多一个人。

一个方案的代价是，有多少时刻，满足这个时刻中健身房里有人。

构造一个代价最小的方案。

$n\le 10^6$。

题解

首先来考虑，假如不存在两个人 $i,j$，使得 $r_i=r_j$ 且 $p_i=p_j$，答案怎么算。

可以发现这是一个贪心，因为每一个人进入健身房的时间应当是越晚越好，这样能让更多的人一起被安排。

具体过程是这样的，我们从小到大枚举时间 $t$。

首先若存在 $l_i=t$，这说明我们可以安排 $i$ 这个人了，将 $i$ 这个人加到 $p_i$ 这个 set 里面。

若存在一个人 $i$，满足 $r_i=t$，并且 $i$ 这个人还没有安排健身房。

那么我们知道，$t$ 这个时刻就一定得有人在健身房了，我们考虑安排哪些人去健身房。

显然，对于同一类人（如果 $p$ 相同我们就认为是一类人），应该选取一个 $r_i$ 最小的人去健身房，直接 set 里面找就好了。

显然，关键的 $t$ 只有 $O(n)$ 个（即每一个人的左右端点），那么这是一个 $O(n\log n)$ 的做法。

考虑为啥不能用这个做法做原题。

因为如果存在两个人 $i,j$，有 $r_i=r_j$，并且 $p_i=p_j$。

那么我们在扫到 $r_i-1$ 这个时刻的时候，就必须要安排一个人上去，否则 $r_i$ 再安排的时候安排不下就爆炸了。

这个时候有一个方法是拿线段树或者什么东西维护一下，可能能做，但我们有更牛的做法。

假设此时存在这样的一对 $i,j$，我们不妨假设 $l_i\le l_j$。

那么我们直接令 $r_i\gets r_i-1$ 就好了。

为什么呢，考虑我们的限制说明了有 $[l_j,r_j]\subseteq [l_i,r_i]$，也就是说 $j$ 能去健身房的时刻 $i$ 也能去。

那么如果 $i$ 在 $r_i$ 这个时刻去了健身房，我们直接让 $i,j$ 两个人去健身房的时刻交换一下，显然交换完的方案依然合法。

所以如果有解，我们就一定能够构造出，$i$ 不在 $r_i$ 时刻去健身房的方案。

那么我们一直做这个操作，做到不存在这样的 $i,j$ 为止。

假设此时存在一个 $k$ 满足 $l_k>r_k$，那么无解。

否则我们可以跑上面那个 set 维护的贪心。

那么如何快速做这个操作呢，把所有 $p_i$ 相同的人放在一起，然后按照 $l_i$ 从大到小进行排序，然后 set 维护连续段即可。

时间复杂度 $O(n\log n)$，并且我们只使用了 set，这实在是太牛了！

题解

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
template<typename A,const int N>
using aya=array<A,N>;
inline int read()
{
	int s=0,w=1;char ch;
	while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
inline ll lread()
{
	ll s=0,w=1;char ch;
	while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
struct node
{
	int l,r,p,id;
}a[1000005];
struct nod
{
	int id,op,t;
	nod(int id=0,int op=0,int t=0):id(id),op(op),t(t){}
};
set<pi>rest[1000005];
set<int>S;
int qans[1000005];
map<int,int>to;
vc<nod>event;
int n,k,c;
set<pi>wtf;
inline void cover(int tim)
{
	vc<int>P;
	for(int i:S)
	{
		qans[a[(*rest[i].begin()).second].id]=tim;
		rest[i].erase(rest[i].begin());
		if(!rest[i].size()) P.push_back(i);
	}
	for(int i:P) S.erase(i);
}
inline int get(int v)
{
	int ans;
	auto it=wtf.upper_bound(pi(v+1,-1));
	if(it==wtf.begin()||(--it)->second<v) ans=v,wtf.insert(pi(v,v));
	else
	{
		int L=it->first,R=it->second;wtf.erase(it);
		while(true)
		{
			it=wtf.upper_bound(pi(v,-1));
			if(it==wtf.begin()||(--it)->second<L-1){ ans=L=L-1;break;}
			L=it->first;wtf.erase(it);
		}
		wtf.insert(pi(L,R));
	}
	return ans;
}
int main()
{
	n=read(),k=read();
	for(int i=1;i<=n;i++) a[i].l=read(),a[i].r=read(),a[i].p=read(),a[i].id=i;
	sort(a+1,a+n+1,[](node a,node b)
	{
		if(a.p!=b.p) return a.p<b.p;
		return a.l>b.l;
	});

	for(int i=1;i<=n;i++)
	{
		if(!to.count(a[i].p)) to[a[i].p]=++c;
		a[i].p=to[a[i].p];
	}

	for(int l=1,r;l<=n;l=r)
	{
		r=l+1;
		while(r<=n&&a[r].p==a[l].p) r++;
		// printf("%d ~ %d\n",l,r-1);
		for(int j=l;j<r;j++)
		{
			a[j].r=get(a[j].r);
			if(a[j].l>a[j].r)
			{
				printf("NIE\n");
				return 0;
			}
			event.push_back(nod(j,0,a[j].l));
			event.push_back(nod(j,1,a[j].r));
		}
		wtf.clear();
	}

	sort(event.begin(),event.end(),[](nod a,nod b)
	{
		if(a.t!=b.t) return a.t<b.t;
		return a.op<b.op;
	});

	// for(int i=1;i<=n;i++) printf("%d %d %d\n",a[i].l,a[i].r,a[i].p);

	int ans=0;
	for(auto p:event)
	{
		if(p.op==0)
		{
			int q=p.id;
			rest[a[q].p].insert(pi(a[q].r,q));
			S.insert(a[q].p);
		}
		else
		{
			int q=p.id,P=a[q].p;
			if(rest[P].find(pi(a[q].r,q))!=rest[P].end()) ans++,cover(a[q].r);
		}
	}

	printf("%d\n",ans);
	for(int i=1;i<=n;i++) printf("%d\n",qans[i]);
	return 0;
}