イベントソートを勉強してみた【競プロ】

#はじめに
イベントソートという用語で検索してもあまり説明しているサイトがなかったので勉強がてら書いていきます!!!!

---

###問題

1.
N回, 整数Si, Ti, Xiが与えられる.
地点[Si, Ti)(←半区間)にXiを定義する(重複してもよい).
2.
Q個の以下のクエリに対して答えを出力しなさい.
  query :地点Diの位置に定義されているXiの最小値を答えよ.
[制約]
1 <= N, Q <= 2×10^5

N, Qに対しての制約しか書いていないが, だいたいこのような問題を考える.
###解説
まず, 数直線を考える.
-から+を見ていくこととする.
もし見ていった先にSiがあれば区間iに入ったこととなる.
またTiがあれば区間iを出たことになる.
これを言い換える.

ある地点Djを考えた時に
Si <= DjであればDjはその区間iに入っている.
Ti <= DjであればDjはその区間iから出ていることになる.

c++では, これは重複を許す順序付き集合 'multiset' で実装できる.

Djを見る時にDj以下のSi, Tiに対して

1. 追加イベント(Si, 1, Xi)
2. 削除イベント(Ti, -1, Xi)
   を行う.
   追加イベントとは, Xiをmultisetにinsertすることで
   削除イベントとは, Xiをmultisetから一つeraseすることである.

地点Djの位置に定義されているXiの最小値は, 以上の処理を行なった後のmultisetの最小値である.
実際のコードは以降ネタバレを参照してほしい.

---

#以降ネタバレ
##練習問題
AtCoderより
・ ABC128 E問題
https://atcoder.jp/contests/abc128/tasks/abc128_e
・ 全国統一プログラミング王決定戦本戦 D問題
https://atcoder.jp/contests/nikkei2019-final/tasks/nikkei2019_final_d

E問題解答

#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define rep2(i, s, n) for(int i=s; i<(n); ++i)
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;

struct event{
    ll t, type, val;
    bool operator<(const event& a){
        return t < a.t;
    }
};

int main(int argc, const char * argv[]) {
    // input
    cout << fixed << setprecision(10);
    ll N, Q; cin >> Q >> N;
    vector<event> eves;
    vector<ll> D(N);
    rep(i, Q){
        ll s, t, q;
        cin >> s >> t >> q;
        eves.push_back({s-q, 1, q}); // ins
        eves.push_back({t-q, -1, q}); // erase
    }
    rep(i, N){
        cin >> D[i];
    }

    sort(ALL(eves));

    int k = 0;
    multiset<ll> st;
    rep(i, N){
        // D[i]以下のイベントを全て処理する(stにins, erase)
        while(k < eves.size() && eves[k].t <= D[i]){
            if(eves[k].type == 1){
                st.insert(eves[k].val);
            }
            else {
                st.erase(st.find(eves[k].val));
            }
            k++;
        }

        // stの最小値を調べて出力
        if(st.empty()){
            cout << -1 << endl;
        }
        else{
            cout << *st.begin() << endl;
        }
    }
    return 0;
}

#終わり
イベントソートの用語自体は, ABC128のEの解説で有名になったようです(？）

コーディングの時, multisetではなくsetを使っていて無限時間かかった.
あと, multisetのerase(x)がxの値全てeraseする点にも注意すべし.