题中重要信息，每堆草的数量都不一样。
可以思考一下，什么情况下才会出现矛盾。
1.如果两个区间的最小值一样，但是这两个区间没有交集，那么就出现矛盾。
2.如果两个区间的最小值一样，并且这两个区间有交集，那么这个最小值一定在交集中，但是如果这个交集被某个最小值较大的区间，或是一些最小值较大的区间的并集包含，那么也是矛盾的。
可以二分答案，将这些区间按照最小值从大到小排序，然后可以用线段树维护，也可以用并查集来搞。
下面是用并查集来搞的。
每到一个区间，可以将[l,r]中的f变成r+1，如果发现find(l) > r那么说明这个区间已经被最小值较大的区间所包含。
#include#include #include #define N 1000011#define min(x, y) ((x) < (y) ? (x) : (y))#define max(x, y) ((x) > (y) ? (x) : (y))int n, q, ans;int f[N];struct node{ int x, y, z;}p[N], t[N];inline int read(){ int x = 0, f = 1; char ch = getchar(); for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1; for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0'; return x * f;}inline bool cmp(node x, node y){ return x.z > y.z;}inline int find(int x){ return x == f[x] ? x : f[x] = find(f[x]);}inline bool check(int k){ int i, j, x, y, lmin, lmax, rmin, rmax; for(i = 1; i <= n + 1; i++) f[i] = i; for(i = 1; i <= k; i++) t[i] = p[i]; std::sort(t + 1, t + k + 1, cmp); lmin = lmax = t[1].x; rmin = rmax = t[1].y; for(i = 2; i <= k; i++) { if(t[i].z < t[i - 1].z) { if(find(lmax) > rmin) return 1; for(j = find(lmin); j <= rmax; j++) f[find(j)] = find(rmax + 1); lmin = lmax = t[i].x; rmin = rmax = t[i].y; } else { lmin = min(lmin, t[i].x); lmax = max(lmax, t[i].x); rmin = min(rmin, t[i].y); rmax = max(rmax, t[i].y); if(lmax > rmin) return 1; } } if(find(lmax) > rmin) return 1; return 0;}int main(){ int i, x, y, mid; n = read(); q = read(); for(i = 1; i <= q; i++) p[i].x = read(), p[i].y = read(), p[i].z = read(); x = 1, y = q; while(x <= y) { mid = (x + y) >> 1; if(check(mid)) ans = mid, y = mid - 1; else x = mid + 1; } printf("%d\n", ans); return 0;}