题意
一个长度为 \(n\) 的序列，每个权值互不相同，给出形如 \(l,r,p\) 的信息表示 \([l,r]\) 区间中最小的数是 \(p\) ，问第几个信息开始出现矛盾。
\(n\leq 5 \times 10^5\) .
分析
-
二分答案再判前 \(mid\) 个信息是否合法。
-
相同 \(p\) 的区间的 \(p\) 一定出现在这些区间的交中。
-
分析出现矛盾的两种情况：
-
相同权值的区间没有交集
-
相同权值的区间有交集，但是这些位置一定要填 \(>p\) 的数
-
-
考虑将区间按照权值从大到小排序，每次处理一种权值 \(p\) ，计算出交之后观察能不能在交区间中找到一个位置来放置 \(p\) 。
-
接着再将并区间打上标记表示不能有 \(< p\) 的数出现在这个区间中。
-
总时间复杂度为 \(O(n log^2n)\)。
代码
#include<bits/stdc++.h>
using namespace std;
#define go(u) for(int i=head[u],v=e[i].to;i;i=e[i].last,v=e[i].to)
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define pb push_back
#define Ls o<<1
#define Rs o<<1|1
typedef long long LL;
inline int gi(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
return x*f;
}
template<typename T>inline bool Max(T &a,T b){return a<b?a=b,1:0;}
template<typename T>inline bool Min(T &a,T b){return b<a?a=b,1:0;}
const int N=5e5 + 7,inf=0x3f3f3f3f;
int n,q;
int par[N];
int getpar(int a){return par[a]==a?a:par[a]=getpar(par[a]);}
struct data{
int l,r,v;
data(){}data(int l,int r,int v):l(l),r(r),v(v){}
bool operator <(const data &rhs)const{
return v>rhs.v;
}
}t[N],d[N];
bool check(int mid){
rep(i,1,mid) t[i]=d[i];
sort(t+1,t+1+mid);
rep(i,1,n) par[i]=i;
for(int i=1,j=1;i<=mid;i=j+1,j=i){
int l=t[i].l,r=t[i].r,L=t[i].l,R=t[i].r;
while(j+1<=mid&&t[j+1].v==t[j].v){
++j;
Max(l,t[j].l);Min(r,t[j].r);
Min(L,t[j].l);Max(R,t[j].r);
}
if(l>getpar(r)) return 0;
while(L<=R){
if(getpar(R)==R) par[R]=getpar(L-1),--R;
else R=getpar(R);
}
}
return 1;
}
int main(){
n=gi(),q=gi();
rep(i,1,q) d[i].l=gi(),d[i].r=gi(),d[i].v=gi();
int l=1,r=q;
while(l<r){
int mid=l+r+1>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
printf("%d\n",l+1);
return 0;
}
