CF-[CF1843E] Tracking Segments 题解

XSean · 2023-06-21 09:17:41 · 题解

E：Tracking Segments

Problem - E - Codeforces

基本思路：

思路：求最小变化数，使用对变化进行二分的方法，然后再用最多 O(N) 的方法 check 出整段序列是否有符合条件的区间即可。方法就是利用前缀和求得一段区间的 1 的数量再与区间长度比较即可。

时间复杂度：O(N\log Q)。

代码实现：

代码应该很好理解，就不多解释了。

核心代码：

const int N = 2e5 + 10;
int n, m;
int L[N], R[N];
int a[N], p[N];
int s[N];
void cover(int indx){
    rep(i, 1, n) a[i] = 0;
    rep(i, 1, indx) a[p[i]] = 1;
}
bool check(){
    int len, k;
    rep(i, 1, n) s[i] = s[i - 1] + a[i];
    rep(i, 1, m){
        len = R[i] - L[i] + 1;
        k = s[R[i]] - s[L[i] - 1];
        if(k * 2 > len) return 1; 
    }
    return 0;
}
int main(){
    int T; rd(T);
    while(T--){
        rd(n, m);
        rep(i, 1, m) rd(L[i], R[i]);
        int q; rd(q);
        rep(i, 1, q) rd(p[i]);
        cover(q);
        if(!check()){
            puts("-1");
            continue;
        }
        int l = 1, r = q;
        while(l < r){
            int mid = (l + r) >> 1;
            cover(mid);
            if(!check()) l = mid + 1;
            else r = mid;
        }
        prf("%d\n", l);
    }
    return 0;
}

完整代码