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) .

Solution (Python):




import sys









MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)


class lazy_segtree:
    def __init__(self, op, e, mapping, composition, id, v: list):
        self.op = op; self.e = e; self.mapping = mapping; self.composition = composition; self.id = id
        self._n = len(v)
        self.log = self.__ceil_pow2(self._n)
        self.size = 1 << self.log
        self.lz = [self.id()] * self.size
        self.d = [self.e()] * (2 * 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: int):
        assert 0 <= p and 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 >> 1)
        
    def get(self, p: int):
        assert 0 <= p and 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, l: int, r: int):
        assert 0 <= l and l <= r and r <= self._n
        if l == r: return self.e()
        l += self.size; r += self.size

        for i in range(self.log, 0, -1):
            if ((l >> i) << i) != l: self.__push(l >> i)
            if ((r >> i) << i) != r: self.__push(r >> i)
            
        sml, smr = self.e(), self.e()
        while l < r:
            if l & 1: sml = self.op(sml, self.d[l]); l += 1
            if r & 1: r -= 1; smr = self.op(self.d[r], smr)
            l >>= 1; r >>= 1
        
        return self.op(sml, smr)
    
    def all_prod(self): return self.d[1]
    
    def apply(self, p: int, f: bool):
        assert 0 <= p and p < 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 >> 1)
    
    def apply(self, l: int, r: int, f: bool):
        assert 0 <= l and l <= r and r <= self._n
        if l == r: return
        l += self.size; r += self.size

        for i in range(self.log, 0, -1):
            if ((l >> i) << i) != l: self.__push(l >> i)
            if ((r >> i) << i) != r: self.__push((r - 1) >> i)
            
        l2, r2 = l, r
        while l < r:
            if l & 1: self.__all_apply(l, f); l += 1
            if r & 1: r -= 1; self.__all_apply(r, f)
            l >>= 1; r >>= 1
        l, r = l2, r2
        
        for i in range(1, self.log + 1):
            if ((l >> i) << i) != l: self.__update(l >> i)
            if ((r >> i) << i) != r: self.__update(r >> i)
    
    def max_right(self, l: int, g):
        assert 0 <= l and l <= self._n
        if l == self._n: return self._n
        l += self.size
        for i in range(self.log, 0, -1): self.__push(l >> i)
        sm = self.e()
        while True:
            while l % 2 == 0: l >>= 1
            if not g(self.op(sm, self.d[l])):
                while l < self.size:
                    self.__push(l)
                    l = 2 * l
                    if g(self.op(sm, self.d[l])):
                        sm = self.op(sm, self.d[l])
                        l += 1
                return l - self.size
            sm = self.op(sm, self.d[l])
            l += 1
            if (l & -l) != l: break
        return self._n

    def min_left(self, r: int, g):
        assert 0 <= r and r <= self._n
        if r == 0: return 0
        r += self.size
        for i in range(self.log, 0, -1): self.__push(r >> i)
        sm = self.e()
        while True:
            r -= 1
            while r > 1 and r % 2: r >>= 1
            if not g(self.op(self.d[r], sm)):
                while r < self.size:
                    self.__push(r)
                    r = 2 * r + 1
                    if g(self.op(self.d[r], sm)):
                        sm = self.op(self.d[r], sm)
                        r += 1
                return r + 1 - self.size
            sm = self.op(self.d[r], sm)
            if (r & -r) != r: break
        return 0

    
    def __update(self, k: int): self.d[k] = self.op(self.d[k * 2], self.d[k * 2 + 1])
    
    def __all_apply(self, k: int, f: bool):
        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):
        self.__all_apply(2 * k, self.lz[k])
        self.__all_apply(2 * k + 1, self.lz[k])
        self.lz[k] = self.id()

    def __ceil_pow2(self, n: int) -> int:
        x = 0
        while (1 << x) < n: x += 1
        return x

def op(l: tuple, r: tuple): return (l[0] + r[0], l[1] + r[1], l[2] + r[2] + l[1] * r[0])

def e(): return (0, 0, 0)

def mapping(l:bool, r: tuple):
    if not l: return r
    return (r[1], r[0], r[1] * r[0] - r[2])

def composition(l: bool, r: bool): return l ^ r

def id(): return False

