链接
https://codeforces.com/problemset/problem/1843/E
题面
思路
二分加树状数组。关键点在于看出来单点修改和区间查询,然后离线+二分:令l=1(1次操作),r=q(最多q次操作)。二分判断能不能行。
以及树状数组的板子要记得。
代码
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<sstream>
#include<string>
#include<string.h>
#include<iomanip>
#include<stdlib.h>
#include<map>
#include<queue>
#include<limits.h>
#include<climits>
#include<fstream>
#include<stack>
#define IOS ios::sync_with_stdio(false), cin.tie(0) ,cout.tie(0)
using namespace std;
#define int long long
const int N = 1e5 + 10;
struct ele
{
int begin, end;
int length;
}eles[N];
bool cmp(ele a, ele b) { return a.length < b.length; }
int lowbit(int x) { return x & (-x); }
int a[N];
void update(int x)
{
while (x < N)
{
a[x]++;
x += lowbit(x);
}
}
int n, m;
int sum(int x)
{
int ans = 0;
while (x > 0)
{
ans += a[x];
x -= lowbit(x);
}
return ans;
}
vector<int>vt;
bool check(int nm)
{
memset(a, 0, sizeof(a));
for (int i = 1; i <= nm; i++)
{
update(vt[i]);
}
bool fa = false;
for (int i = 1; i <= m and !fa; i++)
{
int xnoe = sum(eles[i].end) - sum(eles[i].begin - 1);
if (xnoe>= eles[i].length / 2 + 1)fa = true;
}
return fa;
}
signed main()
{
IOS;
int t; cin >> t;
while (t--)
{
vt.clear();
vt.push_back(0);
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int l; int r;
cin >> l >> r;
eles[i].begin = l, eles[i].end = r;
eles[i].length = r - l + 1;
}
int q; cin >> q;
int x;
for (int i = 0; i < q; i++) { cin >> x; vt.push_back(x); }
int l = 1, r = q;
while (l < r)
{
int m = (l + r ) / 2;
if (check(m))r = m;
else l = m + 1;
}
if (r == q and !check(r))cout << -1;
else cout << r;
cout << '\n';
}
return 0;
}
标签:Tracking,int,Segments,cin,while,length,eles,include
From: https://www.cnblogs.com/zzzsacmblog/p/18299744