本文主要是介绍bzoj1594[Usaco2008 Jan]Haybale Guessing猜数游戏，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1594
题目大意：
N个数排成一列，有q个询问。每个询问告诉你区间[l,r]的最小值是多少(这N个数各不相同)。问你这q个询问有没有矛盾，有的话从哪里开始有矛盾。
题解：
二分+线段树
有人用神奇姿势の并查集来代替线段树来搞..但是我不懂QwQ
于是我就打了线段树。。代码迷の长&迷の慢。。orzorz
我们要先想矛盾之处会在哪里。
1、没有交集的两个区间出现了相同的最小值x。因为每个数各不相同。即x的交集不合法或者说没有交集。
2、已知某段区间的最小值为x，但是这段区间中的某个子区间的最小值为y，而y<x，那么对于已知的条件就矛盾了。即x所在区间的并集包含了y所在区间的交集的话就矛盾了(x>y)。
二分答案，把询问排序。
怎么排？按值从大到小，这样就方便处理矛盾2。
把x的区间都找到，得到其交集和并集的区间。
直接用交集的区间判断矛盾1咯。
对于矛盾二，用线段树维护标记下在哪段区间（用并集标记）已经知道最小值。
因为从大到小排的序，所以更新在线段树里标记的都是比现在的数大的数标记的。那么如果查询到现在这个数的交集区间已经被标记了，就是矛盾2啊有矛盾了。
然后，，，就这样啊。。。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 2000010
#define Q 30000struct node {int l,r,c;}a[Q],b[Q];
bool cmp(node x,node y){return x.c>y.c;}
struct tree
{int l,r,lc,rc;bool c;
}tr[maxn];int len,n;
void bt(int l,int r)
{len++;int now=len;tr[now].l=l;tr[now].r=r;tr[now].lc=tr[now].rc=-1;tr[now].c=0;if (l<r){int mid=(l+r)>>1;tr[now].lc=len+1;bt(l,mid);tr[now].rc=len+1;bt(mid+1,r);}
}
void change(int now,int l,int r)
{if (tr[now].l==l && tr[now].r==r) {tr[now].c=1;return;}int mid=(tr[now].l+tr[now].r)>>1,lc=tr[now].lc,rc=tr[now].rc;if (r<=mid) change(lc,l,r);else if (l>mid) change(rc,l,r);else change(lc,l,mid),change(rc,mid+1,r);if (!tr[now].c) tr[now].c=(tr[lc].c&tr[rc].c);
}
bool query(int now,int l,int r)
{if (tr[now].c) return true;if (tr[now].l==l && tr[now].r==r) return tr[now].c;int mid=(tr[now].l+tr[now].r)>>1,lc=tr[now].lc,rc=tr[now].rc;if (r<=mid) return query(lc,l,r);else if (l>mid) return query(rc,l,r);else return (query(lc,l,mid)&query(rc,mid+1,r));
}
int mymin(int x,int y) {return (x<y)?x:y;}
int mymax(int x,int y) {return (x>y)?x:y;}
bool check(int mid)
{int i,j,k,l1,l2,r1,r2;for (i=1;i<=n*2;i++) tr[i].c=0;for (i=1;i<=mid;i++) b[i]=a[i];sort(b+1,b+1+mid,cmp);for (i=1;i<=mid;){for (j=i;j<=mid && b[j].c==b[i].c;j++);l1=l2=b[i].l;r1=r2=b[i].r;//[l1,r1]是交集区间 [l2,r2]是并集区间for (k=i+1;k<j;k++){l1=mymin(l1,b[k].l);l2=mymax(l2,b[k].l);r1=mymax(r1,b[k].r);r2=mymin(r2,b[k].r);}if (l2>r2) return true;if (query(1,l2,r2)) return true;change(1,l1,r1);i=j;}return false;
}
int main()
{//freopen("bales.in","r",stdin);//freopen("bales.out","w",stdout);int q,i,l,r,bk;scanf("%d%d",&n,&q);len=0;bt(1,n);for (i=1;i<=q;i++)scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].c);l=1;r=q;bk=0;while (l<=r)//二分{int mid=(l+r)>>1;if (check(mid)) {bk=mid;r=mid-1;}else l=mid+1;}printf("%d\n",bk);return 0;
}这篇关于bzoj1594[Usaco2008 Jan]Haybale Guessing猜数游戏的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
