自动搬运

查看原文

来自洛谷，原作者为

	by_chance 还好我拥有不同的宇宙，能治愈所有我偏执的梦。

搬运于2025-08-24 21:51:01，当前版本为作者最后更新于2023-03-30 22:17:28，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意：长为 $n$ 的 $01$ 数列中有 $k$ 个 $1$，满足 $m$ 个条件。每个条件形如 $a_i$,$b_i$,$c_i$，含义如下：

• $c_i=0$ 时，区间 $[a_i,b_i]$ 中没有 $1$。
• $c_i=1$ 时，区间 $[a_i,b_i]$ 中有 $1$。

保证初始有解。求所有必定为 $1$ 的位置。

$1 \le n \le 10^5$，$0 \le m \lt 10^5$，$1 \le k \le n$，$1 \le a_i \le b_i \le n$。

首先解决简单情况：

1. 丢掉所有条件给出为 $0$ 的位置。
2. 如果剩下的可能位置数与总数相同，剩下的所有位置都满足条件。
3. 如果有某个 $c_i=1$ 的区间长为 $1$，这个位置满足条件。
4. 如果有某两个 $c_i=1$ 的区间有包含关系，只用考虑小的那个。

下面来考虑剩下的情形。对所有区间按左端点递增排序，则右端点也递增。

首先可以贪心求出一组解（不考虑 $k$），这只要从左到右扫描所有区间，如果某个区间还没有 $1$，在其右端点放 $1$。同时可以求出满足前 $i$ 个区间所需要的 $1$ 的数目的最小值 $f_i$。类似的，可以求出满足后 $i$ 个区间所需要的 $1$ 的数目的最小值 $g_i$。

“某个位置必须是 $1$”等价于“某个位置是 $0$ 时无解”。只用考虑那些满足 $f_i = f_{i-1} + 1$ 的区间 $[a_i,b_i]$ 的右端点，记为 $x$。则满足前 $i$ 个区间的条件需要 $f_i$ 个 $1$。

再考虑所有完全在 $x-1$ 右侧的区间，设为后 $p$ 个。假设 $x$ 不是 $1$，所以满足前 $i$ 个区间时不会满足后 $p$ 个区间中的任何一个。那么无解的充分必要条件就是 $f_i + g_p \gt k$。

$p$ 可以二分求。时间复杂度 $O(n \log n)$。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,k,m,d[N],t,h[N],lst[N],nxt[N],cnt,st[N],top,f[N],g[N],flag;
struct range{int l,r;}p[N];
bool operator <(const range &a,const range &b){
	return a.l!=b.l?a.l<b.l:a.r<b.r;
}
int main(){
	scanf("%d%d%d",&n,&k,&m);
	for(int i=1,a,b,c;i<=m;i++){
		scanf("%d%d%d",&a,&b,&c);
		if(c==0)++d[a],--d[b+1];
		else{++t;p[t].l=a;p[t].r=b;}
	}
	for(int i=1;i<=n;i++){
		d[i+1]+=d[i];
		if(!d[i]){lst[i]=nxt[i]=++cnt;h[cnt]=i;}
	}
	if(k==cnt){
		for(int i=1;i<=cnt;i++)printf("%d\n",h[i]);
		printf("\n");
		return 0;
	}
	for(int i=1;i<=n;i++)if(!lst[i])lst[i]=lst[i-1];
	for(int i=n;i>=1;i--)if(!nxt[i])nxt[i]=nxt[i+1];
	for(int i=1;i<=t;i++)p[i].l=nxt[p[i].l],p[i].r=lst[p[i].r];
	sort(p+1,p+t+1);top=0;
	for(int i=1;i<=t;i++){
		if(p[i].l>p[i].r)continue;
		while(top&&p[st[top]].r>=p[i].r)--top;
		st[++top]=i;
	}t=top;
	for(int i=1;i<=t;i++)p[i]=p[st[i]];
	int mx=0,mn=1e9;
	for(int i=1;i<=t;i++){
		if(p[i].l>mx)f[i]=f[i-1]+1,mx=p[i].r;
		else f[i]=f[i-1];
	}
	for(int i=t;i>=1;i--){
		if(p[i].r<mn)g[i]=g[i+1]+1,mn=p[i].l;
		else g[i]=g[i+1];
	}
	for(int i=1;i<=t;i++){
		if(p[i].l==p[i].r){flag=1;printf("%d\n",h[p[i].l]);continue;}
		if(f[i]!=f[i-1]+1)continue;
		int pos=t+1,l=i+1,r=t;
		while(l<=r){
			int mid=l+r>>1;
			if(p[mid].l>p[i].r-1)pos=mid,r=mid-1;
			else l=mid+1;
		}
		if(f[i]+g[pos]>k){flag=1;printf("%d\n",h[p[i].r]);}
	}
	if(!flag)printf("-1\n");
	return 0;
}