Tracking Segments

题面翻译

有一个长度为 $n$，初始全为 $0$ 的序列。我们定义一个区间是美丽的，当且仅当区间内 $1$ 的个数严格大于 $0$ 的个数。现给定 $m$ 个区间和 $q$ 次修改，每次修改可以将该位置上的 $0$ 变成 $1$。对于每组数据，求出最少第几次修改后，给定的 $m$ 个区间中至少一个是美丽的。数据保证每次修改各不相同。

题目描述

You are given an array $ a $ consisting of $ n $ zeros. You are also given a set of $ m $ not necessarily different segments. Each segment is defined by two numbers $ l_i $ and $ r_i $ ( $ 1 \le l_i \le r_i \le n $ ) and represents a subarray $ a_{l_i}, a_{l_i+1}, \dots, a_{r_i} $ of the array $ a $ .

Let’s call the segment $ l_i, r_i $ beautiful if the number of ones on this segment is strictly greater than the number of zeros. For example, if $ a = [1, 0, 1, 0, 1] $ , then the segment $ [1, 5] $ is beautiful (the number of ones is $ 3 $ , the number of zeros is $ 2 $ ), but the segment $ [3, 4] $ is not is beautiful (the number of ones is $ 1 $ , the number of zeros is $ 1 $ ).

You also have $ q $ changes. For each change you are given the number $ 1 \le x \le n $ , which means that you must assign an element $ a_x $ the value $ 1 $ .

You have to find the first change after which at least one of $ m $ given segments becomes beautiful, or report that none of them is beautiful after processing all $ q $ changes.

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases.

The first line of each test case contains two integers $ n $ and $ m $ ( $ 1 \le m \le n \le 10^5 $ ) — the size of the array $ a $ and the number of segments, respectively.

Then there are $ m $ lines consisting of two numbers $ l_i $ and $ r_i $ ( $ 1 \le l_i \le r_i \le n $ ) —the boundaries of the segments.

The next line contains an integer $ q $ ( $ 1 \le q \le n $ ) — the number of changes.

The following $ q $ lines each contain a single integer $ x $ ( $ 1 \le x \le n $ ) — the index of the array element that needs to be set to $ 1 $ . It is guaranteed that indexes in queries are distinct.

It is guaranteed that the sum of $ n $ for all test cases does not exceed $ 10^5 $ .

输出格式

For each test case, output one integer — the minimum change number after which at least one of the segments will be beautiful, or $ -1 $ if none of the segments will be beautiful.

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
6
5 5
1 2
4 5
1 5
1 3
2 4
5
5
3
1
2
4
4 2
1 1
4 4
2
2
3
5 2
1 5
1 5
4
2
1
3
4
5 2
1 5
1 3
5
4
1
2
3
5
5 5
1 5
1 5
1 5
1 5
1 4
3
1
4
3
3 2
2 2
1 3
3
2
3
1

样例输出 #1

1
2
3
4
5
6
3
-1
3
3
3
1

提示

In the first case, after first 2 changes we won’t have any beautiful segments, but after the third one on a segment $ [1; 5] $ there will be 3 ones and only 2 zeros, so the answer is 3.

In the second case, there won’t be any beautiful segments.

题解

题目解析

实际上是二分答案, 观察 $q$ , 如果在 $q_1$ 就已经可以满足有区间是优美区间, 那么 $q\ge q_1$ 就一定可以. 我们需要找到最小值, 这个答案有单调性, 那么我们就可以选择二分答案.

接下来是判断函数的书写: 那 么如何快速获取某个区间的 $1$ 的个数呢? 我们只需要存一下询问的位置, 然后扫一遍前缀和就好了.

时间复杂度为 $O((n+m+q)\log q)$ , 自然可以AC.

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;

#define endl "\n"
#define CIN_ ios::sync_with_stdio(0)
#define CIN cin.tie(0)
#define MAXN(size) const long long MAXN = size + 100
#define MOD(size) const long long MOD = size
#define mem(name,value) memset(name,value,sizeof(name))
#define fa(i,a,n) for(int i=a;i<=n;++i)
#define fb(i,a,n) for(int i=a;i>=n;--i)
#define T_ int T;cin >> T;while(T--)
typedef long long ll;
typedef unsigned long long ull;

MAXN(1e5);
int L[MAXN],R[MAXN],sum[MAXN],a[MAXN];
int n,m,q;

signed main(){
	CIN_;CIN;
	auto check = [](int x) -> bool{
		fa(i,0,n) sum[i] = 0;
		fa(i,1,x) sum[a[i]] = 1;
		fa(i,1,n) sum[i] += sum[i-1];
		fa(i,1,m) if(2 * (sum[R[i]] - sum[L[i]-1]) > R[i] - L[i] + 1) return true;
		return false;
	};
	T_{
		cin >> n >> m;
		fa(i,1,m){
			cin >> L[i] >> R[i];
		}
		cin >> q;
		fa(i,1,q){
			cin >> a[i];
		}
		int l=1,r=q,ans=-1;
		while(l <= r){
			int mid = (l + r) >> 1;
			if(check(mid)) r = mid - 1,ans = mid;
			else l = mid + 1;
		}
		cout << ans << endl;
	}
	return 0;
}