Codeforces Round 881 E. Tracking Segments

[Woodyiiiiiii]

Codeforces Round 881 E. Tracking Segments

https://codeforces.com/contest/1843/problem/E

这道题我又被固定思维控制住了，以为是线断树/树状数组，然后就在每次change中用树状数组表示变化，这样保证在n的外层循环下用不到n的时间完成变化表示。但问题是，接下来我如何统计segments是否符合呢？这样如何都会消耗O(n)复杂度了，保证TLE。

那么要想一种办法合理安排统计顺序。抛弃掉线断树的思路。

看到题目最终求得是首个满足条件的改变参数，不妨用二分确定答案，并且在判断segments的时候要求一次遍历，这就要用到前缀和了。

总结：

1. 不要被固定思维、方法和套路限定住，勇于跳出，老毛病了
2. 二分和前缀和的思想很重要

import java.io.*;
import java.util.*;

/**
 * codeforces template
 */
public class Main {

    static final Reader RR = new Reader(System.in);
    static final PrintWriter PP = new PrintWriter(System.out, true);

    public static void main(String[] args) throws IOException {
        int T = RR.nextInt();
        while (T -- > 0) {
            int n = RR.nextInt(), m = RR.nextInt();
            int[][] segs = new int[m][2];
            for (int i = 0; i < m; i++) {
                segs[i][0] = RR.nextInt();
                segs[i][1] = RR.nextInt();
            }
            int q = RR.nextInt();
            int[] qs = new int[q];
            for (int i = 0; i < q; i++) {
                qs[i] = RR.nextInt();
            }
            solve(n, m, segs, q, qs);
        }
    }

    private static void solve(int n, int m, int[][] segs, int q, int[] qs) {
        int l = 0, r = q;
        int[] cnt = new int[n], sum = new int[n];
        while (l < r) {
            int mid = (l + r) >> 1;
            if (ok(mid, n, m, segs, q, qs, cnt, sum)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        if (l == q) {
            PP.println(-1);
        } else {
            PP.println(l + 1);
        }
    }

    private static boolean ok(int mid, int n, int m, int[][] segs, int q, int[] qs, int[] cnt, int[] sum) {
        Arrays.fill(cnt, 0);
        Arrays.fill(sum, 0);
        for (int i = 0; i <= mid; i++) {
            cnt[qs[i] - 1] ++;
        }
        for (int i = 0; i < n; i++) {
            sum[i] = cnt[i] + (i == 0 ? 0 : sum[i - 1]);
        }
        for (int i = 0; i < m; i++) {
            int ll = segs[i][0] - 1, rr = segs[i][1] - 1;
            int oneCnt = sum[rr] - (ll == 0 ? 0 : sum[ll - 1]);
            if (oneCnt > (rr - ll + 1) / 2) {
                return true;
            }
        }
        return false;
    }



    static class Reader {
        private final BufferedReader reader;
        private StringTokenizer tokenizer;

        public Reader(InputStream inputStream) {
            this.reader = new BufferedReader(new InputStreamReader(inputStream), 65536);
            this.tokenizer = new StringTokenizer("");
        }

        public String next() throws IOException {
            while (!tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(reader.readLine());
            }
            return tokenizer.nextToken();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

    }

}