题目描述

难度分:$1600$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 10^5$。

对于每组数据：

一开始，有一个长为$n$的全$0$数组$a$，下标从$1$开始。

输入$n$，$m(1 \leq m \leq n \leq 10^5)$以及$m$个非空连续子数组的左右端点$L$，$R$。

然后输入$q(1 \leq q \leq n)$和$q$个操作，每个操作输入一个下标$p$，表示把$a[p]$变成 $1$。保证所有$p$互不相同。

如果一个子数组中的$1$的个数比$0$多，则称这个子数组是优美的。输入的$q$个操作，按照输入顺序一个一个地执行。至少执行多少个操作，可以使$m$个子数组中有优美子数组？

如果执行完了也没有优美子数组，输出$-1$。

输入样例

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

输出样例

3
-1
3
3
3
1

算法

二分答案+主席树

思路比较好想，但是需要有一个好模板。比较容易想到的一个思路就是对每个区间$[l,r]$进行考虑，看区间变成优美最少需要多少次操作，求出所有区间变成优美的最少操作次数，它们之中的最小值就是答案。这个就存在单调性了，肯定是操作次数越多越容易变成优美子数组，可以二分出这个次数。

对于一个区间$[l,r]$，只需计算操作数组$queries$中前多少个元素在$[l,r]$之中，对于一个给定的前缀$[1,mid]$，分为以下两种情况：

1. 如果$[1,mid]$中在$[l,r]$内的元素$\geq \frac{r-l+1}{2}$，说明$mid$次操作可以让子数组$[l,r]$变优美，记录答案并往左搜索看操作次数能否更小。
2. 否则$mid$就太小了，应该往右搜索更大的操作次数。

而要计算$[1,mid]$中有多少个数在$[l,r]$之间，可以先计算出前缀$[1,mid]$中有多少个数$\leq r$，有多少个数$\leq l-1$，二者做差就是有多少个数在$[l,r]$之间。要计算出某个子数组中有多少个数不超过$x$使用主席树就能求解，套用主席树模板即可。

复杂度分析

时间复杂度

构建主席树的时间复杂度为$O(qlog_2n)$。一共$m$个区间，每个区间需要在$[1,q]$上进行二分，对于给定的$mid \in [1,q]$又要进行$O(log_2n)$的主席树查询，因此时间复杂度为$O(mlog_2qlog_2n)$。因此，整个算法的时间复杂度为$O(qlog_2n+mlog_2qlog_2n)$。

空间复杂度

空间的瓶颈在于主席树，这里我保守给了$40n$，这个规模的数组有$3$个，因此额外空间复杂度大概就是$O(120n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 100010, M = N*40;
int t, n, m, l, r, q, p;
int rt[N], lc[M], rc[M], sum[M], cnt;

void change(int l, int r, int &x, int y, int k){
    sum[x = ++cnt] = sum[y] + 1, lc[x] = lc[y], rc[x] = rc[y];
    if(l == r) return;
    int mid = l + r >> 1;
    if(k <= mid) {
        change(l, mid, lc[x], lc[y], k);
    }else {
        change(mid + 1, r, rc[x], rc[y], k);
    }
}

int ask(int l, int r, int x, int y, int ql, int qr){
    if(l == ql && r == qr) {
        return sum[y] - sum[x];
    }
    if(l == ql && r == qr) {
        return sum[y] - sum[x];
    }
    int mid = l + r >> 1;
    if(qr <= mid) {
        return ask(l, mid, lc[x], lc[y], ql, qr);
    }else if(ql > mid) {
        return ask(mid + 1, r, rc[x], rc[y], ql, qr);
    }else {
        return ask(l, mid, lc[x], lc[y], ql, mid) + ask(mid + 1, r, rc[x], rc[y], mid + 1, qr);
    }
}

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &n, &m);
        vector<array<int, 2>> intervals;
        for(int i = 1; i <= m; i++) {
            scanf("%d%d", &l, &r);
            intervals.push_back({l, r});
        }
        scanf("%d", &q);
        for(int i = 1; i <= q; i++) {
            scanf("%d", &p);
            change(1, N - 10, rt[i], rt[i - 1], p);
        }
        function<int(int, int, int)> query = [&](int l, int r, int x) {
            return ask(1, N - 10, rt[l - 1], rt[r], 1, x);
        };
        int ans = q + 1;
        for(auto&rng: intervals) {
            int l = rng[0], r = rng[1], len = r - l + 1, target = len>>1, res = -1;
            int low = 1, high = q;
            while(low <= high) {
                int mid = low + high >> 1;
                if(query(1, mid, r) - (l > 1? query(1, mid, l - 1): 0) > target) {
                    res = mid;
                    high = mid - 1;
                }else {
                    low = mid + 1;
                }
            }
            if(res != -1) {
                ans = min(ans, res);
            }
        }
        if(ans == q + 1) ans = -1;
        printf("%d\n", ans);
    }
    return 0;
}