結果

問題 No.2154 あさかつの参加人数
コンテスト
ユーザー titan23
提出日時 2023-01-20 14:11:31
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,357 ms / 2,000 ms
コード長 4,131 bytes
コンパイル時間 522 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 91,008 KB
最終ジャッジ日時 2024-12-27 05:48:27
合計ジャッジ時間 24,892 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = lambda: sys.stdin.readline().rstrip()

from typing import List, Iterable


class FenwickTreeRAQ:

  '''Build a new FenwickTreeRAQ.'''
  def __init__(self, n: int, a: Iterable[int]=[]):
    self._n = n
    self.bit0 = FenwickTree(n+1)
    self.bit1 = FenwickTree(n+1)
    for i, a_ in enumerate(a):
      self.add(i, a_)

  '''Add x to a[k]. / O(logN)'''
  def add(self, k: int, x: int) -> None:
    self.add_range(k, k+1, x)

  '''Add x to [l, r). / O(logN)'''
  def add_range(self, l: int, r: int, x: int) -> None:
    self.bit0.add(l, -x*l)
    self.bit0.add(r, x*r)
    self.bit1.add(l, x)
    self.bit1.add(r, -x)

  '''Return sum [l, r). / O(logN)'''
  def sum(self, l: int, r: int) -> int:
    return self.bit0.pref(r) + r*self.bit1.pref(r) - self.bit0.pref(l) - l*self.bit1.pref(l)

  def to_l(self) -> List[int]:
    return [self.sum(i, i+1) for i in range(self._n)]

  def __getitem__(self, k: int):
    return self.sum(k, k+1)

  def __str__(self):
    return '[' + ', '.join(map(str, (self.__getitem__(i) for i in range(self._n)))) + ']'

  def __repr__(self):
    return 'FenwickTreeRAQ(' + str(self) + ')'


from typing import List, Union


class FenwickTree:

  '''Build a new FenwickTree. / O(N)'''
  def __init__(self, _n_or_a: Union[List[int], int]):
    if isinstance(_n_or_a, int):
      self._size = _n_or_a
      self._tree = [0] * (self._size+1)
    else:
      a = list(_n_or_a)
      self._size = len(a)
      self._tree = [0] + a
      for i in range(1, self._size):
        if i + (i & -i) <= self._size:
          self._tree[i + (i & -i)] += self._tree[i]
    self._s = 1 << (self._size-1).bit_length()

  '''Return sum([0, r)) of a. / O(logN)'''
  def pref(self, r: int) -> int:
    # assert r <= self._size
    ret = 0
    while r > 0:
      ret += self._tree[r]
      r -= r & -r
    return ret

  '''Return sum([l, n)) of a. / O(logN)'''
  def suff(self, l: int) -> int:
    # assert 0 <= l < self._size
    return self.pref(self._size) - self.pref(l)

  '''Return sum([l, r)] of a. / O(logN)'''
  def sum(self, l: int, r: int) -> int:
    # assert 0 <= l <= r <= self._size
    return self.pref(r) - self.pref(l)

  def __getitem__(self, k: int) -> int:
    return self.sum(k, k+1)

  '''Add x to a[k]. / O(logN)'''
  def add(self, k: int, x: int) -> None:
    # assert 0 <= k < self._size
    k += 1
    while k <= self._size:
      self._tree[k] += x
      k += k & -k

  '''Update A[k] to x. / O(logN)'''
  def set(self, k: int, x: int) -> None:
    pre = self.get(k)
    self.add(k, x - pre)

  '''bisect_left(acc)'''
  def bisect_left(self, w: int) -> int:
    i = 0
    s = self._s
    while s:
      if i + s <= self._size and self._tree[i + s] < w:
        w -= self._tree[i + s]
        i += s
      s >>= 1
    return i if w else None

  '''bisect_right(acc)'''
  def bisect_right(self, w: int) -> int:
    i = 0
    s = self._s
    while s:
      if i + s <= self._size and self._tree[i + s] <= w:
        w -= self._tree[i + s]
        i += s
      s >>= 1
    return i

  def show(self) -> None:
    print('[' + ', '.join(map(str, (self.pref(i) for i in range(self._size+1)))) + ']')

  def to_l(self) -> List[int]:
    return [self.__getitem__(i) for i in range(self._size)]

  @classmethod
  def inversion_num(self, a: List[int], compress: bool=False) -> int:
    ans = 0
    if compress:
      a_ = sorted(set(a))
      z = {e: i for i, e in enumerate(a_)}
      fw = FenwickTree(len(a_))
      for i, e in enumerate(a):
        ans += i - fw.pref(z[e])
        fw.add(z[e], 1)
    else:
      fw = FenwickTree(len(a))
      for i, e in enumerate(a):
        ans += i - fw.pref(e)
        fw.add(e, 1)
    return ans

  def __str__(self):
    sub = [self.pref(i) for i in range(self._size+1)]
    return '[' + ', '.join(map(str, (sub[i+1]-sub[i] for i in range(self._size)))) + ']'

  def __repr__(self):
    return 'FenwickTree(' + str(self) + ')'



#  -----------------------  #

n, m = map(int, input().split())  
fw = FenwickTreeRAQ(n+1)
for _ in range(m):
  l, r = map(int, input().split())
  fw.add_range(r, l+1, 1)
for i in range(n, 0, -1):
  print(fw[i])
0