n<=1000000个数互不相同，我回答m<=25000个询问说Li到Ri最小值是Xi，求最早第几次答得互相矛盾。

首先找到矛盾的情况：一是两个无交区间最小值相同，二是大区间最小值比它子区间的最小值大。

方法一：二分答案，每次看一段里面有没有这两种冲突。先把询问按Xi排个序扫一次就知道有没有冲突一，然后再把每个值（从大到小）的所有区间的交集加进线段树看线段树在这一段上是不是已经有了，如果是就有冲突二。看是不是已经有了就是区间最小值。

方法二：先排个序扫一次直接找到冲突一的最小位置，然后在1~这个位置-1的询问中查最早的冲突二。还是按Xi排个序，从大到小，如果Xi相同就按询问编号从小到大。对每个值，由于没有冲突一，交集肯定存在的，所以从小编号到大编号一个一个取交集，每次取完去找这个区间内之前出现过的询问编号的最大值，这就是与它出现冲突的之前的询问编号的最早的一个。为什么是最大值呢，如果只靠那些编号小的询问，那我们只要把现在这个数塞到编号大的询问就不会出事。然后一个数判完冲突后，再把这个数的对应区间的编号全部丢进线段树方便后面查。

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 //#include
          
             6 using namespace std;  7     8 int n,q;  9 #define maxn 2000011 10 const int inf=0x3f3f3f3f; 11 int min(const int &a,const int &b) {
    return a
           
            b?a:b;} 13 struct SMT 14 { 15 struct Node 16 { 17 int Max; 18 int Low; 19 int l,r; 20 int ls,rs; 21 }a[maxn]; 22 int size; 23 SMT() {size=0;} 24 void build(int &x,int L,int R) 25 { 26 x=++size; 27 a[x].Max=inf;a[x].Low=inf; 28 a[x].l=L;a[x].r=R; 29 if (a[x].l==a[x].r) 30 { 31 a[x].ls=a[x].rs=0; 32 return; 33 } 34 const int mid=(L+R)>>1; 35 build(a[x].ls,L,mid); 36 build(a[x].rs,mid+1,R); 37 } 38 void build() { int x;build(x,1,n);} 39 void up(int x) 40 { 41 const int &p=a[x].ls,&q=a[x].rs; 42 a[x].Max=max(a[p].Max,a[q].Max); 43 } 44 void lowsingle(int x,int v) 45 { 46 a[x].Max=min(a[x].Max,v); 47 a[x].Low=min(a[x].Low,v); 48 } 49 void down(int x) 50 { 51 const int &p=a[x].ls,&q=a[x].rs; 52 if (a[x].Low
            
             >1; 67 if (ql<=mid) low(a[x].ls); 68 if (qr> mid) low(a[x].rs); 69 up(x); 70 } 71 } 72 void low(int l,int r,int v) 73 { 74 ql=l;qr=r;this->v=v; 75 low(1); 76 } 77 int query(int x) 78 { 79 if (ql<=a[x].l && a[x].r<=qr) return a[x].Max; 80 else 81 { 82 down(x); 83 const int mid=(a[x].l+a[x].r)>>1; 84 int tmp=-1; 85 if (ql<=mid) tmp=max(query(a[x].ls),tmp); 86 if (qr> mid) tmp=max(query(a[x].rs),tmp); 87 return tmp; 88 } 89 } 90 int query(int l,int r) 91 { 92 ql=l;qr=r; 93 return query(1); 94 } 95 }t; 96 struct Query 97 { 98 int l,r,v,id; 99 bool operator < (const Query &b) const100 { return v
             
              b.id);}103 int main()104 {105 scanf("%d%d",&n,&q);106 for (int i=1;i<=q;i++)107 {108 scanf("%d%d%d",&a[i].l,&a[i].r,&a[a[i].id=i].v);109 b[i].l=a[i].l,b[i].r=a[i].r,b[b[i].id=i].v=a[i].v;110 }111 sort(b+1,b+1+q);b[0].v=0;112 int ans=q+1,l,r;bool flag;113 for (int i=1;i<=q;i++)114 {115 if (b[i].v!=b[i-1].v) l=1,r=n,flag=0;116 if (flag) continue;117 if (b[i].l>r || b[i].r
              
               =1;i--)124 {125 l=max(l,a[i].l);r=min(r,a[i].r);126 int tmp=t.query(l,r);127 ans=min(ans,max(tmp,a[i].id));128 if (a[i].v!=a[i-1].v)129 {130 for (int j=last;j>=i;j--) t.low(a[j].l,a[j].r,a[j].id);131 last=i-1;132 l=1,r=n;133 }134 }135 printf("%d\n",ans==q+1?0:ans);136 return 0;137 }138
              
             
            
           
          
         
        
       
      

方法三：并查集，略（不会）。