这题的算法真是多种多样，所用的数据结构也是琳琅满目。
而统一的第一步都是：先二分答案，设前a个句子不矛盾。
之后，我用一种朴素的区间染色的方法来处理：
按A[i]值从大到小遍历，把对应的区间[Ql[i],Qh[i]]染成颜色A[i]，
并且规定已经染色的区间不再染色。
这个染色的过程可以用一种类似并查集的方式处理。
这样，所有的区间都染色之后其实就是得到每个区间的最大可能值。
可以证明：若句子不矛盾，则每个区间都取最大可能值就是一组解。
然而，题目有个要求：各个stack的hay bales数都不一样。
这个怎么处理呢？
区间[Ql[i],Qh[i]]的最小值是A[i]的意思蕴含A[i]必须出现在[Ql[i],Qh[i]]中，
也就是说，x必须出现在所有最小值是x的区间的交里。
这个可以预先把每种最小值的交区间都处理出来，
染色的时候判断一下每种最小值是否都可以在它的交区间中找到一个位置。

当然，由于Ql,Qh,A的范围都比较邪恶，我们当然要离散化。
然而，请不要暴力离散化，请看下面这个数据：
10 3
1 10 1
1 1 5
10 10 4
所以，对于Ql,Qh我们要使用“王道离散化”，对普通的离散化加一些手脚，
使得它能把[a,b]与[a,a]∪[b,b]区分出来。
对于A只用暴力离散化就行了。
其实离散化是一种方便、实用的处理方式，虽然很多人不喜欢它，但我认为，
读入数据之后立刻离散化是种不错的处理问题的方式。

提供几组数据：
10 3
1 3 1
2 9 1
8 10 1
输出：3
10 3
1 3 1
2 9 3
4 10 2
输出：0
10 3
1 10 1
1 1 5
10 10 4
输出：0
10 3
1 5 2
4 10 2
10 10 1
输出：3
可见，这题是一个非常靠细心的题，好像中考数学......

示例代码：
void exchange(int &a,int &b){
	static int t;
	t=a;a=b;b=t;
}
void qs1(int b,int e){int j;
	if (b>=e)return;
	exchange(a[b],a[(b+e)>>1]);
	for (int i=j=b+1;i<=e;i++)if (a[i]<a[b] ||
		a[i]==a[b] && (i&1))
			exchange(a[i],a[j++]);
	exchange(a[b],a[--j]);
	qs1(b,j-1);qs1(j+1,e);
}
int getId(int k,int l,int r){
	while (l!=r){
		int m=(l+r)>>1;
		if (a[m]==k)l=r=m;
		else if (k<a[m])r=m-1;
		else l=m+1;
	}
	return l;
}
int lbd[NMax],hbd[NMax];
int Intersection(int &a,int &b,int c,int d){
	if (a==-1){a=c;b=d;return 0;}
	if (b<c || a>d)return 1;
	if (a<c)a=c;
	if (b>d)b=d;
	return 0;
}
int next[NMax<<2];
int getP(int a){return next[a]==-1?a:next[a]=getP(next[a]);}
int ll[NMax];
void qs2(int b,int e){int j;
	if (b>=e)return;
	exchange(ll[b],ll[(b+e)>>1]);
	for (int i=j=b+1;i<=e;i++)if (A[ll[i]]<A[ll[b]] ||
		A[ll[i]]==A[ll[b]] && ll[i]<ll[b])
			exchange(ll[i],ll[j++]);
	exchange(ll[--j],ll[b]);
	qs2(b,j-1);qs2(j+1,e);
}
int Test(int n){
	for (int i=0;i<W;i++)lbd[i]=hbd[i]=-1;
	for (int i=0;i<n;i++){
		if (Intersection(lbd[A[i]],hbd[A[i]],B[i],E[i]))return 0;
	}
	for (int i=0;i<L+N;i++)next[i]=-1;
	int ok[NMax];
	for (int i=0;i<W;i++)ok[i]=0;
	for (int i=N-1;i>=0;i--)if (ll[i]<n){
		for (int p=getP(B[ll[i]]);p<=E[ll[i]];p=getP(p)){
			next[p]=p+1;
			if (lbd[A[ll[i]]]<=p && p<=hbd[A[ll[i]]])
				ok[A[ll[i]]]=1;
		}
	}
	for (int i=0;i<n;i++)if (!ok[A[i]])return 0;
	return 1;
}

	scanf("%d %d",&L,&N);
	for (int i=0;i<N;i++){
		scanf("%d %d %d",B+i,E+i,A+i);B[i]--;E[i]--;
		a[i]=A[i];
	}
	qs1(0,N-1);
	W=0;
	for (int i=0;i<N;i++)if (!W || a[i]!=a[W-1])
		a[W++]=a[i];
	for (int i=0;i<N;i++)A[i]=getId(A[i],0,W-1);
	for (int i=0;i<N;i++){
		a[i<<2]=B[i];a[(i<<2)+1]=E[i];
		a[(i<<2)+2]=B[i]+1;a[(i<<2)+3]=E[i]+1;
	}
	qs1(0,(N<<2)-1);
	L=0;
	for (int i=0;i<(N<<2);i++)if (!L || a[i]!=a[L-1])
		a[L++]=a[i];
	for (int i=0;i<N;i++)E[i]=getId(E[i],0,L-1),B[i]=getId(B[i],0,L-1);
	for (int i=0;i<N;i++)ll[i]=i;
	qs2(0,N-1);
	if (Test(N))printf("0\n");
	else{
		l=0;r=N;
		while (r-l>1){
			if (Test((r+l)>>1))l=((l+r)>>1);
			else r=((l+r)>>1);
		}
		printf("%d\n",l+1);
	}

• 非常感谢ls的数据,这么邪恶的离散化........ (3295) superDD 2010-04-10 13:10:55
• 其实不用离散化的，越离越麻烦…… (0) applepi 2010-10-20 17:36:53