def Main():
    n, q = read_ints()
    A = read_int_list()
    query = [(read_ints()) for _ in range(q)]
    
    a = [(1, 0, 0) if i == 0 else (0, 1, 0) for i in A]
    seg = lazy_segtree(op, e, mapping, composition, id, a)

    for t, l, r in query:
        if t == 1:
            seg.apply(~-l, r, True)
        else:
            print(seg.prod(~-l, r)[2])           

if __name__ == '__main__':
    Main()

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
 
class LazySegmentTree():
    def __init__(self, init, unitX, unitA, f, g, h):
        self.f = f 
        self.g = g 
        self.h = h 
        self.unitX = unitX
        self.unitA = unitA
        self.f = f
        if type(init) == int:
            self.n = init
            
            self.X = [unitX] * (self.n * 2)
            self.size = [1] * (self.n * 2)
        else:
            self.n = len(init)
            
            self.X = [unitX] * self.n + init + [unitX] * (self.n - len(init))
            self.size = [0] * self.n + [1] * len(init) + [0] * (self.n - len(init))
            for i in range(self.n-1, 0, -1):
                self.X[i] = self.f(self.X[i*2], self.X[i*2|1])
    
        for i in range(self.n - 1, 0, -1):
            self.size[i] = self.size[i*2] + self.size[i*2|1]
        
        self.A = [unitA] * (self.n * 2)
        
    def update(self, i, x):
        i += self.n
        self.X[i] = x
        i >>= 1
        while i:
            self.X[i] = self.f(self.X[i*2], self.X[i*2|1])
            i >>= 1
    
    def calc(self, i):
        return self.g(self.X[i], self.A[i], self.size[i])
    
    def calc_above(self, i):
        i >>= 1
        while i:
            self.X[i] = self.f(self.calc(i*2), self.calc(i*2|1))
            i >>= 1
    
    def propagate(self, i):
        self.X[i] = self.g(self.X[i], self.A[i], self.size[i])
        self.A[i*2] = self.h(self.A[i*2], self.A[i])
        self.A[i*2|1] = self.h(self.A[i*2|1], self.A[i])
        self.A[i] = self.unitA
        
    def propagate_above(self, i):
        H = i.bit_length()
        for h in range(H, 0, -1):
            self.propagate(i >> h)
    
    def propagate_all(self):
        for i in range(1, self.n):
            self.propagate(i)
    
    def getrange(self, l, r):
        l += self.n
        r += self.n
        l0, r0 = l // (l & -l), r // (r & -r) - 1
        self.propagate_above(l0)
        self.propagate_above(r0)
        
        al = self.unitX
        ar = self.unitX
        while l < r:
            if l & 1:
                al = self.f(al, self.calc(l))
                l += 1
            if r & 1:
                r -= 1
                ar = self.f(self.calc(r), ar)
            l >>= 1
            r >>= 1
        return self.f(al, ar)
    
    def getvalue(self, i):
        i += self.n
        self.propagate_above(i)
        return self.calc(i)
    
    def operate_range(self, l, r, a):
        l += self.n
        r += self.n
        l0, r0 = l // (l & -l), r // (r & -r) - 1
        self.propagate_above(l0)
        self.propagate_above(r0)
        while l < r:
            if l & 1:
                self.A[l] = self.h(self.A[l], a)
                l += 1
            if r & 1:
                r -= 1
                self.A[r] = self.h(self.A[r], a)
            l >>= 1
            r >>= 1
        
        self.calc_above(l0)
        self.calc_above(r0)
    
    
    def max_right(self, l, z):
        if l >= self.n: return self.n
        l += self.n
        s = self.unitX
        while 1:
            while l % 2 == 0:
                l >>= 1
            if not z(self.f(s, self.calc(l))):
                while l < self.n:
                    l *= 2
                    if z(self.f(s, self.calc(l))):
                        s = self.f(s, self.calc(l))
                        l += 1
                return l - self.n
            s = self.f(s, self.calc(l))
            l += 1
            if l & -l == l: break
        return self.n
    
    
    def min_left(self, r, z):
        if r <= 0: return 0
        r += self.n
        s = self.unitX
        while 1:
            r -= 1
            while r > 1 and r % 2:
                r >>= 1
            if not z(self.f(self.calc(r), s)):
                while r < self.n:
                    r = r * 2 + 1
                    if z(self.f(self.calc(r), s)):
                        s = self.f(self.calc(r), s)
                        r -= 1
                return r + 1 - self.n
            s = self.f(self.calc(r), s)
            if r & -r == r: break
        return 0
    
    def debug(self):
        X = self.X
        print("X =", [self.calc(i) for i in range(self.n, self.n * 2)])

