結果

問題 No.3103 Butterfly Effect
コンテスト
ユーザー nasutarou1341
提出日時 2025-04-11 23:00:54
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 11,482 bytes
コンパイル時間 309 ms
コンパイル使用メモリ 82,416 KB
実行使用メモリ 194,624 KB
最終ジャッジ日時 2025-04-11 23:02:41
合計ジャッジ時間 82,152 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21 WA * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

class Union:
  def __init__(self, num):
    self.T = [-1] * num

  def root(self, x):
    if self.T[x] < 0: return x
    t = self.root(self.T[x])
    self.T[x] = t
    return t

  def merge(self, x, y):
    an, bn = self.root(x), self.root(y)
    if an == bn: return False
    am, bm = -self.T[an], -self.T[bn]
    if am < bm: an, bn = bn, an
    self.T[an] += self.T[bn]
    self.T[bn] = an
    return True

  def size(self, x):
    n = self.root(x)
    return -self.T[n]

  def same(self, x, y):
    return self.root(x) == self.root(y)
  
  def root_group(self):
    '''
    マージされているグループごとにリストにして返す
    各グループの先頭は根である
    '''
    R = {}
    ans: list[list[int]] = []
    for i in range(len(self.T)):
      t = self.root(i)
      if t not in R:
        R[t] = len(ans)
        ans.append([t])
      if t != i:
        ans[R[t]].append(i)
    return ans

  def print(self): #デバッグ用
    print(*self.T)
    ans = []
    for i in range(len(self.T)):
      ans.append(self.root(i))
    print(*ans)

###################################### 212行目まではACL ##########################################

import typing

def _ceil_pow2(n: int) -> int:
    x = 0
    while (1 << x) < n:
        x += 1

    return x

