B - ドキドキデート大作戦高橋君 AtCoder Regular Contest 045

問題概略
B: ドキドキデート大作戦高橋君 - AtCoder Regular Contest 045 | AtCoder
いくつかの区間が与えられる。それらの区間の中で、除いてもすべてを被覆出来る区間を出力せよ。

制約
10^5

解法
現状取り除いても大丈夫な区間を簡単に扱いたい。
いもす法を使い、複数の区間で覆われている場所を1、その他を0とした時、ある区間を除けるならその区間の数字がすべて1である
累積を求めておけば、ある区間の数字がすべて1かO(1)でわかる。

   public static void solve() throws Exception {
        //longを忘れるなオーバーフローするぞ
        N = ni();
        M = ni();
        int[] f = niah(M, 2);
        int[] t = niah(M, 2);
        int[] imosu = imosu(f, t, N + 5);
        for (int i = 0; i < imosu.length; i++) {
            if (imosu[i] > 1) imosu[i] = 1;
            else imosu[i] = 0;
        }
        for (int i = 0; i < imosu.length - 1; i++) {
            imosu[i + 1] += imosu[i];
        }
        ArrayList<Integer> res = new ArrayList<>();
        for (int i = 0; i < M; i++) {
            if (imosu[t[i]] - imosu[f[i] - 1] == t[i] - f[i]+1) res.add(i + 1);
        }
        System.out.println(res.size());
        print(res);

    }