题解 | Haybale-牛客假日团队赛8E题

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 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 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 ?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.

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

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[25001],b[25001];
 int c[4000001],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]=0;
       return;
    }
    int mid=(l+r)/2;
    build(rt*2,l,mid);
   build(rt*2+1,mid+1,r);
    c[rt]=c[rt*2]&c[rt*2+1];
 }
 void pushdown(int rt)
 {
   if (c[rt])
     {
       c[rt*2]=c[rt];
      c[rt*2+1]=c[rt];
     }
  }
 void update(int rt,int l,int r,int L,int R)
  {
   if (l>=L&&r<=R)
      {
       c[rt]=1;
       return;
     }
   int mid=(l+r)/2;
  pushdown(rt);
   if (L<=mid) update(rt*2,l,mid,L,R);
  if (R>mid) update(rt*2+1,mid+1,r,L,R);
  c[rt]=c[rt*2]&c[rt*2+1];
 }
 int query(int rt,int l,int r,int L,int R)
 {
   if (c[rt]) return 1;
   if (l>=L&&r<=R)
    {
       return c[rt];
      }
   int mid=(l+r)/2;
    int ll=1,rr=1;
    if (L<=mid) ll=query(rt*2,l,mid,L,R);
    if (R>mid) rr=query(rt*2+1,mid+1,r,L,R);
    c[rt]=c[rt*2]&c[rt*2+1];
    return ll&rr;
  }
  bool check(int mid)
  {int i,j,l1,l2,r1,r2,k;
    for (i=1;i<=mid;i++)
      b[i]=a[i];
    build(1,1,n);
    sort(b+1,b+mid+1,cmp);
    for (i=1;i<=mid;i=j)
      {
        j=i;
        while (j<=mid&&b[j].x==b[i].x) j++;
        l1=2e9;r2=2e9;l2=-1;r1=-1;
       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 0;
        if (query(1,1,n,l2,r2)) return 0;
        update(1,1,n,l1,r1); 
      }
    return 1;
  }
  int main()
  {int i;
   cin>>n>>q;
   for (i=1;i<=q;i++)
      {
        scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].x);
      }
    int l=1,r=q,ans=0;
   while (l<=r)
     {
        int mid=(l+r)/2;
        if (check(mid)) 
      {
    ans=mid;
       l=mid+1;
      }
         else r=mid-1;
      }
    cout<<(ans+1)%(q+1);
  }