mayoko’s diary

プロコンとかいろいろ。

Educational Codeforces Round 10 D. Nested Segments

気づかなかった…ガックシ。Codeforces の data structure の問題解いてきます…

解法

条件は, 「a_i < a_j かつ b_j < b_i を満たすような (i, j) の組み合わせの数を求めること」です。

まず a_i の大きい順番にソートし, 順番に a_i を見ていくと, 後から見る a_i は, それ以前に考慮されたすべての a_j について, a_i < a_j を満たしています。後は b_j < b_i を満たしているかを調べれば良いですが, これは Binary Indexed Tree を使えば O(log N) で求められます。

落ち着いて条件書き下せば解けたかも…

// 0-based Binary Indexed Tree
// 数え上げ用
template<typename T> struct BIT {
    int max;
    vector<T> bit;
    BIT(int max) : max(max) {bit.resize(max+1);}
    // [0, i)
    T sum(int i) {
        T s = 0;
        while (i > 0) {
            (s += bit[i]);
            i ^= i&-i;
        }
        return s;
    }
    // 0-basedな座標iに値xを追加する
    void add(int i, T x) {
        ++i;
        while (i <= max) {
            (bit[i] += x);
            i += i&-i;
        }
    }
    // [a, b)
    T sum(int a, int b) {
        return sum(b)-sum(a);
    }
    // sum(0, i) >= wとなる最小のiを求める 存在しなければmaxを返す
    int lb(T w) {
        if (w <= 0) return 0;
        int k = 1;
        while (k <= max) k <<= 1;
        int i = 0;
        for (; k > 0; k >>= 1) if (i+k <= max && bit[i+k] < w) {
            w -= bit[i+k];
            i += k;
        }
        return i+1;
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> vs;
    vector<pair<pii, int> > lr(n);
    vector<ll> ret(n);
    for (int i = 0; i < n; i++) {
        cin >> lr[i].first.first >> lr[i].first.second;
        vs.push_back(lr[i].first.first);
        vs.push_back(lr[i].first.second);
        lr[i].second = i;
    }
    sort(vs.begin(), vs.end());
    for (int i = 0; i < n; i++) {
        lr[i].first.first = lower_bound(vs.begin(), vs.end(), lr[i].first.first) - vs.begin();
        lr[i].first.second = lower_bound(vs.begin(), vs.end(), lr[i].first.second) - vs.begin();
    }
    sort(lr.rbegin(), lr.rend());
    BIT<ll> bit(2*n);
    for (int i = 0; i < n; i++) {
        int index = lr[i].second, r = lr[i].first.second;
        ret[index] = bit.sum(r);
        bit.add(r, 1);
    }
    for (int i = 0; i < n; i++) cout << ret[i] << endl;
    return 0;
}