题目描述

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.

输入输出样例

输入样例#1：

20 41 10 75 19 73 12 811 15 12

输出样例#1：

3 以下题解摘自洛谷题解，非常清楚

出现矛盾的区间符合两个条件之一：

1.题目中的两个干草堆没有任何数量是一样的，所以如果两个区间没有交集并且它们的最小值相同，则这两个区间产生矛盾

2.如果一个区间包含另一个区间，被包含的区间的最小值大于另一个区间，则两个区间产生矛盾

考虑对原先问答的顺序进行二分答案，对于一个二分出的mid作如下处理：

为了方便处理矛盾2，将从1到mid的每个区间的值按照从大到小进行排序

对于值相同的区间，求出并集和交集的范围，如果不存在并集，则mid不可行

维护一颗线段树，将交集的区间覆盖为1

查询并集的区间是否被覆盖为1，如果是，则mid不可行

1 #include
        
           2 #include
         
            3 #include
          
             4 #include
           
              5 #include
            
               6 using namespace std;  7 struct Ask  8 {  9   int l,r,x; 10 }a[25001],b[25001]; 11 int c[4000001],n,q; 12 bool cmp(Ask a,Ask b) 13 { 14   return a.x>b.x; 15 } 16 void build(int rt,int l,int r) 17 { 18   if (l==r) 19     { 20       c[rt]=0; 21       return; 22     } 23   int mid=(l+r)/2; 24   build(rt*2,l,mid); 25   build(rt*2+1,mid+1,r); 26   c[rt]=c[rt*2]&c[rt*2+1]; 27 } 28 void pushdown(int rt) 29 { 30   if (c[rt]) 31     { 32       c[rt*2]=c[rt]; 33       c[rt*2+1]=c[rt]; 34     } 35 } 36 void update(int rt,int l,int r,int L,int R) 37 { 38   if (l>=L&&r<=R) 39     { 40       c[rt]=1; 41       return; 42     } 43   int mid=(l+r)/2; 44   pushdown(rt); 45   if (L<=mid) update(rt*2,l,mid,L,R); 46   if (R>mid) update(rt*2+1,mid+1,r,L,R); 47   c[rt]=c[rt*2]&c[rt*2+1]; 48 } 49 int query(int rt,int l,int r,int L,int R) 50 { 51   if (c[rt]) return 1; 52   if (l>=L&&r<=R) 53     { 54       return c[rt]; 55     } 56   int mid=(l+r)/2; 57   int ll=1,rr=1; 58   if (L<=mid) ll=query(rt*2,l,mid,L,R); 59   if (R>mid) rr=query(rt*2+1,mid+1,r,L,R); 60   c[rt]=c[rt*2]&c[rt*2+1]; 61   return ll&rr; 62 } 63 bool check(int mid) 64 {
      int i,j,l1,l2,r1,r2,k; 65   for (i=1;i<=mid;i++) 66     b[i]=a[i]; 67   build(1,1,n); 68   sort(b+1,b+mid+1,cmp); 69   for (i=1;i<=mid;i=j) 70     { 71       j=i; 72       while (j<=mid&&b[j].x==b[i].x) j++; 73       l1=2e9;r2=2e9;l2=-1;r1=-1; 74       for (k=i;k
             
              r2) return 0; 82 if (query(1,1,n,l2,r2)) return 0; 83 update(1,1,n,l1,r1); 84 } 85 return 1; 86 } 87 int main() 88 { int i; 89 cin>>n>>q; 90 for (i=1;i<=q;i++) 91 { 92 scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].x); 93 } 94 int l=1,r=q,ans=0; 95 while (l<=r) 96 { 97 int mid=(l+r)/2; 98 if (check(mid)) 99 {100 ans=mid;101 l=mid+1;102 }103 else r=mid-1;104 }105 cout<<(ans+1)%(q+1);106 }