問題概要

$N$ 個のマス $1, 2, \dots, N$ がある。 $M$ 個の区間があって、それぞれマス $S_{i}$ からマス $T_{i}$ までを連続して覆っている。 $M$ 個の区間によって一回以上被覆されるマスの集合を $P$ とする。

各区間について、その区間を除外してできる残りの $M-1$ 個の区間によって被覆されるマスの集合が $P$ であるかどうかを判定せよ。

制約

$1 \le N \le 3 \times 10^{5}$
$1 \le M \le 10^{5}$

考えたこと

まず、各マスが $M$ 個の区間によって何回被覆されるかをいもす法によって求めよう！

num[x]：マス $x$ が何個の区間によって被覆されるか

このとき、 $M$ 個の区間について、次の判定が高速にできればよい。

区間 $\lbrack S_{i}, T_{i} \rbrack$ 内に、num[x] < 2 となるようなマス $x$ が存在しないとき、その区間は除外可能である

これを判定するためには、累積和が使える。つまり、

sum[x]：左から $x$ マス分について、num の値が 2 未満であるようなものの個数

を求めよう。そうすれば、sum[T[i]] - sum[S[i]] の値が 0 であるかどうかを判定すればよいこととなる。

全体として、 $O(N + M)$ の計算量で解ける。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 入力と imos 法
    int N, M;
    cin >> N >> M;
    vector<int> num(N+1, 0), S(M), T(M);
    for (int i = 0; i < M; i++) {
        cin >> S[i] >> T[i];
        S[i]--;

        num[S[i]]++;
        num[T[i]]--;
    }
    for (int i = 0; i < N; i++) num[i+1] += num[i];

    // 区間内の、num[x] = 1 となる x の個数を求めるための累積和配列
    vector<int> sum(N+1, 0);
    for (int i = 0; i < N; i++) {
        int add = 0;
        if (num[i] < 2) add = 1;
        sum[i+1] = sum[i] + add;
    }

    // 各区間を考える
    vector<int> res;
    for (int i = 0; i < M; i++) {
        int violent_num = sum[T[i]] - sum[S[i]];
        if (violent_num == 0) res.push_back(i);
    }
    cout << res.size() << endl;
    for (auto v : res) cout << v+1 << endl;
}