题目
题解
首先考虑如何判定是否有不合法的，我们把这些区间信息按照v从大到小排序，按顺序做，每次相当于在区间中找一个位置，填下这个v，还要满足这个v不能填在已经做过的区间中（否则那些区间的最小值就是这次的v了，显然小于了本来应该是的v），那么我们就每次判断是否能填后，用一条线段覆盖本次区间，表示这个区间不能填比我小的了。v相等的若干区间怎么办呢？我们求出这些区间的交，如果交为空，则显然不可能，否则v一定要填在交的位置上，查询一下交的位置是否被完全覆盖即可。做完后要覆盖这些区间的并。可以用线段树实现这个操作。因为原题要求第一个不合法的位置，所以我们还要二分答案。复杂度O(logq∗(n+q∗logq))O(logq∗(n+q∗logq))

upd: leoly表示这题哪有这么简单！是数据太水了！我来加强给你看！然后我就52了orz

还要考虑一下每个位置上是否都能填上数，举个栗子：3-10区间最小值是1e9，你会把他判成合法，可是实际上，因为每个数互不相同，最大为1e9，你是无法填上其他位置的。因此这种情况其实不合法。

并查集

#include<bits/stdc++.h> using namespace std; const int N=1000002; struct node{ int l,r,v; }q[25002],q1[25002]; int n,Q,i,ans,l,r,mid,f[N]; inline char gc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } inline int rd(){ int x=0,fl=1;char ch=gc(); for (;ch<48||ch>57;ch=gc())if(ch=='-')fl=-1; for (;48<=ch&&ch<=57;ch=gc())x=(x<<3)+(x<<1)+(ch^48); return x*fl; } int find(int x){ return x==f[x]?x:f[x]=find(f[x]); } bool cmp(node a,node b){return a.v>b.v || a.v==b.v && a.l<b.l;} bool chk(int x){ for (int i=1;i<=x;i++) q[i]=q1[i]; for (int i=1;i<=n+1;i++) f[i]=i; sort(q+1,q+x+1,cmp); int l,r,l1,r1,las=q[1].v; l=l1=q[1].l;r=r1=q[1].r; for (int i=2;i<=x;i++) if (q[i].v!=las){ if (find(l)>r) return 0; int now=find(l1); while (now<=r1) f[now]=f[now+1],now=find(now+1); l=l1=q[i].l;r=r1=q[i].r;las=q[i].v; }else{ l=max(l,q[i].l);r=min(r,q[i].r); l1=min(l1,q[i].l);r1=max(r1,q[i].r); if (l>r) return 0; } return find(l)<=r; } int main(){ n=rd();Q=rd(); for (i=1;i<=Q;i++) q1[i].l=rd(),q1[i].r=rd(),q1[i].v=rd(); l=1;r=Q; while (l<=r){ mid=l+r>>1; if (chk(mid)) l=mid+1; else r=mid-1; } printf("%d",l>Q?0:l); }

线段树

#include <bits/stdc++.h> using namespace std; #define ll long long #define N 1000010 #define inf 0x3f3f3f3f inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x*f; } int n,m; struct que{ int l,r,x; }q[25010],a[25010]; struct node{ int x,len;bool lazy;//x-区间和  }tree[N<<2]; inline bool cmp(que x,que y){return x.x>y.x;} void build(int p,int l,int r){ tree[p].x=tree[p].lazy=0;tree[p].len=r-l+1;if(l==r) return; int mid=l+r>>1; build(p<<1,l,mid);build(p<<1|1,mid+1,r); } inline void pushdown(int p){ if(!tree[p].lazy) return; tree[p<<1].x=tree[p<<1].len;tree[p<<1|1].x=tree[p<<1|1].len; tree[p<<1].lazy=1;tree[p<<1|1].lazy=1;tree[p].lazy=0; } inline void pushup(int p){ tree[p].x=tree[p<<1].x+tree[p<<1|1].x; } int ask(int p,int l,int r,int x,int y){//1-全覆盖  if(x<=l&&r<=y) return tree[p].x; int mid=l+r>>1;pushdown(p);int res=0; if(x<=mid) res+=ask(p<<1,l,mid,x,y); if(y>mid) res+=ask(p<<1|1,mid+1,r,x,y);return res; } void cover(int p,int l,int r,int x,int y){ if(tree[p].x==tree[p].len) return; if(x<=l&&r<=y){tree[p].x=tree[p].len;tree[p].lazy=1;return;} int mid=l+r>>1;pushdown(p); if(x<=mid) cover(p<<1,l,mid,x,y); if(y>mid) cover(p<<1|1,mid+1,r,x,y);pushup(p); } bool jud(int mid){ for(int i=1;i<=mid;++i) a[i]=q[i];sort(a+1,a+mid+1,cmp); build(1,1,n);int top=1e9; for(int i=1;i<=mid;++i){ int last=i+1,l=a[i].l,r=a[i].r,l1=l,r1=r;//l,r--并集，l1,r1--交集  while(last<=mid&&a[last].x==a[i].x){ if(a[last].l>r1||a[last].r<l1) return 0; l1=max(l1,a[last].l);r1=min(r1,a[last].r); l=min(l,a[last].l);r=max(r,a[last].r);++last; }i=last-1;if(ask(1,1,n,l1,r1)==r1-l1+1) return 0; int cnt=tree[1].x;cover(1,1,n,l,r);cnt=tree[1].x-cnt; if(top-a[i].x+1<cnt) return 0;top-=cnt;//判断能不能把新位置都填上  }return 1; } int main(){ n=read();m=read(); for(int i=1;i<=m;++i) q[i].l=read(),q[i].r=read(),q[i].x=read(); int l=1,r=m; while(l<=r){ int mid=l+r>>1; if(jud(mid)) l=mid+1; else r=mid-1; }if(r==m) puts("0"); else printf("%d\n",r+1); }