E. Tracking Segments

Problem - E - Codeforces

题目大意：有一个长为n的二进制字符串，初始全为0，给出m个字符串内的区间，和q次操作，每次操作将1个位置上的字符变成1，问至少要几次操作能使m个区间内的至少一个满足区间内1的数量多于0的数量

1<=m<=n<=1e5;1<=q<=1e5

思路：可以二分答案，我们先把所有操作放到一个数组b里，然后二分枚举最少操作数x，然后取出数组b中的前x个，将其按照操作的位置从小到大排序，得到数组c，然后遍历每一个区间，在c中二分查找到左右端点的位置，两个位置之间有多少个数就是有多少个1，区间内其他的元素就是0，最后判断1的数量是否大于0的数量，大于就少操作，否则增加操作次数

//#include<__msvc_all_public_headers.hpp>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
pair<int,int> a[N];
int b[N];
int c[N];
ll n, m;
bool check(int x)
{
	for (int i = 1; i <= x; i++)
	{//取出前x个操作的位置
		c[i] = b[i];
	}
	sort(c + 1, c + x + 1);//从小到大排序来二分查找
	for (int i = 1; i <= m; i++)
	{
		int it1 = lower_bound(c + 1, c + x + 1, a[i].first)-c;//查找当前区间左端点在c中的哪
		if (it1 == x + 1)
			continue;
		int it2 = upper_bound(c + 1, c + x + 1, a[i].second) - c;//右端点的再右一个位置
		it2--;
		int cnt1 = it2 - it1 + 1;//区间内1的数量
		int tot = a[i].second - a[i].first + 1;//区间内总元素数
		if (cnt1 > tot / 2)
			return 1;
	}
	return 0;
}
int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
	int t;
	cin >> t;
	while (t--)
	{
		cin >> n>>m;
		for (int i = 1; i <= m; i++)
		{//记录区间
			cin >> a[i].first >> a[i].second;
		}
		int q;
		cin >> q;
		for (int i = 1; i <= q; i++)
		{//记录操作位置
			cin >> b[i];
		}
		int l = 1, r = q, ans=-1;
		while (l <= r)
		{//二分最小操作次数
			int mid = (l + r) >> 1;
			if (check(mid))
			{
				ans = mid;
				r = mid - 1;
			}
			else
			{
				l = mid + 1;
			}
		}
		cout << ans << endl;
	}
	return 0;
}