题解：猜数

• 题目描述
• 解析
• 代码

题目描述

对于一个长度为n的数列给出m个描述
每一个描述给出一个区间[a,b]的最小值的x
求从第几个描述开始矛盾

解析

本题关键是一个关于矛盾的充要条件：如果存在一个最小值x，其所在的区间的交集（就是它真正可以存在的区间）是比x大的所有最小值的区间的并集的子集，那么就会矛盾（因为x肯定在那些区间中的一个里，那么那个区间的最小值就应该是x了）
知道这个之后后面就好做了，把所有区间按最小值降序排序，二分出现矛盾的位置mid，每次按新顺序考虑mid之前的描述，用线段树维护之前所有的并集并查询交集,判断是否矛盾即可
复杂度
二分 log ? m
枚举询问 m
线段树 log ? n
总复杂度： m ? log ?m ? log ? n

代码

#include
#define ll long long
#define mid ((l+r) >> 1) 
#define ls k<<1
#define rs k<<1|1
using namespace std;
const int N=1e6+100;
int n,m;
struct node{
    int a,b,x,id;
    bool operator < (const node y)const{return x>y.x;}
}p[N]; 
int tr[4*N];
void build(int k,int l,int r){
    if(l==r){
	    tr[k]=1;return;
    }
    build(ls,l,mid);
    build(rs,mid+1,r);
    tr[k]=tr[ls]+tr[rs];return;
}
void change(int k,int l,int r,int x,int y){
    if(tr[k]==0) return;
    if(x<=l&&r<=y){
	    tr[k]=0;return;
    }
    if(x<=mid) change(ls,l,mid,x,y);
    if(y>mid) change(rs,mid+1,r,x,y);
    tr[k]=tr[ls]+tr[rs];return;
}
int ask(int k,int l,int r,int x,int y){
    if(tr[k]==0) return 0;
    if(x<=l&&r<=y){
	    return tr[k];
    }
    int ans=0;
    if(x<=mid) ans+=ask(ls,l,mid,x,y);
    if(y>mid) ans+=ask(rs,mid+1,r,x,y);
    tr[k]=tr[ls]+tr[rs];
    return ans;
}
bool check(int k){
    build(1,1,n);
    int now=-1,l,r,ml,mr;
    for(int i=1;i<=m;i++){
	    if(p[i].id>k) continue;
	    if(p[i].x==now){
		    l=max(p[i].a,l);
		    r=min(p[i].b,r);
		    ml=min(p[i].a,ml);
		    mr=max(p[i].b,mr);
	    }
	    else{
		    if(now!=-1&&ask(1,1,n,l,r)==0) return false;
		    if(now!=-1) change(1,1,n,ml,mr);
		    l=ml=p[i].a;
		    r=mr=p[i].b;
		    now=p[i].x;
	    }
    }
    if(ask(1,1,n,l,r)==0) return false;
    else return true;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
	    scanf("%d%d%d",&p[i].a,&p[i].b,&p[i].x);
	    p[i].id=i;
    }
    sort(p+1,p+1+m);
    check(2);
    int st=1,ed=m;
    while(st>1;
	    if(check(mmid)) st=mmid;
	    else ed=mmid-1;
    }
    printf("%d",st+1);
}
/*
20 4  
1 10 7
5 19 7
3 12 8
1 20 1
*/