問題概要

数直線上に $N$ 個の区間が与えられる。 $i$ 番目の区間は $\lbrack l_{i}, r_{i} \rbrack$ である。

これら区間の組であって、共有点をもつ (端点含む) ものの個数を求めよ。

制約

$2 \le N \le 5 \times 10^{5}$

考えたこと

公式解説では、互いに交差しない区間の個数を数える方針をとっている。また、「各 $r_{i}$ に対して、 $r_{i} \lt l_{j}$ となるような $j$ の個数」をしゃくとり法によって求めている。これはとても明快な解法だと思う。

ここでは、コンテスト中の自分の方法を書いておこうと思う。僕は区間に関する問題での定石に従って、「区間の始点でソートして考える」こととした (終点でソートすることが有効な場合もある)。

区間ソート

区間を始点が早い順に並び替えて、改めて区間の番号を $0, 1, \dots, N-1$ と振り直す。このとき、区間 $i$ と共有点をもつような区間 (のうち、番号が $i$ より大きいもの) の個数を数えることにしよう。

上図のように、区間 $i$ の終点 $r_{i}$ に対して

$l_{j} \le r_{i}$

を満たすような最大の $j$ を求める (たとえば lower_bound() などで求められる)。そうすると、区間 $i$ と共有点を持つような区間 (のうち、番号が $i$ より大きいもの) の個数は

$j - i$

と求められる。これを各 $i$ に対して足していけばよい。

上記の $j$ を求めるのに lower_bound() を用いた場合、全体の計算量は $O(N \log N)$ となる。

コード

#include <bits/stdc++.h>
using namespace std;
using pll = pair<long long, long long>;

int main() {
    int N;
    cin >> N;
    vector<pll> v(N);
    for (int i = 0; i < N; ++i) cin >> v[i].first >> v[i].second;
    
    // 区間を左端でソートする
    sort(v.begin(), v.end());
    
    // 区間の左端の座標たち
    vector<long long> lefts;
    for (int i = 0; i < v.size(); ++i) lefts.push_back(v[i].first);
 
    // 各区間について処理していく
    long long res = 0;
    for (int i = 0; i < v.size(); ++i) {
        int j = upper_bound(lefts.begin(), lefts.end(), v[i].second) - lefts.begin() - 1;
        res += j - i;
    }
    cout << res << endl;
}