Submission #1635962

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define pb push_back
#define all(r) (r).begin(),(r).end()
#define rall(r) (r).rbegin(),(r).rend()
#define fi first
#define se second

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;

// 区間加算　最小値取得
template <typename T>
struct SegTree {
    vector<T> segVal;
    vector<T> segAdd;
    int n;
    const T Default;
    const T MAX;
    SegTree(int n_, const T& def, const T& MAX) : Default(def), MAX(MAX) {init(n_);}
    void init(int n_) {
        n = 1;
        while (n < n_) n *= 2;
        segVal = vector<T>(2 * n - 1, Default);
        segAdd = vector<T>(2 * n - 1);
    }
    T f(const T& a, const T& b) {
        return min(a, b);
    }
    void add(int a, int b, const T& x) {
        add(a, b, x, 0, 0, n);
    }
    void add(int a, int b, const T& x, int k, int l, int r) {
        if (r <= a || b <= l) return; //もし交差しない区間であれば終える.

        if (a <= l && r <= b) { //もし今みている区間[l, r)が[a, b)に完全に内包されていれば
            segAdd[k] += x;  //区間[l, r)にkを加算する.
            return;
        }

        add(a, b, x, k * 2 + 1, l, (l + r) / 2); //子の区間に(必要があれば)xを加算する.
        add(a, b, x, k * 2 + 2, (l + r) / 2, r); //〃

        //親の区間の最小値は, 子の区間の最小値 + 自分に一様に加算されている値 である.一様に加算される値は更新しなくて良い.
        segVal[k] = min(segVal[k * 2 + 1] + segAdd[k * 2 + 1], segVal[k * 2 + 2] + segAdd[k * 2 + 2]);
    }
    T query(int a, int b, int k, int l, int r ) {
        if (r <= a || b <= l) return (MAX);

        if (a <= l && r <= b) return (segVal[k] + segAdd[k]); //完全に内包されていれば,その区間の最小値を返す.

        T left = query(a, b, k * 2 + 1, l, (l + r) / 2); //子の区間の最小値を求める.
        T right = query(a, b, k * 2 + 2, (l + r) / 2, r); //子の区間の最小値を求める

        return (f(left, right) + segAdd[k]); //親の区間の最小値は, 子の区間の最小値 + 自分に一様に加算されている値 である (大切なので2回書きました!!)

    }
    T query(int a, int b) {
        return query(a, b, 0, 0, n);
    }
};


int main() {
#ifdef LOCAL_TEST
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    // cerr << "Start" << endl;
    int n, m;
    cin >> n >> m;
    SegTree<ll> st(n, 0LL, 1e18);
    vi s(m), t(m);
    rep(i, m) {
        cin >> s[i] >> t[i];
        s[i]--;
        st.add(s[i], t[i], 1);
    }
    if (st.query(0, n) == 0) {
        cout << 0 << endl;
        return 0;
    }
    vector<int> ans;
    rep(i, m) {
        st.add(s[i], t[i], -1);
        // cerr << s[i] << " " << t[i] << " " << st.query(s[i], t[i]) << endl;
        if (st.query(s[i], t[i]) != 0) ans.pb(i + 1);
        st.add(s[i], t[i], +1);
    }
    cout << ans.size() << endl;
    for (auto& a : ans) cout << a << endl;
    return 0;
}

Submission Info

Judge Result