题意：
给定一个长度为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 }