CF1843E 二分+前缀和

题意：

给定一个长度为n且均为0的数组，q次单点修改（从0改为1），以及m个基于该数组的区间。

规定好区间为：区间内1的个数严格大于0的个数。

上述m个区间若存在一个好区间则为合法，问按顺序进行q次单点修改过程中最早出现合法的单次修改编号，若无则输出-1。

马后炮思考：

对于m个区间，其实际关系是无序的。二分最重要的是考虑单调性，本题中单点修改的不断积累过程本质是趋于合法的单调。因而考虑二分q，一个log。

那么对于某一次二分的check(x)，对前x个单点修改作前缀和cnt统计，O(n)。随后遍历所有的m个区间，通过查看cnt[R] - cnt[L-1]判断是否为好区间，得出合法性。

下面是代码，若有误，请您指出。

 1 #include<iostream>
 2 #include<vector> 
 3 #define ll long long
 4 using namespace std;
 5 
 6 const int N = 1e5 + 10;
 7 int L[N], R[N], q[N];
 8 int cnt[N];
 9 int n, m;
10 
11 bool check(int x)
12 {
13     for(int i = 0 ; i <= n ; i++) {
14         cnt[i] = 0;
15     }
16     for(int i = 1 ; i <= x ; i++) {
17         cnt[q[i]] = 1;
18     }
19     for(int i = 1 ; i <= n ; i++) {
20         cnt[i] += cnt[i - 1];
21     }
22     for(int i = 1 ; i <= m ; i++) {
23         int len = R[i] - L[i] + 1;
24         if(cnt[R[i]] - cnt[L[i] - 1] > len / 2){
25             return true;
26         }
27     }
28     return false;
29 }
30 
31 int main(){
32     ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
33     int cas; cin >> cas;
34     while(cas--)
35     {
36         cin >> n >> m;
37         for(int i = 1 ; i <= m ; i++) {
38             cin >> L[i] >> R[i];
39         }
40         int Q; cin >> Q;
41         for(int i = 1 ; i <= Q ; i++) {
42             cin >> q[i];
43         }
44         int l = 1, r = Q;
45         while(l < r) {
46             int mid = (l + r) >> 1;
47             if(check(mid)) {
48                 r = mid;
49             }else {
50                 l = mid + 1;
51             }
52         }
53         if(check(l) && l <= Q) {
54             cout << l << endl;
55         }else if(check(l + 1) && l + 1 <= Q){
56             cout << l + 1 << endl;
57         }else {
58             cout << -1 << endl;
59         }
60     }
61     
62     return 0;
63 }