class NestedSplayArray(object): def __init__(self, n, cell_size = None): self.n = n if cell_size == None: cell_size = 32 while cell_size * 32 < n: cell_size *= 32 self.cell_size = cell_size self.length = n // self.cell_size + (1 if n % self.cell_size else 0) if self.cell_size <= 1024: self.cells = [SplayArray(self.cell_size) for i in range(self.length)] else: self.cells = [NestedSplayArray(self.cell_size) for i in range(self.length)] self.all_off = True self.all_on = False self.total = 0 def _clear_lazy_eval(self): if self.all_on: for cell in self.cells: cell.turn_on(0, self.cell_size - 1) self.all_on = False if self.all_off: for cell in self.cells: cell.turn_off(0, self.cell_size - 1) self.all_off = False def _get_range(self, L, R): idxL, posL = divmod(L, self.cell_size) idxR, posR = divmod(R, self.cell_size) return idxL, posL, idxR, posR def turn_on(self, L, R): if L == 0 and R == self.n - 1: self.all_on = True self.all_off = False self.total = self.n return self._clear_lazy_eval() self.total = -1 idxL, posL, idxR, posR = self._get_range(L, R) if idxL == idxR: self.cells[idxL].turn_on(posL, posR) else: self.cells[idxL].turn_on(posL, self.cell_size - 1) self.cells[idxR].turn_on(0, posR) for idx in range(idxL + 1, idxR): self.cells[idx].turn_on(0, self.cell_size - 1) def turn_off(self, L, R): '''[l, r] の範囲を off にする。 ''' if L == 0 and R == self.n - 1: self.all_off = True self.all_on = False self.total = 0 return self._clear_lazy_eval() self.total = -1 idxL, posL, idxR, posR = self._get_range(L, R) if idxL == idxR: self.cells[idxL].turn_off(posL, posR) else: self.cells[idxL].turn_off(posL, self.cell_size - 1) self.cells[idxR].turn_off(0, posR) for idx in range(idxL + 1, idxR): self.cells[idx].turn_off(0, self.cell_size - 1) def count(self, L, R): '''[l, r] の範囲の on の個数を返す。 ''' is_all_range = (L == 0 and R == self.n - 1) if self.all_on: return R - L + 1 if self.all_off: return 0 if is_all_range and self.total != -1: return self.total idxL, posL, idxR, posR = self._get_range(L, R) if idxL == idxR: return self.cells[idxL].count(posL, posR) counts = self.cells[idxL].count(posL, self.cell_size - 1) counts += self.cells[idxR].count(0, posR) for idx in range(idxL + 1, idxR): counts += self.cells[idx].count(0, self.cell_size - 1) if is_all_range: self.total = counts return counts class SplayArray(object): def __init__(self, n, cell_size = 32): self.n = n self.cell_size = cell_size self.full = (1 << self.cell_size) - 1 self.length = n // cell_size + (1 if n % cell_size else 0) self.cells = [0] * self.length self.all_off = True self.all_on = False self.total = 0 def _clear_lazy_eval(self): if self.all_on: self.cells = [self.full] * self.length self.all_on = False if self.all_off: self.cells = [0] * self.length self.all_off = False def _get_range(self, L, R): idxL, posL = divmod(L, self.cell_size) idxR, posR = divmod(R, self.cell_size) return idxL, posL, idxR, posR def turn_on(self, L, R): '''[l, r] の範囲を on にする。 ''' if L == 0 and R == self.n - 1: self.all_on = True self.all_off = False self.total = self.n return self._clear_lazy_eval() self.total = -1 idxL, posL, idxR, posR = self._get_range(L, R) if idxL == idxR: self.cells[idxL] |= (1 << (posR + 1)) - (1 << posL) else: self.cells[idxL] |= (1 << self.cell_size) - (1 << posL) self.cells[idxR] |= (1 << (posR + 1)) - 1 self.cells[idxL + 1 : idxR] = [self.full] * (idxR - idxL - 1) def turn_off(self, L, R): '''[l, r] の範囲を off にする。 ''' if L == 0 and R == self.n - 1: self.all_off = True self.all_on = False self.total = 0 return self._clear_lazy_eval() self.total = -1 idxL, posL, idxR, posR = self._get_range(L, R) if idxL == idxR: self.cells[idxL] &= ~((1 << (posR + 1)) - (1 << posL)) else: self.cells[idxL] &= ~((1 << self.cell_size) - (1 << posL)) self.cells[idxR] &= ~((1 << (posR + 1)) - 1) self.cells[idxL + 1 : idxR] = [0] * (idxR - idxL - 1) def count(self, L, R): '''[l, r] の範囲の on の個数を返す。 ''' is_all_range = (L == 0 and R == self.n - 1) if self.all_on: return R - L + 1 if self.all_off: return 0 if is_all_range and self.total != -1: return self.total idxL, posL, idxR, posR = self._get_range(L, R) if idxL == idxR: return bin(self.cells[idxL] & ((1 << (posR + 1)) - (1 << posL))).count('1') counts = bin(self.cells[idxL] & ((1 << self.cell_size) - (1 << posL))).count('1') counts += bin(self.cells[idxR] & ((1 << (posR + 1)) - 1)).count('1') for idx in range(idxL + 1, idxR): counts += bin(self.cells[idx]).count('1') if is_all_range: self.total = counts return counts if __name__ == '__main__': N = int(input()) Q = int(input()) teamA = NestedSplayArray(N) teamB = NestedSplayArray(N) scoreA = 0 scoreB = 0 for q in range(Q): x, l, r = map(int, input().split()) if x == 0: bonusA = teamA.count(l, r) bonusB = teamB.count(l, r) if bonusA > bonusB: scoreA += bonusA elif bonusA < bonusB: scoreB += bonusB elif x == 1: teamA.turn_on(l, r) teamB.turn_off(l, r) elif x == 2: teamA.turn_off(l, r) teamB.turn_on(l, r) scoreA += teamA.count(0, N-1) scoreB += teamB.count(0, N-1) print('{} {}'.format(scoreA, scoreB))