自动搬运

查看原文

来自洛谷，原作者为

	George1123 **

搬运于2025-08-24 21:43:12，当前版本为作者最后更新于2020-01-11 16:54:02，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

广告：blog$\spadesuit$

P2898 【[USACO08JAN]haybale猜测Haybale Guessing】

题意：有一个没有重复数的正整数序列，每句话告诉你 $l\sim r$ 区间的最小值为 $f$，求第一句与前面矛盾的话。

此题算法：并查集 $+$ 二分

二分枚举第一句矛盾的话 $x$ 。

拿出 $1\sim x$ 句话，按 $f$ 从大到小排序。

从左到右读每一句话：

如果出现两段没有重合区域的话满足 $f$ 相等，得出矛盾。

如果出现所有 $f$ 相等的话 $\ll$区域交$\gg$ 已经全为一块，得出矛盾。

将所有相同 $f$ 相等的话 $\ll$区域并$\gg$ 合并为一块。

如果都不满足矛盾，就得出符合。

最后结束二分，得出第一句矛盾的话。

以下是代码 $+$ 注释

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
const int Q=3e4+10;
int d(){int x;scanf("%d",&x);return x;}
int n,q;
struct ask{int l,r,f;}a[Q],cp[Q];
bool cmp(ask x,ask y){ //按 f 从大到小排序
	if(x.f==y.f) return x.l<y.l;
	return x.f>y.f;
}
struct mas{ //并查集
	int f[N];
	void clear(int x){
		for(int i=1;i<=x;i++)
			f[i]=i;
	}
	int find(int x){
		if(f[x]==x) return x;
		return f[x]=find(f[x]); 
	}
}s;
bool check(int x){ //判断1~x这些话矛不矛盾，原理如上
	s.clear(n+1);
	for(int i=1;i<=x;i++)
		cp[i]=a[i];
	sort(cp+1,cp+x+1,cmp);
	int p=cp[1].f,lx,ln,rx,rn;
	lx=ln=cp[1].l,rx=rn=cp[1].r;
	for(int i=2;i<=x;i++){
		if(p==cp[i].f){
			ln=min(ln,cp[i].l);
			rn=min(rn,cp[i].r);
			lx=max(lx,cp[i].l);
			rx=max(rx,cp[i].r);
			if(lx>rn) return 0;
		} else {
			if(s.find(lx)>rn) return 0;
			for(int j=s.find(ln);;j=s.find(j+1))
				if(j>rx) break;
				else s.f[j]=s.f[j+1];
			p=cp[i].f;
			lx=ln=cp[i].l;
			rx=rn=cp[i].r;
		}
	}
	return s.find(lx)<=rn;
}
int main(){
	n=d(),q=d();
	for(int i=1;i<=q;i++)
		a[i].l=d(),a[i].r=d(),a[i].f=d();
	int l=0,r=q+1;
	while(l<r-1){ //二分得出答案
		int mid=(l+r)>>1;
		if(check(mid)) l=mid;
		else r=mid;
	}
	if(r==q+1) puts("0");
	else printf("%d\n",r);
	return 0;
}

用线段树也可以做到，但又麻烦又慢。

画图、写题解不易，快点个赞吧。

谢谢大家! !