Problem:


Score : 100 points

Problem Statement

You are given a binary array A=(A_1,A_2,\cdots,A_N) of length N. 

Process Q queries of the following types. The i-th query is represented by three integers T_i,L_i,R_i.

T_i=1: Replace the value of A_j with 1-A_j for each L_i \leq j \leq R_i.

T_i=2: Calculate the inversion(*) of the array A_{L_i},A_{L_i+1},\cdots,A_{R_i}．

Note：The inversion of the array x_1,x_2,\cdots,x_k is the number of the pair of integers i,j with 1 \leq i < j \leq k, x_i > x_j.

Constraints

1 \leq N \leq 2 \times 10^5

0 \leq A_i \leq 1

1 \leq Q \leq 2 \times 10^5

1 \leq T_i \leq 2

1 \leq L_i \leq R_i \leq N

All values in Input are integer.

Input

Input is given from Standard Input in the following format:

N Q
A_1 A_2 \cdots A_N
T_1 L_1 R_1
T_2 L_2 R_2
\vdots
T_Q L_Q R_Q

Output

For each query with T_i=2, print the answer.

Sample Input 1

5 5
0 1 0 0 1
2 1 5
1 3 4
2 2 5
1 1 3
2 1 2

Sample Output 1

2
0
1

First query: Print 2, which is the inversion of (A_1,A_2,A_3,A_4,A_5)=(0,1,0,0,1).

Second query: Replace the value of A_3 and A_4 with 1 and 1, respectively.

Third query: Print 0, which is the inversion of (A_2,A_3,A_4,A_5)=(1,1,1,1).

Fourth query: Replace the value of A_1, A_2 and A_4 with 1, 0 and 0, respectively.

Fifth query: Print 1, which is the inversion of (A_1,A_2)=(1,0).



Sample input:
5 5
0 1 0 0 1
2 1 5
1 3 4
2 2 5
1 1 3
2 1 2


Sample output:
2
0
1

Submission status: Time Limit Exceeded

Solution code:
import sys
S=sys.stdin.readlines()
from copy import *
def m(X,Y):
  return [X[0]+Y[0],X[1]+Y[1],X[2]+Y[2]+X[1]*Y[0]]

def r(X,F):
  if F:
    return [X[1],X[0],X[0]*X[1]-X[2]]
  else:
    return X[:]

def init(N,node,func,first,unit,unitr,refl,prop):
  while len(node):
    del node[-1]
  node.append([])
  node.append([])
  n=1
  while n<N:
    n<<=1
  for j in range((n<<1)-1):
    node[0].append(deepcopy(unit))
    node[1].append(deepcopy(unitr))
  for j in range(N):
    node[0][n-1+j]=deepcopy(first[j])
  for j in range(n-2,-1,-1):
    node[0][j]=func(node[0][(j<<1)+1],node[0][(j<<1)+2])
  node[0].append(func)
  node[0].append(deepcopy(unit))
  node[0].append(n)
  node[1].append(refl)
  node[1].append(deepcopy(unitr))
  node[1].append(prop)

def refl(node,k):
  node[0][k]=node[1][-3](node[0][k],node[1][k])
  if k<node[0][-1]-1:
    node[1][(k<<1)+1]=node[1][-1](node[1][(k<<1)+1],node[1][k])
    node[1][(k<<1)+2]=node[1][-1](node[1][(k<<1)+2],node[1][k])
  node[1][k]=deepcopy(node[1][-2])

def upd(node,x,a,b):
  q=[[0,0,node[0][-1],0]]
  k=0
  while len(q):
    k=q[-1][:]
    del q[-1]
    if k[3]:
      node[0][k[0]]=node[0][-3](node[0][(k[0]<<1)+1],node[0][(k[0]<<1)+2])
      continue
    refl(node,k[0])
    if b<=k[1] or k[2]<=a:
      continue
    if a<=k[1] and k[2]<=b:
      node[1][k[0]]=deepcopy(x)
      refl(node,k[0])
    else:
      q.append([k[0],k[1],k[2],1])
      q.append([(k[0]<<1)+1,k[1],(k[1]+k[2])>>1,0])
      q.append([(k[0]<<1)+2,(k[1]+k[2])>>1,k[2],0])