f = lambda x, y: (x[0] + y[0] + x[2] * y[1], x[1] + y[1], x[2] + y[2])
g = lambda x, a, s: (x[1] * x[2] - x[0], x[2], x[1]) if a else x
h = lambda a, b: a ^ b
unitX = (0, 0, 0)
unitA = 0
N, Q = map(int, input().split())
A = [(0, 1, 0) if int(a) == 0 else (0, 0, 1) for a in input().split()]
st = LazySegmentTree(A, unitX, unitA, f, g, h)

for _ in range(Q):
    t, l, r = map(int, input().split())
    if t == 1:
        st.operate_range(l - 1, r, 1)
    else:
        print(st.getrange(l - 1, r)[0])

Solution (Python):



class lazy_segtree:
  
  def __init__(s, S, op, e, F, mapping, composition, id, v):
    if type(v) is int: v = [e()] * v
    s._n = len(v)
    s.log = s.ceil_pow2(s._n)
    s.size = 1 << s.log
    s.d = [e()] * (2 * s.size)
    s.lz = [id()] * s.size
    s.e = e
    s.op = op
    s.mapping = mapping
    s.composition = composition
    s.id = id
    for i in range(s._n): s.d[s.size + i] = v[i]
    for i in range(s.size - 1, 0, -1): s.update(i)
  
  
  def set(s, p, x):
    p += s.size
    for i in range(s.log, 0, -1): s.push(p >> i)
    s.d[p] = x
    for i in range(1, s.log + 1): s.update(p >> i)

  
  def get(s, p):
    p += s.size
    for i in range(s.log, 0, -1): s.push(p >> i)
    return s.d[p]

  
  def prod(s, l, r):
    if l == r: return e()
    l += s.size
    r += s.size
    for i in range(s.log, 0, -1):
      if (((l >> i) << i) != l): s.push(l >> i)
      if (((r >> i) << i) != r): s.push(r >> i)
    sml, smr = s.e(), s.e()
    while (l < r):
      if l & 1: 
        sml = s.op(sml, s.d[l])
        l += 1
      if r & 1:
        r -= 1
        smr = s.op(s.d[r], smr)
      l >>= 1
      r >>= 1
    return s.op(sml, smr)

  
  def all_prod(s): return d[1]

  
  def apply(s, p, f):
    p += s.size
    for i in range(s.log, 0, -1): s.push(p >> i)
    s.d[p] = s.mapping(f, s.d[p])
    for i in range(1, s.log + 1): s.update(p >> i)

  
  def apply(s, l, r, f):
    if l == r: return
    l += s.size
    r += s.size
    for i in range(s.log, 0, -1):
      if (((l >> i) << i) != l): s.push(l >> i)
      if (((r >> i) << i) != r): s.push((r - 1) >> i)
    l2, r2 = l, r
    while l < r:
      if l & 1: 
        sml = s.all_apply(l, f)
        l += 1
      if r & 1:
        r -= 1
        smr = s.all_apply(r, f)
      l >>= 1
      r >>= 1
    l, r = l2, r2
    for i in range(1, s.log + 1):
      if (((l >> i) << i) != l): s.update(l >> i)
      if (((r >> i) << i) != r): s.update((r - 1) >> i)
   
  
  def max_right(l, g):
    if l == s._n: return _n
    l += s.size
    for i in range(s.log, 0, -1): s.push(l >> i)
    sm = s.e()
    while True:
      while (l % 2 == 0): l >>= 1
      if not g(s.op(sm, s.d[l])):
        while l < s.size:
          s.push(l)
          l = 2 * l
          if g(s.op(sm, s.d[l])):
            sm = s.op(sm, s.d[l])
            l += 1
        return l - s.size
      sm = s.op(sm, s.d[l])
      l += 1
      if (l & -l) == l: break
    return s._n

  
  def min_left(r, g):
    if r == 0: return 0
    r += s.size
    for i in range(s.log, 0, -1): s,push((r - 1) >> i)
    sm = s.e()
    while True:
      r -= 1
      while r > 1 and (r % 2): r >>= 1
      if not g(s.op(s.d[r], sm)):
        while r < s.size:
          s.push(r)
          r = 2 * r + 1
          if g(s.op(s.d[r], sm)):
            sm = s.op(s.d[r], sm)
            r -= 1
        return r + 1 - s.size
      sm = s.op(s.d[r], sm)
      if (r & - r) == r: break
    return 0

  def update(s, k): s.d[k] = s.op(s.d[2 * k], s.d[2 * k + 1])
  def all_apply(s, k, f):
    s.d[k] = s.mapping(f, s.d[k])
    if k < s.size: s.lz[k] = s.composition(f, s.lz[k])
  def push(s, k):
    s.all_apply(2 * k, s.lz[k])
    s.all_apply(2 * k + 1, s.lz[k])
    s.lz[k] = s.id()
  def ceil_pow2(s, n):
    x = 0
    while (1 << x) < n: x += 1
    return x



