문제 설명
n개의 0으로 초기화된 배열 a가 주어집니다. 또한 m개의 구간이 주어지며, 각 구간은 l_i와 r_i(1 ≤ l_i ≤ r_i ≤ n)로 정의됩니다. 이는 배열 a의 부분 배열 a[l_i], a[l_i+1], ..., a[r_i]를 의미합니다.
특정 구간에서 1의 개수가 0의 개수보다 크다면 해당 구간을 아름다운 구간이라고 합니다. 예를 들어, a = [1, 0, 1, 0, 1]인 경우 구간 [1, 5]는 1이 3개, 0이 2개이므로 아름다운 구간이지만, 구간 [3, 4]는 1과 0이 각각 1개씩이므로 아름답지 않습니다.
q개의 변경 연산이 주어집니다. 각 변경에서는 인덱스 x(1 ≤ x ≤ n)를指定하고, 배열의 해당 위치에 1을 저장해야 합니다. 변경에 사용되는 인덱스들은 서로 다릅니다.
목표는 q개의 변경을 차례대로 수행한 후, m개의 구간 중 최소 하나가 아름다워지는 최소 변경 횟수를 찾는 것입니다. 모든 변경을 수행한 후에도 아름다운 구간이 없다면 -1을 출력합니다.
입력 형식
첫 줄에 테스트 케이스 수 t(1 ≤ t ≤ 10^4)가 주어집니다.
각 테스트 케이스에서:
- 첫 번째 줄에 n과 m(1 ≤ m ≤ n ≤ 10^5)이 주어집니다.
- 接下来的 m개 줄에는 각 구간의 l_i와 r_i가 주어집니다.
- 그 다음 줄에 q(1 ≤ q ≤ n)가 주어집니다.
- 다음 q개 줄에는 각 변경의 인덱스 x가 주어집니다. (모든 인덱스는 서로 다릅니다)
모든 테스트 케이스의 n 합은 10^5를 초과하지 않습니다.
출력 형식
각 테스트 케이스마다, 최소 몇 번째 변경 이후에 첫 번째로 아름다운 구간이出现하는지 출력합니다. 그런 구간이 존재하지 않으면 -1을 출력합니다.
접근 방법
이 문제는 이분 탐색과 구간 누적합을 결합하여 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다:
1. 변경이 적용된 후 각 위치에 1이 설정되었는지 여부를 표시하는 배열을 사용합니다.
2. 구간 누적합을 통해任意 구간 내의 1 개수를 O(1)时间内에 구할 수 있습니다.
3. 주어진 구간에서 1의 개수가 0의 개수보다 많다는 조건은 다음과 같이 표현됩니다:
ones > zeros ones > (区间长度 - ones) 2 * ones >区间长度
4. 이분 탐색을 사용하여 최소 변경 횟수를 찾습니다. 각 중간값에 대해 해당 시점까지 변경을 적용하고,美丽的 구간이 있는지 확인합니다.
알고리즘
check(k) 함수를 통해 처음 k개의 변경을 적용한 후 아름다운 구간이 있는지 검증합니다:
- 长度为 n인 배열을 0으로 초기화합니다.
- 앞에서 k개의 변경 인덱스에 대해 표시 배열을 1로 설정합니다.
- 누적 합 배열을 구성합니다.
- 각 구간 [l_i, r_i]에 대해:
- 해당 구간内的 1 개수를 누적 합으로 계산합니다.
- 조건 2 * ones > (r_i - l_i + 1)을 확인합니다.
- 조건을 만족하면 true를 반환합니다.
- 어떤 구간도 조건을 만족하지 않으면 false를 반환합니다.
메인 함수에서는 이분 탐색을 수행하여 정답을 찾습니다. 찾지 못한 경우 -1을 출력합니다.
복잡도 분석
각 check 함수는 O(n + m)의 시간이 소요됩니다. 이분 탐색으로 O(log q)번 호출하므로 총 시간 복잡도는 O((n + m) * log q)입니다. 메모리 사용량은 O(n + m)입니다.
구현 예시
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000000;
int n, t;
int query[MAXN];
int mark[MAXN];
int prefix[MAXN];
int leftBound[MAXN];
int rightBound[MAXN];
int segmentCount;
bool verify(int k)
{
for (int i = 1; i <= n; i++) {
prefix[i] = 0;
mark[i] = 0;
}
for (int i = 1; i <= k; i++) {
mark[query[i]] = 1;
}
for (int i = 1; i <= n; i++) {
prefix[i] = prefix[i - 1] + mark[i];
}
for (int i = 1; i <= segmentCount; i++) {
int start = leftBound[i];
int end = rightBound[i];
int onesInSegment = prefix[end] - prefix[start - 1];
int segmentLength = end - start + 1;
if (onesInSegment * 2 > segmentLength) {
return true;
}
}
return false;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> t;
while (t--) {
cin >> n >> segmentCount;
for (int i = 1; i <= segmentCount; i++) {
cin >> leftBound[i] >> rightBound[i];
}
int q;
cin >> q;
for (int i = 1; i <= q; i++) {
cin >> query[i];
}
int low = 1, high = q + 1;
bool found = false;
while (low < high) {
int mid = low + (high - low) / 2;
if (verify(mid)) {
high = mid;
found = true;
} else {
low = mid + 1;
}
}
if (!found) {
cout << -1 << '\n';
} else {
cout << high << '\n';
}
}
return 0;
}
이 구현은 문제의 요구사항을 충족하며, 이분 탐색을 통해 최소 변경 횟수를 효율적으로 찾습니다.