Description
隔壁村的阿黑的Dog没有跑, 但Dog已经15岁了, 相当于人类达到了79岁.
为了防止Dog患上犬类认知障碍 (Canine cognitive dysfunction, CCD), 阿黑决定陪Dog玩猜数游戏.
游戏开始前，阿黑会在Dog后面摆上(N)个数字. 所有数字排成一条直线，按次序从(1)到(N)编号，每个位置的数字均不同.
游戏开始后，Dog将会询问阿黑(Q)个问题，每个问题的格式都是一样的:
"位置在(l)到(r)的数字中，最小的数字是多少?"
对每个问题，阿黑都会回答一个数字(A). 但阿黑的回答可能不正确.
年迈的Dog想知道阿黑从哪里开始已经出现了矛盾, 可惜的是, Dog其实已经患上了严重的犬类认知障碍, 于是这就成了一道机考题.
Input
输入的第一行有两个用空格分开的整数(N)和(Q), 含义如上.
接下来(Q)行, 每行有三个用空格分开的整数(l, r, A), 含义如上.
Output
如果完全没有矛盾，输出(0)，否则输出最先造成矛盾的问题编号
Sample Input
20 4
1 10 7
5 19 7
3 12 8
11 15 12
Sample Output
3
这道题我们可以这样想，如果我们按照询问数值的某种顺序来排序，是不是会好做一点。这个时候我们只要套上一个二分，一样可以求出最小是哪个询问不满足。
如果我们从小到大排序，由于每个位置的值不同，数值相同的区间要两两相交才行。并且如果这些区间的并中包含之前某个数值区间的交也不行（稍微YY下吧）。这个算法可以用set写，但是很复杂啊。
但是我们可以从大到小排序，过程刚好相反。数值相同的区间要两两相交才行，并且这些区间的交不能包含别的区间。这个我们可以用并查集实现。一段区间表示一个集合，集合的代表元便是区间右端点(+1)(方便实现)。
具体实现看代码：
#include<set>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
using namespace std;
#define inf (1<<29)
#define maxn (1000010)
int ans,N,Q,father[maxn],tmp[maxn],cnt;
struct node
{
int L,R,V,id;
friend inline bool operator <(const node &a,const node &b) { return a.V > b.V; }
inline void read(int i) { scanf("%d %d %d",&L,&R,&V); id = i; }
}query[maxn];
inline int find(int x)
{
for (;x != father[x];x = father[x]) tmp[++cnt] = x;
while (cnt) father[tmp[cnt--]] = x;
return x;
}
inline bool check(int mid)
{
for (int i = 1;i <= N+1;++i) father[i] = i;
for (int i = 1,j;i <= Q;i = j)
{
int jl = -inf,jr = inf,bl = inf,br = -inf;
for (j = i;j <= Q&&query[j].V == query[i].V;++j)
{
if (query[j].id > mid) continue;
jl = max(jl,query[j].L); bl = min(bl,query[j].L);
jr = min(jr,query[j].R); br = max(br,query[j].R);
if (jl > jr) return false;
}
if (jl == -inf) continue;
if (find(jl)-1 >= jr) return false;
int f = find(br+1);
for (int k = find(bl);k <= br;++k) father[k] = f;
}
return true;
}
inline void work()
{
int l = 1,r = Q,mid;
while (l <= r)
{
mid = (l+r) >> 1;
if (check(mid)) l = mid + 1;
else r = mid - 1,ans = mid;
}
}
int main()
{
freopen("1586.in","r",stdin);
freopen("1586.out","w",stdout);
scanf("%d %d",&N,&Q);
for (int i = 1;i <= Q;++i) query[i].read(i);
sort(query+1,query+Q+1);
work(); printf("%d",ans);
fclose(stdin); fclose(stdout);
return 0;
}