class LazySegTree:
    def __init__(
            self,
            op: typing.Callable[[typing.Any, typing.Any], typing.Any],
            e: typing.Any,
            mapping: typing.Callable[[typing.Any, typing.Any], typing.Any],
            composition: typing.Callable[[typing.Any, typing.Any], typing.Any],
            id_: typing.Any,
            v: typing.Union[int, typing.List[typing.Any]]) -> None:
        self._op = op
        self._e = e
        self._mapping = mapping
        self._composition = composition
        self._id = id_

        if isinstance(v, int):
            v = [e] * v

        self._n = len(v)
        self._log = _ceil_pow2(self._n)
        self._size = 1 << self._log
        self._d = [e] * (2 * self._size)
        self._lz = [self._id] * self._size
        for i in range(self._n):
            self._d[self._size + i] = v[i]
        for i in range(self._size - 1, 0, -1):
            self._update(i)

    def set(self, p: int, x: typing.Any) -> None:
        assert 0 <= p < self._n

        p += self._size
        for i in range(self._log, 0, -1):
            self._push(p >> i)
        self._d[p] = x
        for i in range(1, self._log + 1):
            self._update(p >> i)

    def get(self, p: int) -> typing.Any:
        assert 0 <= p < self._n

        p += self._size
        for i in range(self._log, 0, -1):
            self._push(p >> i)
        return self._d[p]

    def prod(self, left: int, right: int) -> typing.Any:
        assert 0 <= left <= right <= self._n

        if left == right:
            return self._e

        left += self._size
        right += self._size

        for i in range(self._log, 0, -1):
            if ((left >> i) << i) != left:
                self._push(left >> i)
            if ((right >> i) << i) != right:
                self._push((right - 1) >> i)

        sml = self._e
        smr = self._e
        while left < right:
            if left & 1:
                sml = self._op(sml, self._d[left])
                left += 1
            if right & 1:
                right -= 1
                smr = self._op(self._d[right], smr)
            left >>= 1
            right >>= 1

        return self._op(sml, smr)

    def all_prod(self) -> typing.Any:
        return self._d[1]

    def apply(self, left: int, right: typing.Optional[int] = None,
              f: typing.Optional[typing.Any] = None) -> None:
        assert f is not None

        if right is None:
            p = left
            assert 0 <= left < self._n

            p += self._size
            for i in range(self._log, 0, -1):
                self._push(p >> i)
            self._d[p] = self._mapping(f, self._d[p])
            for i in range(1, self._log + 1):
                self._update(p >> i)
        else:
            assert 0 <= left <= right <= self._n
            if left == right:
                return

            left += self._size
            right += self._size

            for i in range(self._log, 0, -1):
                if ((left >> i) << i) != left:
                    self._push(left >> i)
                if ((right >> i) << i) != right:
                    self._push((right - 1) >> i)

            l2 = left
            r2 = right
            while left < right:
                if left & 1:
                    self._all_apply(left, f)
                    left += 1
                if right & 1:
                    right -= 1
                    self._all_apply(right, f)
                left >>= 1
                right >>= 1
            left = l2
            right = r2

            for i in range(1, self._log + 1):
                if ((left >> i) << i) != left:
                    self._update(left >> i)
                if ((right >> i) << i) != right:
                    self._update((right - 1) >> i)

    def max_right(
            self, left: int, g: typing.Callable[[typing.Any], bool]) -> int:
        assert 0 <= left <= self._n
        assert g(self._e)

        if left == self._n:
            return self._n

        left += self._size
        for i in range(self._log, 0, -1):
            self._push(left >> i)

        sm = self._e
        first = True
        while first or (left & -left) != left:
            first = False
            while left % 2 == 0:
                left >>= 1
            if not g(self._op(sm, self._d[left])):
                while left < self._size:
                    self._push(left)
                    left *= 2
                    if g(self._op(sm, self._d[left])):
                        sm = self._op(sm, self._d[left])
                        left += 1
                return left - self._size
            sm = self._op(sm, self._d[left])
            left += 1

        return self._n

    def min_left(self, right: int, g: typing.Any) -> int:
        assert 0 <= right <= self._n
        assert g(self._e)

        if right == 0:
            return 0

        right += self._size
        for i in range(self._log, 0, -1):
            self._push((right - 1) >> i)

        sm = self._e
        first = True
        while first or (right & -right) != right:
            first = False
            right -= 1
            while right > 1 and right % 2:
                right >>= 1
            if not g(self._op(self._d[right], sm)):
                while right < self._size:
                    self._push(right)
                    right = 2 * right + 1
                    if g(self._op(self._d[right], sm)):
                        sm = self._op(self._d[right], sm)
                        right -= 1
                return right + 1 - self._size
            sm = self._op(self._d[right], sm)

        return 0

    def _update(self, k: int) -> None:
        self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])

    def _all_apply(self, k: int, f: typing.Any) -> None:
        self._d[k] = self._mapping(f, self._d[k])
        if k < self._size:
            self._lz[k] = self._composition(f, self._lz[k])

    def _push(self, k: int) -> None:
        self._all_apply(2 * k, self._lz[k])
        self._all_apply(2 * k + 1, self._lz[k])
        self._lz[k] = self._id

################################################################################

# from atcoder.lazysegtree import LazySegTree

