ABC038D - プレゼント

【関連】

• ABC231F - Jealous Two - 競プロはじめました

考え方

ABC231Fと類似の考え方．ただし，BITで区間和を取るのではなく，区間の最大値を求める．

最大値を求めるように，BIT (Binary Indexed Tree (BIT) / Fenwick Tree - 競プロはじめました) を書き換えればよい．

具体的には，$h$の昇順・$w$の降順で各点を見ていき，bit[w]で「$h, w$を一番外側にしたときの入れ子にできる最大数」を管理する．

get[w]で$w$以下の最大値を求められるとすれば，更新ルールは

• bit[w] = update(w, get(w - 1) + 1)
• ans = max(ans, get(w - 1) + 1)

となる．

回答例

N = int(input())
BOX = [tuple(map(int, input().split())) for _ in range(N)]
BOX.sort(key = lambda x: (x[0], -x[1]))

INF = 1 << 60
bit_size = 10 ** 5 + 1
bit = [0] * bit_size

def update(i, x):
  i += 1
  while i < bit_size:
      bit[i] = max(bit[i], x)
      i += i & -i

def get(i):
  ans = - INF
  i += 1
  while i > 0:
      ans = max(ans, bit[i])
      i -= i & -i
  return ans

ans = 0
for h, w in BOX:
  num = get(w - 1) + 1
  update(w, num)
  ans = max(ans, num)

print(ans)