Submission #69497956

---

Source Code Expand

class LazySegTree:
  def __init__(self, op, e, mapping, composition, id_, v):
    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 = (self._n-1).bit_length()
    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, x):
    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):
    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, right):
    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):
    return self._d[1]

  def apply(self, left, right, f):
    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, g):
    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, g):
    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):
    self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])

  def _all_apply(self, k, f):
    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):
    self._all_apply(2 * k, self._lz[k])
    self._all_apply(2 * k + 1, self._lz[k])
    self._lz[k] = self._id


n, q = map(int, input().split())
Q = [tuple(map(int, input().split())) for _ in range(q)]
seg = LazySegTree(
  op = lambda x, y: x+y, 
  e = 0, 
  mapping = lambda x, y: x+y, 
  composition = lambda x, y: x+y, 
  id_ = 0, 
  v = [0]*n 
)

mod = 998244353
p = 1007
now = 1
for i, (l, r) in enumerate(Q):
  l -= 1
  r -= 1
  if seg.get(l)==seg.get(r):
    seg.apply(l, r+1, now)
    now = now*p%mod
    print('Yes')
  else:
    print('No')

Submission Info

Judge Result