題目描述

對于一個長度為n的數列給出m個描述
每一個描述給出一個區間[a,b]的最小值的x
求從第幾個描述開始矛盾

解析

本題關鍵是一個關于矛盾的充要條件：

如果存在一個最小值x，其所在的區間的交集（就是它真正可以存在的區間）是比x大的所有最小值的區間的并集的子集，那么就會矛盾（因為x肯定在那些區間中的一個里，那么那個區間的最小值就應該是x了）

知道這個之后后面就好做了
把所有區間按最小值降序排序
二分出現矛盾的位置mid
每次按新順序考慮mid之前的描述
用線段樹維護之前所有的并集并查詢交集
判斷是否矛盾即可

復雜度

二分$\log m$
枚舉詢問$m$
線段樹$\log n$
總復雜度：$m?\log m?\log n$

代碼

#include<bits/stdc++.h> #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{//printf("now=%d l=%d r=%d ml=%d mr=%d\n",now,l,r,ml,mr);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<ed){int mmid=st+ed+1>>1;if(check(mmid)) st=mmid;else ed=mmid-1;} // printf("%dok ",check(2));printf("%d",st+1); } /* 20 4 1 10 7 5 19 7 3 12 8 1 20 1 */

總結

以上是生活随笔為你收集整理的猜数（二分、线段树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。