链接：https://www.luogu.org/problemnew/show/P1083
虽然说这是二分答案的题，但我一开始还真没想到怎么用二分答案去做。
后来想到了，发现又碰了壁。一是二分什么（当然答案要求什么就二分什么呗，沙茶！），二是如何将每份订单的需求对应到每天上去。因为对二分答案不熟，一开始胡乱地选择了二分天数，所以找到需要修改订单的申请人编号也是个问题。
其实方法就摆在那里啊！我真傻。如果不能全部满足要求，人家让你输出哪份订单先不满足的，这不明摆着要二分订单，如果处理到一份订单，无法满足当前全部，那再此之后的订单肯定也无法全部满足，答案是单调的，因此使用二分答案是可以的。
第二面墙，说的书面一点就是单点查询，区间增加，不是有个差分可以方便实现？！
再有一点，我先是用的前闭后开区间，但发现会死循环，又改的闭区间。
1 #include <cstdio> 2 #include <cstring> 3 4 inline int get_num() { 5 int num = 0; 6 char c = getchar(); 7 while (c < '0' || c > '9') c = getchar(); 8 while (c >= '0' && c <= '9') 9 num = num * 10 + c - '0', c = getchar(); 10 return num; 11 } 12 13 const int mmax = 1e6 + 5; 14 15 int n, m, r[mmax], d[mmax], s[mmax], t[mmax], need[mmax]; 16 17 inline int check(int x) { 18 memset(need, 0, sizeof(need)); 19 for (int i = 1; i <= x; ++i) 20 need[s[i]] += d[i], need[t[i] + 1] -= d[i]; 21 for (int i = 1; i <= n; ++i) { 22 need[i] += need[i - 1]; 23 if (need[i] > r[i]) return 0; 24 } 25 return 1; 26 } 27 28 int main() { 29 n = get_num(), m = get_num(); 30 for (int i = 1; i <= n; ++i) r[i] = get_num(); 31 for (int i = 1; i <= m; ++i) 32 d[i] = get_num(), s[i] = get_num(), t[i] = get_num(); 33 int l = 1, r = m; 34 if (check(m)) {printf("0"); return 0;} 35 while (l < r) { 36 int mid = l + (r - l) / 2; 37 if (check(mid)) l = mid + 1; 38 else r = mid; 39 } 40 printf("-1 %d", l); 41 return 0; 42 }