def query(node,a,b):
  r=deepcopy(node[0][-2])
  q=[[0,0,node[0][-1]]]
  k=0
  while len(q):
    k=q[-1][:]
    del q[-1]
    if b<=k[1] or k[2]<=a:
      continue
    refl(node,k[0])
    if a<=k[1] and k[2]<=b:
      r=node[0][-3](node[0][k[0]],r)
    else:
      q.append([(k[0]<<1)+1,k[1],(k[1]+k[2])>>1])
      q.append([(k[0]<<1)+2,(k[1]+k[2])>>1,k[2]])
  return r

N,Q=map(int,S[0].split())
A=list(map(int,S[1].split()))
X=[]
Y=[[0,0,0] for i in range(N)]
for i in range(N):
  Y[i][A[i]]=1
init(N,X,lambda x,y:m(x,y),Y,[0,0,0],0,lambda x,y:r(x,y),lambda x,y:x^y)
a,b,c=0,0,0
for i in range(Q):
  a,b,c=map(int,S[i+2].split())
  if a==1:
    upd(X,1,b-1,c)
  else:
    print(query(X,b-1,c)[2])

Submission status: Time Limit Exceeded

Solution code:
import types

_atcoder_code = """
# Python port of AtCoder Library.

__version__ = '0.0.1'
"""

atcoder = types.ModuleType('atcoder')
exec(_atcoder_code, atcoder.__dict__)

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

    return x


def _bsf(n: int) -> int:
    x = 0
    while n % 2 == 0:
        x += 1
        n //= 2

    return x
"""

atcoder._bit = types.ModuleType('atcoder._bit')
exec(_atcoder__bit_code, atcoder._bit.__dict__)


_atcoder_lazysegtree_code = """
import typing

# import atcoder._bit


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 = atcoder._bit._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 >> 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):
        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
