传送门
题中重要信息，每堆草的数量都不一样。
可以思考一下，什么情况下才会出现矛盾。
1.如果两个区间的最小值一样，但是这两个区间没有交集，那么就出现矛盾。
2.如果两个区间的最小值一样，并且这两个区间有交集，那么这个最小值一定在交集中，但是如果这个交集被某个最小值较大的区间，或是一些最小值较大的区间的并集包含，那么也是矛盾的。
可以二分答案，将这些区间按照最小值从大到小排序，然后可以用线段树维护，也可以用并查集来搞。
下面是用并查集来搞的。
每到一个区间，可以将[l,r]中的f变成r+1，如果发现find(l) > r那么说明这个区间已经被最小值较大的区间所包含。
#include <cstdio> #include <iostream> #include <algorithm> #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 p[N], t[N]; inline int read() inline bool cmp(node x, node y) inline int find(int x) inline bool check(int k) else } if(find(lmax) > rmin) return 1; return 0; } int main() printf("%d\n", ans); return 0; }
上一篇：[BZOJ1590] [Usaco2008 Dec]Secret Message 秘密信息（字典树）
下一篇：[BZOJ4992] [Usaco2017 Feb]Why Did the Cow Cross the Road（spfa）
二分 并查集