def op(l, r):
  return [l[0] + r[0], l[1] + r[1], l[2] + r[2] + l[1] * r[0]]

def e():
  return [0, 0, 0]

def mapping(l, r):
  if (not l): return r
  return [r[1], r[0], r[1] * r[0] - r[2]]

def composition(l, r):
  return (l and not r) or (not l and r)

def id():
  return False

def main():
  N, Q = list(map(int, input().split()))
  A = list(map(int, input().split()))
  TLR = [list(map(int, input().split())) for _ in range(Q)]

  a = []
  for i in A:
    if i == 0:
      a.append([1, 0, 0])
    else:
      a.append([0, 1, 0])

  _ = 0

  seg = lazy_segtree(_, op, e, _, mapping, composition, id, a)
  for i in range(Q):
    t, l, r = TLR[i]
    l -= 1
    if t == 1:
      seg.apply(l, r, True)
    else:
      print(seg.prod(l, r)[2])

main()

Solution (Python):
class LazySegmentTree():
    def __init__(self,n,init,merge,merge_unit,operate,merge_operate,operate_unit):
        self.merge=merge
        self.merge_unit=merge_unit
        self.operate=operate
        self.merge_operate=merge_operate
        self.operate_unit=operate_unit

        self.n=(n-1).bit_length()
        self.num = 1<<self.n
        self.data=[merge_unit for i in range(1<<(self.n+1))]
        self.lazy=[operate_unit for i in range(1<<(self.n+1))]
        if init:
            for i in range(n):
                self.data[2**self.n+i]=init[i]
            for i in range(2**self.n-1,0,-1):
                self.data[i]=self.merge(self.data[2*i],self.data[2*i+1])

    def propagate(self,v):
        ope = self.lazy[v]
        if ope == self.operate_unit:
            return
        self.lazy[v]=self.operate_unit
        self.data[2*v]=self.operate(self.data[2*v],ope)
        self.data[2*v+1]=self.operate(self.data[2*v+1],ope)
        self.lazy[2*v]=self.merge_operate(self.lazy[2*v],ope)
        self.lazy[2*v+1]=self.merge_operate(self.lazy[2*v+1],ope)

    def propagate_above(self,i):
        m=i.bit_length()-1
        for bit in range(m,0,-1):
            v=i>>bit
            self.propagate(v)

    def remerge_above(self,i):
        while i:
            i>>=1
            self.data[i]=self.operate(self.merge(self.data[2*i],self.data[2*i+1]),self.lazy[i])

    def update(self,l,r,x):
        l+=1<<self.n
        r+=1<<self.n
        l0=l//(l&-l)
        r0=r//(r&-r)-1
        while l<r:
            if l&1:
                self.data[l]=self.operate(self.data[l],x)
                self.lazy[l]=self.merge_operate(self.lazy[l],x)
                l+=1
            if r&1:
                self.data[r-1]=self.operate(self.data[r-1],x)
                self.lazy[r-1]=self.merge_operate(self.lazy[r-1],x)
            l>>=1
            r>>=1
        self.remerge_above(l0)
        self.remerge_above(r0)

    def query(self,l,r):
        l+=1<<self.n
        r+=1<<self.n
        l0=l//(l&-l)
        r0=r//(r&-r)-1
        self.propagate_above(l0)
        self.propagate_above(r0)
        res=self.merge_unit
        L = []
        R = []
        while l<r:
            if l&1:
                L.append(l)
                l+=1
            if r&1:
                R.append(r-1)
            l>>=1
            r>>=1

        if L and R and R[-1]==L[-1]:
            R.pop()
        R=R[::-1]
        m = L+R
        for idx in m:
            res = self.merge(res,self.data[idx])
        return res

    def bisect_l(self,l,r,x):
        l += 1<<self.n
        r += 1<<self.n
        l0=l//(l&-l)
        r0=r//(r&-r)-1
        self.propagate_above(l0)
        self.propagate_above(r0)
        Lmin = -1
        Rmin = -1
        while l<r:
            if l & 1:
                if self.data[l][0] <= x and Lmin==-1:
                    Lmin = l
                l += 1
            if r & 1:
                if self.data[r-1][0] <=x:
                    Rmin = r-1
            l >>= 1
            r >>= 1

        res = -1
        if Lmin != -1:
            pos = Lmin
            while pos<self.num:
                self.propagate(pos)
                if self.data[2 * pos][0] <=x:
                    pos = 2 * pos
                else:
                    pos = 2 * pos +1
            res =  pos-self.num
        if Rmin != -1:
            pos = Rmin
            while pos<self.num:
                self.propagate(pos)
                if self.data[2 * pos][0] <=x:
                    pos = 2 * pos
                else:
                    pos = 2 * pos +1
            if res==-1:
                res = pos-self.num
            else:
                res = min(res,pos-self.num)

        return res

