ABC106 D - AtCoder Express 2

問題へのリンク (問題内容は省略)

atcoder.jp

考察

想定解ではなかったが、汎用性がありそうなのでメモしておく。

各クエリに対して効率的に求めたいが、 をそのままにして考えるのは難しい。( 例えば、 について昇順でソートしても、 について単調性がある保証がないので、二分探索などができない。)

列車とクエリの区間をまとめて について昇順にソートしてみる。( 思考過程も書きたかったが省略… )
が等しいときはクエリが先にくるようにしておく。
ソートされた順にデータを見ると、クエリに訪れたときに、クエリ以降の列車で条件を満たすのは、右端がクエリの右端以下になっているものである。
昇順に並んでいるので、左端に関しては考慮する必要がない。
この条件を満たす個数を求めて保存していけばよい。
個数は、右端を添え字として列車の個数を累積和で持っておくことで求めることができる。
データを順に見ているときに、列車に関する情報であるときは、以降で現れるクエリで考慮しないように減算しておく。
この解き方だと、区間和取得と一点更新が効率的に行えるデータ構造が必要であるが、Segment Tree や Binary Indexed Tree (Fenwick Tree) を用いればよい。

計算量は となる。

ソートによって左端を考慮する必要なくすことで、右端を点としてみることを可能にするという考え方を、すぐにアウトプットできるようにインプットしておくべきだと感じた。

コード

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
using namespace std;

template<typename T>
struct BinaryIndexedTree{
    vector<T> data;
    int sz;

    BinaryIndexedTree(int n){
        sz = n + 1;
        data.assign(sz, 0);
    }

    void add(int i, T x){
        ++i;
        while(i < sz){
            data[i] += x;
            i += i & -i;
        }
    }

    // [0, i] の区間和
    T sum(int i){
        T res = 0;
        ++i;
        while(i > 0){
            res += data[i];
            i -= i & -i;
        }
        return res;
    }

    // [l, r) の区間和
    T sum(int l, int r){
        return sum(r - 1) - sum(l - 1);
    }

    // val 以上を満たす 0-indexed の位置を返す
    int lower_bound(T val){
        // if(val <= 0)    return -1;
        int res = 0;
        int n = 1;
        while(n < sz)   n <<= 1;
        for(int k = n >> 1; k > 0; k >>= 1){
            if(res + k < sz && data[res + k] < val){
                val -= data[res + k];
                res += k;
            }
        }
        return res;
    }
};

int main(){
    int n, m, q;
    cin >> n >> m >> q;
    vector<tuple<int, int, int>> table;
    // bit.data[i] := 右端が i である列車の個数
    BinaryIndexedTree<int> bit(n + 1);
    for(int i = 0; i < m; ++i){
        int l, r;
        cin >> l >> r;
        table.emplace_back(l, q, r);
        bit.add(r, 1);
    }
    for(int i = 0; i < q; ++i){
        int l, r;
        cin >> l >> r;
        table.emplace_back(l, i, r);
    }
    // 列車とクエリを左端昇順ソート (左端が同じものはクエリが先にくるようにする。)
    // こうすることで、クエリの区間に対して左端がはみ出たものを考慮せずに済む。
    sort(table.begin(), table.end());

    vector<int> ans(q);
    for(auto tup : table){
        int i = get<1>(tup);
        // 列車であれば、以降は利用しないので減算しておく。
        if(i == q)  bit.add(get<2>(tup), -1);
        // クエリであれば、[l, r] に含まれる列車の個数を取得する。
        else{
            int l = get<0>(tup), r = get<2>(tup);
            ans[i] = bit.sum(l, r + 1);
        }
    }
    for(int x : ans)    cout << x << '\n';
}

雑記

二次元平面上で考えることで の組を点で管理できる。
今回は の制約が小さいので、二次元累積和でこれを管理できる。
二次元で問題を捉える考え方が苦手なのでものにしたいものである。
何回も解き直してるんだけど、スラスラと解けるようにはなかなかならないね。
競プロやってたら一日が終わっているが…？