题目描述
The cows, who always have an inferiority complex about their intelligence, have a new guessing game to sharpen their brains.
A designated 'Hay Cow' hides behind the barn and creates N (1 ≤ N ≤ 1,000,000) uniquely-sized stacks (conveniently numbered 1..N) of hay bales, each with 1..1,000,000,000 bales of hay.
The other cows then ask the Hay Cow a series of Q (1 ≤ Q ≤ 25,000) questions about the the stacks, all having the same form:
What is the smallest number of bales of any stack in the range of stack numbers Ql..Qh (1 ≤ Ql ≤ N; Ql ≤ Qh ≤ N)?The Hay Cow answers each of these queries with a single integer A whose truthfulness is not guaranteed.
Help the other cows determine if the answers given by the Hay Cow are self-consistent or if certain answers contradict others.
给一段长度为n，每个位置上的数都不同的序列a[1..n]和q和问答，每个问答是(x, y, r)代表RMQ(a, x, y) = r, 要你给出最早的有矛盾的那个问答的编号。
输入输出格式
输入格式：
Line 1: Two space-separated integers: N and Q
- Lines 2..Q+1: Each line contains three space-separated integers that represent a single query and its reply: Ql, Qh, and A
输出格式：
- Line 1: Print the single integer 0 if there are no inconsistencies
among the replies (i.e., if there exists a valid realization of the hay
stacks that agrees with all Q queries). Otherwise, print the index from
1..Q of the earliest query whose answer is inconsistent with the answers
to the queries before it.
输入输出样例
3
以下题解摘自洛谷题解，非常清楚
出现矛盾的区间符合两个条件之一：
1.题目中的两个干草堆没有任何数量是一样的，所以如果两个区间没有交集并且它们的最小值相同，则这两个区间产生矛盾
2.如果一个区间包含另一个区间，被包含的区间的最小值大于另一个区间，则两个区间产生矛盾
考虑对原先问答的顺序进行二分答案，对于一个二分出的mid作如下处理：
为了方便处理矛盾2，将从1到mid的每个区间的值按照从大到小进行排序
对于值相同的区间，求出并集和交集的范围，如果不存在并集，则mid不可行
维护一颗线段树，将交集的区间覆盖为1
查询并集的区间是否被覆盖为1，如果是，则mid不可行
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
struct Ask
{
int l,r,x;
}a[],b[];
int c[],n,q;
bool cmp(Ask a,Ask b)
{
return a.x>b.x;
}
void build(int rt,int l,int r)
{
if (l==r)
{
c[rt]=;
return;
}
int mid=(l+r)/;
build(rt*,l,mid);
build(rt*+,mid+,r);
c[rt]=c[rt*]&c[rt*+];
}
void pushdown(int rt)
{
if (c[rt])
{
c[rt*]=c[rt];
c[rt*+]=c[rt];
}
}
void update(int rt,int l,int r,int L,int R)
{
if (l>=L&&r<=R)
{
c[rt]=;
return;
}
int mid=(l+r)/;
pushdown(rt);
if (L<=mid) update(rt*,l,mid,L,R);
if (R>mid) update(rt*+,mid+,r,L,R);
c[rt]=c[rt*]&c[rt*+];
}
int query(int rt,int l,int r,int L,int R)
{
if (c[rt]) return ;
if (l>=L&&r<=R)
{
return c[rt];
}
int mid=(l+r)/;
int ll=,rr=;
if (L<=mid) ll=query(rt*,l,mid,L,R);
if (R>mid) rr=query(rt*+,mid+,r,L,R);
c[rt]=c[rt*]&c[rt*+];
return ll&rr;
}
bool check(int mid)
{int i,j,l1,l2,r1,r2,k;
for (i=;i<=mid;i++)
b[i]=a[i];
build(,,n);
sort(b+,b+mid+,cmp);
for (i=;i<=mid;i=j)
{
j=i;
while (j<=mid&&b[j].x==b[i].x) j++;
l1=2e9;r2=2e9;l2=-;r1=-;
for (k=i;k<j;k++)
{
l1=min(l1,b[k].l);
r1=max(r1,b[k].r);
l2=max(l2,b[k].l);
r2=min(r2,b[k].r);
}
if (l2>r2) return ;
if (query(,,n,l2,r2)) return ;
update(,,n,l1,r1);
}
return ;
}
int main()
{int i;
cin>>n>>q;
for (i=;i<=q;i++)
{
scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].x);
}
int l=,r=q,ans=;
while (l<=r)
{
int mid=(l+r)/;
if (check(mid))
{
ans=mid;
l=mid+;
}
else r=mid-;
}
cout<<(ans+)%(q+);
}