P2898 [USACO08JAN] Haybale Guessing G 题解

P2898 [USACO08JAN] Haybale Guessing G 题解

集训考到的题，赛时没想出来，很巧妙的做法。

解法

前置芝士：线段树，二分。

注意到题面要我们求最早与前面的条件有矛盾的条件的编号，所以这个答案是有单调性的，即假设前 $i$ 个条件有矛盾，则对于所有的 $j>i$，前 $j$ 个条件也有矛盾。相应的，对于所有的 $j<i$，前 $j$ 个条件没有矛盾。就此单调性，我们考虑二分答案。下面考虑如何写这个 check。

考虑什么时候条件之间有矛盾，分两种情况，如下图所示。

1. 因为题中说数组中的数字互不相同，所以如果两个相离的区间的最小值相同，则两条件一定矛盾。这个情况显然。

2. 如果区间 $A$ 包含区间 $B$，且区间 $A$ 的最小值大于区间 $B$ 的最小值则两条件一定矛盾。这个情况显然。

所以我们使用线段树标记区间，看是否违反情况二。用简单的循环就可以判断是否违反情况一。

代码

#include<bits/stdc++.h>
using namespace std;
namespace fast_IO
{
	/*
	fast input/output
	*/
};
using namespace fast_IO;
int n,q,l=1,r,mid,ans;
/**
 * seg_node:
 * 1. sum,lazy,lc,rc
 * 2. pushup
 * 3. pushdown
 * 
 * segment_tree:
 * 1. build
 * 2. clear
 * 3. fix
 * 4. ask
*/
#define ls l,mid
#define rs mid+1,r
struct seg_node
{
	int sum,lazy;
	seg_node *lc,*rc;
	inline void pushup()
	{
		sum=lc->sum+rc->sum;
	}
	inline void pushdown(const int &l,const int &r)
	{
		if(lazy)
		{
			int mid=(l+r)/2;
			lc->sum=mid-l+1,rc->sum=r-mid,lc->lazy=rc->lazy=1,lazy=0;
		}
	}
};
class seg_tree
{
private:
	seg_node *root;
	inline seg_node *build(int l,int r)
	{
		seg_node *rt=new seg_node;
		if(l<r)
		{
			int mid=(l+r)/2;
			rt->lc=build(ls),rt->rc=build(rs);
		}
		return rt;
	}
	inline void clear(seg_node *rt,int l,int r)
	{
		rt->sum=rt->lazy=0;
		if(l<r)
		{
			int mid=(l+r)/2;
			clear(rt->lc,ls),clear(rt->rc,rs);
		}
	}
	inline void fix(seg_node *rt,const int &L,const int &R,int l,int r)
	{
		if(L<=l && r<=R)
		{
			rt->sum=r-l+1,rt->lazy=1;
			return;
		}
		rt->pushdown(l,r);
		int mid=(l+r)/2;
		if(L<=mid) fix(rt->lc,L,R,ls);
		if(R>mid) fix(rt->rc,L,R,rs);
		rt->pushup();
	}
	inline int ask(seg_node *rt,const int &L,const int &R,int l,int r)
	{
		if(L<=l && r<=R) return rt->sum;
		rt->pushdown(l,r);
		int mid=(l+r)/2,ret=0;
		if(L<=mid) ret+=ask(rt->lc,L,R,ls);
		if(R>mid) ret+=ask(rt->rc,L,R,rs);
		return ret;
	}
public:
	inline void build()
	{
		root=build(1,n);
	}
	inline void clear()
	{
		clear(root,1,n);
	}
	inline void fix(const int &L,const int &R)
	{
		fix(root,L,R,1,n);
	}
	inline int ask(const int &L,const int &R)
	{
		return ask(root,L,R,1,n);
	}
};
seg_tree tree;
struct que
{
	int l,r,x;
	inline bool operator<(const que &rhs) const
	{
		return x>rhs.x;
	}
};
que a[25010],tmp[25010];
inline bool judge(int x)
{
	for(int i=1;i<=x;i++) tmp[i]=a[i];
	sort(tmp+1,tmp+x+1),tree.clear();
	for(int i=1,j,l1,l2,r1,r2;i<=x;i=j)
	{
		j=i,l1=l2=tmp[i].l,r1=r2=tmp[i].r;
		while(tmp[i].x==tmp[j].x && j<=x) j++;
		for(int k=i;k<j;k++)
			l1=min(l1,tmp[k].l),r1=max(r1,tmp[k].r),l2=max(l2,tmp[k].l),r2=min(r2,tmp[k].r);
		if(l2>r2) return false;
		if(tree.ask(l2,r2)==r2-l2+1) return false;
		tree.fix(l1,r1);
	}
	return true;
}
int main()
{
	read(n),read(q),r=q,tree.build();
	for(int i=1;i<=q;i++) read(a[i].l),read(a[i].r),read(a[i].x);
	while(l<=r)
	{
		mid=(l+r)/2;
		if(judge(mid)) l=mid+1;
		else ans=mid,r=mid-1;
	}
	cout<<ans;
	return 0;
}