import sys

input = sys.stdin.readline

merge = lambda x,y:(x[0]+y[0]+x[2]*y[1],x[1]+y[1],x[2]+y[2])
merge_unit = (0,0,0)

def operate(x,y):
    if y:
        return (x[1]*x[2]-x[0],x[2],x[1])
    else:
        return x

merge_operate = lambda x,y: (x+y)%2

operate_unit = 0

N,Q = map(int,input().split())
A = list(map(int,input().split()))

for i in range(N):
    if A[i]==0:
        A[i]=(0,1,0)
    else:
        A[i]=(0,0,1)

LST = LazySegmentTree(N,A,merge,merge_unit,operate,merge_operate,operate_unit)

for i in range(Q):
    t,l,r = map(int,input().split())
    l = l-1
    if t==1:
        LST.update(l,r,1)
    else:
        print(LST.query(l,r)[0])

Solution (Python):







MOD = 998244353
mask = (1 << 32) - 1
mask20 = (1 << 20) - 1
mask40 = (1 << 40) - 1


class LazySegmentTree:

    __slots__ = ["n", "data", "lazy", "me", "oe", "fmm", "fmo", "foo"]

    def __init__(self, monoid_data, monoid_identity, operator_identity, func_monoid_monoid, func_monoid_operator, func_operator_operator):
        self.me = monoid_identity
        self.oe = operator_identity
        self.fmm = func_monoid_monoid
        self.fmo = func_monoid_operator
        self.foo = func_operator_operator

        self.n = len(monoid_data)
        self.data = monoid_data * 2
        for i in range(self.n-1, 0, -1):
            self.data[i] = self.fmm(self.data[2*i], self.data[2*i+1])
        self.lazy = [self.oe] * (self.n * 2)
        

    def replace(self, index, value):
        index += self.n

        
        for shift in range(index.bit_length()-1, 0, -1):
            i = index >> shift
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe

        
        self.data[index] = value
        self.lazy[index] = self.oe

        
        i = index
        while i > 1:
            i //= 2
            self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
            self.lazy[i] = self.oe


    def effect(self, l, r, operator):
        l += self.n
        r += self.n
        
        
        indices = []
        l0 = (l // (l & -l))     // 2
        r0 = (r // (r & -r) - 1) // 2
        while r0 > l0:
            indices.append(r0)
            r0 //= 2
        while l0 > r0:
            indices.append(l0)
            l0 //= 2
        while l0 and l0 != r0:
            indices.append(r0)
            r0 //= 2
            if l0 == r0:
                break
            indices.append(l0)
            l0 //= 2
        while r0:
            indices.append(r0)
            r0 //= 2

        
        for i in reversed(indices):
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe

        
        while l < r:
            if l % 2:
                self.lazy[l] = self.foo(self.lazy[l], operator)
                l += 1
            if r % 2:
                r -= 1
                self.lazy[r] = self.foo(self.lazy[r], operator)
            l //= 2
            r //= 2

        
        for i in indices:
            self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
            self.lazy[i] = self.oe
            
        
    def folded(self, l, r):
        l += self.n
        r += self.n

        
        indices = []
        l0 = (l // (l & -l))     // 2
        r0 = (r // (r & -r) - 1) // 2
        while r0 > l0:
            indices.append(r0)
            r0 //= 2
        while l0 > r0:
            indices.append(l0)
            l0 //= 2
        while l0 and l0 != r0:
            indices.append(r0)
            r0 //= 2
            if l0 == r0:
                break
            indices.append(l0)
            l0 //= 2
        while r0:
            indices.append(r0)
            r0 //= 2
        
        
        for i in reversed(indices):
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe

        
        left_folded = self.me
        right_folded = self.me
        while l < r:
            if l % 2:
                left_folded = self.fmm(left_folded, self.fmo(self.data[l], self.lazy[l]))
                l += 1
            if r % 2:
                r -= 1
                right_folded = self.fmm(self.fmo(self.data[r], self.lazy[r]), right_folded)
            l //= 2
            r //= 2
        return self.fmm(left_folded, right_folded)





def main():
    import sys
    input = sys.stdin.buffer.readline

    def fmm(m1, m2):
        m = m1 + m2
        return (((m >> 32) % MOD) << 32) + (m & mask)
    
    def fmo(m1, o1):
        val = m1 >> 32
        cnt = m1 & mask
        b = o1 >> 32
        c = o1 & mask
        return (((b * val + c * cnt) % MOD) << 32) + cnt

    def foo(o1, o2):
        b1 = o1 >> 32
        c1 = o1 & mask
        b2 = o2 >> 32
        c2 = o2 & mask
        b = b1 * b2 % MOD
        c = (c1 * b2 + c2) % MOD
        return (b << 32) + c

    N, Q = map(int, input().split())
    monoid_data = [(A << 32) + 1 for A in map(int, input().split())]
    lst = LazySegmentTree(monoid_data, 1, 1 << 32, fmm, fmo, foo)
    for _ in range(Q):
        q, *k = map(int, input().split())
        if q == 0:
            o = (k[2] << 32) + k[3]
            lst.effect(k[0], k[1], o)
        else:
            print(lst.folded(k[0], k[1]) >> 32)

def test():
    import random

    def madd(a, b):
        return (a + b) % MOD

    def mmul(a, b):
        return a * b % MOD

    lst = LazySegmentTree([0] * 10, 0, 1, madd, mmul, mmul)
    ls = [0] * 10

    for _ in range(10000000):
        if random.randint(0, 1): 
            l = random.randint(0, 9)
            r = random.randint(l+1, 10)
            e = random.randint(1, 782)
            lst.effect(l, r, e)
            for i in range(l, r):
                ls[i] *= e
                ls[i] %= MOD
        else:
            l = random.randint(0, 9)
            r = random.randint(l+1, 10)
            if lst.folded(l, r) != sum(ls[l:r]):
                print(ls)
                print(l, r)
                print(lst.folded(l, r))

def atc():
    
    

    import sys
    input = sys.stdin.buffer.readline

    N, Q = map(int, input().split())
    monoid_data = [1099511627776 if A == b'1' else 1152921504606846976 for A in input().split()]

    def fmm(m1, m2):
        return m1 + m2 + ((m1 >> 40) & mask20) * (m2 >> 60)

    def fmo(m1, o1):
        if o1:
            cnt = m1 & mask40
            c1 = (m1 >> 40) & mask20 
            c0 = m1 >> 60
            return (c1 << 60) + (c0 << 40) + ((c0 * c1) - cnt)
        else:
            return m1 

    def foo(o1, o2):
        return o1 ^ o2

    lst = LazySegmentTree(monoid_data, 0, 0, fmm, fmo, foo)

    for _ in range(Q):
        T, L, R = map(int, input().split())
        if T == 1:
            lst.effect(L-1, R, 1)
        else:
            print(lst.folded(L-1, R) & mask40)

def atc2():
    
    

    import sys
    input = sys.stdin.buffer.readline

    N, Q = map(int, input().split())
    monoid_data = [(0, 1, 0) if A == b'1' else (1, 0, 0) for A in input().split()]

    def fmm(m1, m2):
        return (m1[0] + m2[0], m1[1] + m2[1], m1[2] + m2[2] + m1[1] * m2[0])

    def fmo(m1, o1):
        if o1:
            return (m1[1], m1[0], m1[0] * m1[1] - m1[2])
        else:
            return m1 

    def foo(o1, o2):
        return o1 ^ o2

    lst = LazySegmentTree(monoid_data, (0, 0, 0), 0, fmm, fmo, foo)

    for _ in range(Q):
        T, L, R = map(int, input().split())
        if T == 1:
            lst.effect(L-1, R, 1)
        else:
            print(lst.folded(L-1, R)[2])

if __name__ == "__main__":
    atc2()