【POJ3657】【USACO 2008 Jan Gold】 1.Haybale Guessing 二分答案，并查集check

题意：

输入n、m表示数列长度为n，有m条有序的限制｛l,r,x｝。

限制：l~r间所有数最小值为x。

问到第几条限制开始出现矛盾，都不出现输出"0"。

题解：

首先这题比较厉害，正常解有点难，不妨转化成二分答案。

我们二分“答案”，也就是第ans条出现矛盾。

考虑到若一条限制S所在区间被另一个限制Seg包含，且Seg这条限制的x又比S.x大，

那么也就是意为

① [Seg.l,Seg.r]间最小值为Seg.x

② [S  .l,S  .r]间最小值为S  .x

③S.x < Seg.x

易得这是矛盾情况且是唯一矛盾情况，即不存在其它矛盾情况。

然后我们就可以怒check了。

这时候涉及一种想法：

我们可以 以x为关键字对当前一次check涉及的“限制”降序排序、

然后记录一个节点（或区间）是否被覆盖。

线段树显然是可以过的。  (...也显然是需要好几K的常数优化的

所以又有了一个技巧：

我们可以维护一个并查集 f[i]=j表示j+1到i这段区间都被覆盖了。

然后均摊是貌似是大常数O（n），，总之非常快就是了，我都没有离散化就高速过了。  ...(虽然它不是瓶颈

对于这个时间复杂度分析如果谁能证明是n*logn，欢迎留言打脸。

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1001000
#define M 30000
#define inf 0x3f3f3f3f
using namespace std;
/*struct LSH
{
	int x,note;
	bool flag;
	bool operator < (const LSH &a)const{return x<a.x;}
}lsh[M<<1];*/
struct Lux
{
	int l,r,x;
	bool operator < (const Lux &a)const{return x>a.x;}
}q[M],Q[M];
int n,m,f[N];
int stk[N],top;
int find(int x)
{
	top=0;
	while(f[x]!=x)stk[++top]=x,x=f[x];
	while(top)f[stk[top--]]=x;
	return x;
}
bool check(int mid)
{
	int i,j,k,t;
	int L,R,l,r;
	for(i=1;i<=n;i++)f[i]=i;
	for(i=1;i<=mid;i++)q[i]=Q[i];
	sort(q+1,q+mid+1);
	for(i=1;i<=mid;i=j+1)
	{
		L=l=q[i].l,R=r=q[i].r;
		for(j=i;j<mid&&q[j+1].x==q[j].x;)
		{
			j++;
			L=min(L,q[j].l),R=max(R,q[j].r);
			l=max(l,q[j].l),r=min(r,q[j].r);
		}
		if(find(r)<l)return 0;
		for(t=R;k=find(t),k>=L;t=k-1)f[k]=L-1;
	}
	return 1;
}
int main()
{
//	freopen("test.in","r",stdin);
	int i,j,k;
	int l,r,mid,ans;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)scanf("%d%d%d",&Q[i].l,&Q[i].r,&Q[i].x);
	l=1,r=m,ans=0;
	for(i=1;i<=20&&l<=r;i++)
	{
		mid=l+r>>1;
		if(check(mid))l=mid+1;
		else ans=mid,r=mid-1;
	}
	printf("%d\n",ans);
	return 0;
}

原文：http://blog.csdn.net/vmurder/article/details/42105647