"""

atcoder.lazysegtree = types.ModuleType('atcoder.lazysegtree')
exec(_atcoder_lazysegtree_code, atcoder.lazysegtree.__dict__)
atcoder.lazysegtree.__dict__['atcoder'] = atcoder
atcoder.lazysegtree.__dict__['atcoder._bit'] = atcoder._bit
LazySegTree = atcoder.lazysegtree.LazySegTree

# https://atcoder.jp/contests/practice2/tasks/practice2_l

import sys

# from atcoder.lazysegtree import LazySegTree


def main() -> None:
    n, q = map(int, sys.stdin.readline().split())
    a = []
    for x in map(int, sys.stdin.readline().split()):
        if x == 0:
            a.append((1, 0, 0))
        else:
            a.append((0, 1, 0))

    def op(x: (int, int, int), y: (int, int, int)) -> (int, int, int):
        return x[0] + y[0], x[1] + y[1], x[2] + y[2] + x[1] * y[0]

    e = (0, 0, 0)

    def mapping(x: bool, y: (int, int, int)) -> (int, int, int):
        if not x:
            return y
        return y[1], y[0], y[0] * y[1] - y[2]

    def composition(x: bool, y: bool) -> bool:
        return (x and not y) or (not x and y)

    id_ = False

    lazy_segtree = LazySegTree(op, e, mapping, composition, id_, a)
    for _ in range(q):
        t, left, right = map(int, sys.stdin.readline().split())
        left -= 1
        if t == 1:
            lazy_segtree.apply(left, right, True)
        else:
            print(lazy_segtree.prod(left, right)[2])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from copy import *
def m(X,Y):
  return [X[0]+Y[0],X[1]+Y[1],X[2]+Y[2]+X[1]*Y[0]]

def r(X,F):
  if F:
    return [X[1],X[0],X[0]*X[1]-X[2]]
  else:
    return X[:]

def init(N,node,func,first,unit,unitr,refl,prop):
  while len(node):
    del node[-1]
  node.append([])
  node.append([])
  n=1
  while n<N:
    n<<=1
  for j in range((n<<1)-1):
    node[0].append(deepcopy(first))
    node[1].append(deepcopy(unitr))
  for j in range(N,n):
    node[0][n-1+j]=deepcopy(unit)
  for j in range(n-2,-1,-1):
    node[0][j]=func(node[0][(j<<1)+1],node[0][(j<<1)+2])
  node[0].append(func)
  node[0].append(deepcopy(unit))
  node[0].append(n)
  node[1].append(refl)
  node[1].append(deepcopy(unitr))
  node[1].append(prop)

def refl(node,k):
  node[0][k]=node[1][-3](node[0][k],node[1][k])
  if k<node[0][-1]-1:
    node[1][(k<<1)+1]=node[1][-1](node[1][(k<<1)+1],node[1][k])
    node[1][(k<<1)+2]=node[1][-1](node[1][(k<<1)+2],node[1][k])
  node[1][k]=deepcopy(node[1][-2])

def upd(node,x,a,b):
  q=[[0,0,node[0][-1],0]]
  k=0
  while len(q):
    k=q[-1][:]
    del q[-1]
    if k[3]:
      node[0][k[0]]=node[0][-3](node[0][(k[0]<<1)+1],node[0][(k[0]<<1)+2])
      continue
    refl(node,k[0])
    if b<=k[1] or k[2]<=a:
      continue
    if a<=k[1] and k[2]<=b:
      node[1][k[0]]=deepcopy(x)
      refl(node,k[0])
    else:
      q.append([k[0],k[1],k[2],1])
      q.append([(k[0]<<1)+1,k[1],(k[1]+k[2])>>1,0])
      q.append([(k[0]<<1)+2,(k[1]+k[2])>>1,k[2],0])

def query(node,a,b):
  r=deepcopy(node[0][-2])
  q=[[0,0,node[0][-1]]]
  k=0
  while len(q):
    k=q[-1][:]
    del q[-1]
    if b<=k[1] or k[2]<=a:
      continue
    refl(node,k[0])
    if a<=k[1] and k[2]<=b:
      r=node[0][-3](node[0][k[0]],r)
    else:
      q.append([(k[0]<<1)+1,k[1],(k[1]+k[2])>>1])
      q.append([(k[0]<<1)+2,(k[1]+k[2])>>1,k[2]])
  return r

N,Q=map(int,input().split())
A=list(map(int,input().split()))
X=[]
init(N,X,lambda x,y:m(x,y),[1,0,0],[0,0,0],0,lambda x,y:r(x,y),lambda x,y:x^y)
for i in range(N):
  if A[i]:
    upd(X,1,i,i+1)
a,b,c=0,0,0
for i in range(Q):
  a,b,c=map(int,input().split())
  if a==1:
    upd(X,1,b-1,c)
  else:
    print(query(X,b-1,c)[2])

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]

class LazySegTree():
	def __init__(self, a, func, unit, oper, comp, idem):
		#the number of nodes is 2n-1
		self.hght = len(a).bit_length()
		self.n = 1 << self.hght
		self.size = len(a)
		self.func = func #(ele, ele) -> ele
		self.unit = unit #ele
		self.oper = oper #(ele, op) -> ele
		self.comp = comp #(op, op) -> op
		self.idem = idem #op
		self.node = [unit] * (2 * self.n)
		#immediate evaluation enables size reduction
		self.lazy = [idem] * self.n
		for i in range(self.size + self.n - 1, 0, -1):
			if i >= self.n:
				self.node[i] = a[i - self.n]
			else:
				self.update(i)

	def update(self, k):
		self.node[k] = self.func(self.node[2 * k], self.node[2 * k + 1])
		return

	def apply_node_lazy(self, k, op):
		self.node[k] = self.oper(op, self.node[k])
		if k < self.n:
			self.lazy[k] = self.comp(op, self.lazy[k])
		return

	def push(self, k):
		self.apply_node_lazy(2 * k, self.lazy[k])
		self.apply_node_lazy(2 * k + 1, self.lazy[k])
		self.lazy[k] = self.idem
		return

	def set(self, k, x):
		k += self.n
		for i in range(self.hght, 0, -1):
			self.push(k >> i)

		self.node[k] = x
		
		while k > 1:
			k >>= 1
			self.update(k)
		return

	def get(self, k):
		k += self.n
		for i in range(self.hght, 0, -1):
			self.push(k >> i)
		
		return self.node[k]

	#[l, r)
	def prod(self, l, r):
		if l == r:
			return self.unit
		l += self.n
		r += self.n
		
		for i in range(self.hght, 0, -1):
			if ((l >> i) << i) != l:
				self.push(l >> i)
			if ((r >> i) << r) != r:
				self.push(r >> i)

		s_l, s_r = self.unit, self.unit
		while l < r:
			if l & 1:
				s_l = self.func(s_l, self.node[l])
				l += 1
			if r & 1:
				r -= 1
				s_r = self.func(self.node[r], s_r)
			l >>= 1
			r >>= 1
		return self.func(s_l, s_r)

	def all_prod(self):
		return self.node[1]

	def point_apply(self, k, op):
		k += self.n
		for i in range(self.hght, 0, -1):
			self.push(k >> i)
		
		self.node[k] = self.oper(op, self.node[k])
		
		while k > 1:
			k >>= 1
			self.update(k)
		return

	#operate to [l, r)
	def apply(self, l, r, op):
		if l == r:
			return
		l += self.n
		r += self.n
		
		for i in range(self.hght, 0, -1):
			if ((l >> i) << i != l):
				self.push(l >> i)
			if ((r >> i) << i != r):
				self.push((r - 1) >> i)

		l_pres, r_pres = l, r
		while l < r:
			if l & 1:
				self.apply_node_lazy(l, op)
				l += 1
			if r & 1:
				r -= 1
				self.apply_node_lazy(r, op)
			l >>= 1
			r >>= 1
		l, r = l_pres, r_pres

		for i in range(1, self.hght+1):
			if ((l >> i) << i != l):
				self.update(l >> i)
			if ((r >> i) << i != r):
				self.update((r - 1) >> i)
		return

	#maximum of r (within [l, n)) which satisfies val(prod(l, r))
	def max_right(self, l, val):
		if l == self.size:
			return self.size
		l += self.n
		for i in range(self.hght, 0, -1):
			self.push(l >> i)

		s = self.unit
		while True:
			while l % 2 == 0:
				l >>= 1
			if not val(self.func(s, self.node[l])):
				while l < self.n:
					self.push(l) #before descending
					l <<= 1
					if val(self.func(s, self.node[l])):
						s = self.func(s, self.node[l])
						l += 1
				return l - self.n
			s = self.func(s, self.node[l])
			l += 1
			if (l & -l) == l:
				return self.size

	#minimum of l (within [0, r)) which satisfies val(prod(l, r))
	def min_left(self, r, val):
		if r == 0:
			return 0
		r += self.n
		for i in range(self.hght, 0, -1):
			self.push((r - 1) >> i)

		s = self.unit
		while True:
			r -= 1
			while r > 1 and r % 2:
				r >>= 1
			if not val(self.func(self.node[r], s)):
				while r < self.n:
					self.push(r) #before descending
					r = (r << 1) + 1
					if val(self.func(self.node[r], s)):
						s = self.func(self.node[r], s)
						r -= 1
				return r + 1 - self.n
			s = self.func(self.node[r], s)
			if (r & -r) == r:
				return 0

def func(x, y):
	return (x[0] + y[0], x[1] + y[1], x[2] + y[2] + x[1] * y[0])

unit = (0, 0, 0)

def oper(f, x):
	if not f:
		return x
	else:
		return (
			x[1],
			x[0],
			x[0] * x[1] - x[2]
			)

def comp(f, g):
	return f ^ g

idem = False

n, q = map(int, input().split())
a = list(map(int, input().split()))
a = [(0, 1, 0) if x else (1, 0, 0) for x in a]
st = LazySegTree(a, func, unit, oper, comp, idem)
ans = []
for _ in range(q):
	t, l, r = map(int, input().split())
	if t == 1:
		st.apply(l-1, r, True)
	else:
		ans.append(st.prod(l-1, r)[2])
print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



### 遅延評価セグメント木
class LazySegmentTree:
    def __init__(self, n, a=None):
        """初期化
        num : n以上の最小の2のべき乗
        """
        num = 1
        v = 0
        while num<=n:
            num *= 2
            v += 1
        self.q = [None]*(2*v+10)
        self.num = num
        self.seg = [ninf] * (2*self.num-1)
        self.lazy = [f0] * (2*self.num-1)
        self.ls = [0]*(2*self.num-1)
        self.rs = [0]*(2*self.num-1)
        self.ls[0] = 0
        self.rs[0] = self.num
        for i in range(self.num-1):
            self.ls[2*i+1] = self.ls[i]
            self.rs[2*i+1] = (self.ls[i] + self.rs[i])//2
            self.ls[2*i+2] = (self.ls[i] + self.rs[i])//2
            self.rs[2*i+2] = self.rs[i]
        if a is not None:
            # O(n)で初期化
            assert len(a)==n
            for i in range(n):
                self.seg[num-1+i] = a[i]
            for k in range(num-2, -1, -1):
                self.seg[k] = op(self.seg[2*k+1], self.seg[2*k+2])
    def eval(self, k):
        if self.lazy[k]==f0:
            return 
        if k<self.num-1:
            self.lazy[k*2+1] = composition(self.lazy[k], self.lazy[k*2+1])
            self.lazy[k*2+2] = composition(self.lazy[k], self.lazy[k*2+2])
        self.seg[k] = mapping(self.lazy[k], self.seg[k])
        self.lazy[k] = f0
    def eval_all(self):
        for i in range(2*self.num-1):
            self.eval(i)
    def update(self,a,b,x=None,f=None):
        """A[a]...A[b-1]をxに更新する
        """
        if f is None:
            # 更新クエリ
            f = lambda y: x
        k = 0
        self.q[0] = k # k>=0なら行きがけ順
        ind = 1
        # 重なる区間を深さ優先探索
        while ind:
            ind -= 1
            k = self.q[ind]
            l,r = self.ls[k], self.rs[k]
            if k>=0:
                self.eval(k)
                if r<=a or b<=l:
                    continue
                elif a<=l and r<=b:
                    self.lazy[k] = composition(f, self.lazy[k])
                    self.eval(k)
                else:
                    self.q[ind] = ~k
                    self.q[ind+1] = 2*k+1
                    self.q[ind+2] = 2*k+2
                    ind += 3
#                     q.append(~k)
#                     q.append(2*k+1)
#                     q.append(2*k+2)
            else:
                k = ~k
                self.seg[k] = op(self.seg[2*k+1], self.seg[2*k+2])
    def query(self,a,b):
        k = 0
        l = 0
        r = self.num
        self.q[0] = k
        ind = 1
        ans = ninf
        # 重なる区間を深さ優先探索
        while ind:
            ind -= 1
            k = self.q[ind]
            l,r = self.ls[k], self.rs[k]
            self.eval(k)
            if r<=a or b<=l:
                continue
            elif a<=l and r<=b:
                ans = op(ans, self.seg[k])
            else:
                self.q[ind] = 2*k+2
                self.q[ind+1] = 2*k+1
                ind += 2
#                 q.append(2*k+2)
#                 q.append(2*k+1)
#             print(q, ans, l,r,a,b, self.seg[k])
        return ans
n,q = list(map(int, input().split()))
a = list(map(int, input().split()))
# ninf = -10**9
# op = max
# mapping = lambda f,x: f(x)
# composition = lambda f1, f2: f1 if f1 is not None else f2
b1 = 32
b2 = 32
ninf = 0 # (転倒数, #0, #1)
def op(x,y):
    x0 = x>>(b1+b2)
    xx = x%(1<<(b1+b2))
    x1 = xx>>b1
    x2 = xx%(1<<b2)
    y0 = y>>(b1+b2)
    xx = y%(1<<(b1+b2))
    y1 = xx>>b1
    y2 = xx%(1<<b2)
    return ((x0+y0+x2*y1)<<(b1+b2)) + ((x1+y1)<<b1) + x2+y2
def mapping(f,x):
    if not f:
        return x
    x0 = x>>(b1+b2)
    xx = x%(1<<(b1+b2))
    x1 = xx>>b1
    x2 = xx%(1<<b2)
    return (((x1+x2)*(x1+x2-1)//2 - (x1*(x1-1)//2) - (x2*(x2-1)//2) - x0)<<(b1+b2)) + (x2<<b1) + x1

# op = lambda x,y: (x[0]+y[0]+x[2]*y[1], x[1]+y[1], x[2]+y[2])
# mapping = lambda f,x: ((x[1]+x[2])*(x[1]+x[2]-1)//2 - (x[1]*(x[1]-1)//2) - (x[2]*(x[2]-1)//2) - x[0], x[2], x[1]) if f else x
composition = lambda f1, f2: f1^f2
f0 = False
sg = LazySegmentTree(n, [((1<<b1) if item==0 else 1) for item in a])
ans = []
for _ in range(q):
    t = tuple(map(int, input().split()))
    if t[0]==1:
        _, l,r = t
        sg.update(l-1,r,f=True)
    else:
        _,l,r = t
        ans.append(sg.query(l-1,r)>>(b1+b2))
#         break
write("\n".join(map(str, ans)))