E. Tracking Segments

E. Tracking Segments

题目大意：

给一个全为零的数组，m次询问区间，q次修改，定义一个区间中的1个数严格大于0个数为漂亮，问在第几次修改后出现了第一个完美区间。

思路：

对修改次数进行二分，利用前缀和判断区间中的1个数，时间复杂度为$mlog(q)$

code

int n, m;
int b[N];
vector<pii> a;
bool check(int op)
{
    int pre[n + 1] = {0}, res[n + 1] = {0};
    for (int i = 1; i <= op; ++i)
        res[b[i]] = 1;
    for (int i = 1; i <= n; ++i)
        pre[i] = pre[i - 1] + res[i];
    for (auto [l, r] : a)
        if (2 * (pre[r] - pre[l - 1]) > r - l + 1)
            return true;
    return false;
}
void solved()
{
    cin >> n >> m;
    a.resize(m);
    for (int i = 0; i < m; ++i)
    {
        int x, y;
        cin >> x >> y;
        a[i] = {x, y};
    }
    int q;
    cin >> q;
    for (int i = 1; i <= q; ++i)
    {
        int tot;
        cin >> tot;
        b[i] = tot;
    }
    int l = 0, r = q + 1;
    while (l + 1 < r)
    {
        int mid = (l + r) >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid;
    }
    if (r != q + 1)
        cout << r << endl;
    else
        cout << -1 << endl;
}