LoginSignup
2

More than 3 years have passed since last update.

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

Last updated at Posted at 2020-04-02

はじめに

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


問題


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' で実装できる.
Untitled.png

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する点にも注意すべし.

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2