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; }