class LSTFactory:
  RNG = 30
  INF = 1 << 63
  MOD = 998244353
  class LazySegTreeWithSizeWrp(LazySegTree):
    def __init__(s, op, e, mapping, composition, id_, v):
        if isinstance(v, int): v = [e] * v
        v = [(1 << LSTFactory.RNG) + x for x in v]
        super().__init__(op, e, mapping, composition, id_, v)
    def set(s, p, x): return super().set(p, (1 << LSTFactory.RNG) + x)
    def get(s, p): return super().get(p) % (1 << LSTFactory.RNG)
    def prod(s, left, right): return super().prod(left, right) % (1 << LSTFactory.RNG)
  class LazySegTreeWithSize2ApplyWrp(LazySegTreeWithSizeWrp):
    def apply(s, left, right, a, b): super().apply(left, right, (a << LSTFactory.RNG) + b)
  def makeAddMinSegTree(v): return LazySegTree(LSTFactory.opmin, LSTFactory.INF, LSTFactory.mappingadd, LSTFactory.compositionadd, 0, v)
  def makeAddMaxSegTree(v): return LazySegTree(LSTFactory.opmax, -LSTFactory.INF, LSTFactory.mappingadd, LSTFactory.compositionadd, 0, v)
  def makeAddSumSegTree(v): return LSTFactory.LazySegTreeWithSizeWrp(LSTFactory.opsum, 0, LSTFactory.mappingaddwithsize, LSTFactory.compositionadd, 0, v)
  def makeSetMinSegTree(v): return LazySegTree(LSTFactory.opmin, LSTFactory.INF, LSTFactory.mappingset, LSTFactory.compositionset, LSTFactory.INF, v)
  def makeSetMaxSegTree(v): return LazySegTree(LSTFactory.opmax, -LSTFactory.INF, LSTFactory.mappingset, LSTFactory.compositionset, LSTFactory.INF, v)
  def makeSetSumSegTree(v): return LSTFactory.LazySegTreeWithSizeWrp(LSTFactory.opsum, 0, LSTFactory.mappingsetwithsize, LSTFactory.compositionset, LSTFactory.INF, v)
  def makeAffineSumSegTree(v): return LSTFactory.LazySegTreeWithSize2ApplyWrp(LSTFactory.opaffine, 0, LSTFactory.mappingaffine, LSTFactory.compositionaffine, None, v)   
  def opmin(ele1, ele2): return min(ele1, ele2)
  def opmax(ele1, ele2): return max(ele1, ele2)
  def opsum(ele1, ele2): return ele1 + ele2
  def opaffine(ele1, ele2):
    a0, a1 = ele1 >> LSTFactory.RNG, ele1 % (1 << LSTFactory.RNG)
    b0, b1 = ele2 >> LSTFactory.RNG, ele2 % (1 << LSTFactory.RNG)
    return ((a0 + b0) << LSTFactory.RNG) + (a1 + b1) % LSTFactory.MOD
  def mappingadd(func, ele): return func + ele
  def mappingaddwithsize(func, ele):
    a0, a1 = ele >> LSTFactory.RNG, ele % (1 << LSTFactory.RNG)
    return (a0 << LSTFactory.RNG) + (func * a0 + a1)
  def mappingset(func, ele):
    if func == LSTFactory.INF: return ele
    else: return func
  def mappingsetwithsize(func, ele):
    if func == LSTFactory.INF: return ele
    a0 = ele >> LSTFactory.RNG
    return (a0 << LSTFactory.RNG) + (func * a0)
  def mappingaffine(func, ele):
    if func == None: return ele
    a0, a1 = ele >> LSTFactory.RNG, ele % (1 << LSTFactory.RNG)
    f0, f1 = func >> LSTFactory.RNG, func % (1 << LSTFactory.RNG)
    return (a0 << LSTFactory.RNG) + ((a1 * f0 % LSTFactory.MOD + f1 * a0 % LSTFactory.MOD) % LSTFactory.MOD)
  def compositionadd(func_upper, func_lower): 
    return func_upper + func_lower
  def compositionset(func_upper, func_lower):
    if func_upper == LSTFactory.INF: return func_lower
    else: return func_upper
  def compositionaffine(func_upper, func_lower):
    if func_lower == None: return func_upper
    if func_upper == None: return func_lower
    f0, f1 = func_lower >> LSTFactory.RNG, func_lower % (1 << LSTFactory.RNG)
    g0, g1 = func_upper >> LSTFactory.RNG, func_upper % (1 << LSTFactory.RNG)
    return ((f0 * g0 % LSTFactory.MOD) << LSTFactory.RNG) + ((g0 * f1 + g1) % LSTFactory.MOD)

N, Q = list(map(int, input().split()))
PXY = [list(map(int, input().split())) for _ in range(Q)]

T = [-1] * N
T[0] = 0

v = [1] * Q
ls = LSTFactory.makeAddSumSegTree(v)

PXYI = [[*PXY[i]] + [i] for i in range(Q)]
PXYI.sort()

uni = Union(N)
for p, x, y, i in PXYI:
  x -= 1
  y -= 1
  if (T[x] == -1) == (T[y] == -1): continue
  if T[y] != -1: x, y = y, x
  t = max(T[x], i)
  ls.apply(t, Q, 1)
  T[y] = i

for i in range(Q):
   print(ls.get(i))
0