競プロ典型90問 081 Friendly Group(★5)
$ K, A_i, B_i \leq 5000という制約に注目すると, $ A_i, B_iを平面上にプロットできるということがわかる. そこで二次元配列$ aをもっておき, $ a_{A_i}{B_i}に$ 1を加算することで, 求めたい和の最大値は長方形領域内の要素の総和の最大値と言い換えられる. これは, 二次元累積和をとっておくことで高速に計算できる.
よってこの問題を, $ P = 5000として, $ O(N + P^2)で解くことができた.