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





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

        l0 = l
        r0 = r - 1
        while l0 % 2 == 0:
            l0 //= 2
        while r0 % 2 == 1:
            r0 //= 2
        l0 //= 2
        r0 //= 2
        
        
        indices = []
        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

        l0 = l
        r0 = r - 1
        while l0 % 2 == 0:
            l0 //= 2
        while r0 % 2 == 1:
            r0 //= 2
        l0 //= 2
        r0 //= 2

        
        indices = []
        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 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)
    ans = []
    for _ in range(Q):
        T, L, R = map(int, input().split())
        if T == 1:
            lst.effect(L-1, R, 1)
        else:
            ans.append(lst.folded(L-1, R)[2])
    print('\n'.join(map(str, ans)))

if __name__ == "__main__":
    atc2()

Solution (Python):







class LazySegmentTree:

    __slots__ = ["n", "original_size", "log", "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.original_size = len(monoid_data)
        self.log = (self.original_size - 1).bit_length()
        self.n = 1 << self.log
        self.data = [self.me] * self.n + monoid_data + [self.me] * (self.n - self.original_size)
        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(self.log, 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
        l0 = l
        r0 = r - 1
        while l0 % 2 == 0:
            l0 //= 2
        while r0 % 2 == 1:
            r0 //= 2
        
        
        l0 //= 2
        r0 //= 2
        indices = []
        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
            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
        l0 = l
        r0 = r - 1
        while l0 % 2 == 0:
            l0 //= 2
        while r0 % 2 == 1:
            r0 //= 2
        
        
        l0 //= 2
        r0 //= 2
        indices = []
        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
            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 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)
    ans = []
    for _ in range(Q):
        T, L, R = map(int, input().split())
        if T == 1:
            lst.effect(L-1, R, 1)
        else:
            ans.append(lst.folded(L-1, R)[2])
    print('\n'.join(map(str, ans)))

if __name__ == "__main__":
    atc2()

Solution (Python):
I = [int(_) for _ in open(0).read().split()]
N, Q = I[:2]
A = I[2:2 + N]
T = I[2 + N::3]
L = I[3 + N::3]
R = I[4 + N::3]


class LazySegmentTree():
    def __init__(self, array, f, g, h, ti, ei):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
            T x T -> T
            T is dat
        g : func
            binary operation of the monoid
            T x E -> T
            T is dat, E is laz
        h : func
            binary operation of the monoid
            E x E -> T
            E is laz
        ti : T
            identity element of T
        ei : E
            identity element of E
        """
        self.f = f
        self.g = g
        self.h = h
        self.ti = ti
        self.ei = ei
        self.height = height = len(array).bit_length()
        self.n = n = 2**height
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        self.laz = [ei] * (2 * n)
        for i in range(n - 1, 0, -1):  
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def reflect(self, k):
        dat = self.dat
        ei = self.ei
        laz = self.laz
        g = self.g
        return self.dat[k] if laz[k] is ei else g(dat[k], laz[k])

    def evaluate(self, k):
        laz = self.laz
        ei = self.ei
        reflect = self.reflect
        dat = self.dat
        h = self.h
        if laz[k] is ei:
            return
        laz[(k << 1) | 0] = h(laz[(k << 1) | 0], laz[k])
        laz[(k << 1) | 1] = h(laz[(k << 1) | 1], laz[k])
        dat[k] = reflect(k)
        laz[k] = ei

    def thrust(self, k):
        height = self.height
        evaluate = self.evaluate
        for i in range(height, 0, -1):
            evaluate(k >> i)

    def recalc(self, k):
        dat = self.dat
        reflect = self.reflect
        f = self.f
        while k:
            k >>= 1
            dat[k] = f(reflect((k << 1) | 0), reflect((k << 1) | 1))

    def update(self, a, b, x):  
        thrust = self.thrust
        n = self.n
        h = self.h
        laz = self.laz
        recalc = self.recalc
        a += n
        b += n - 1
        l = a
        r = b + 1
        thrust(a)
        thrust(b)
        while l < r:
            if l & 1:
                laz[l] = h(laz[l], x)
                l += 1
            if r & 1:
                r -= 1
                laz[r] = h(laz[r], x)
            l >>= 1
            r >>= 1
        recalc(a)
        recalc(b)

    def set_val(self, a, x):
        n = self.n
        thrust = self.thrust
        dat = self.dat
        laz = self.laz
        recalc = self.recalc
        ei = self.ei
        a += n
        thrust(a)
        dat[a] = x
        laz[a] = ei
        recalc(a)

    def query(self, a, b):  
        f = self.f
        ti = self.ti
        n = self.n
        thrust = self.thrust
        reflect = self.reflect
        a += n
        b += n - 1
        thrust(a)
        thrust(b)
        l = a
        r = b + 1
        vl = vr = ti
        while l < r:
            if l & 1:
                vl = f(vl, reflect(l))
                l += 1
            if r & 1:
                r -= 1
                vr = f(reflect(r), vr)
            l >>= 1
            r >>= 1
        return f(vl, vr)



array = [(0, 0, 0)] + [(0, 1, 0) if a else (1, 0, 0) for a in A]
f = lambda a, b: (a[0] + b[0], a[1] + b[1], a[2] + b[2] + a[1] * b[0])


def g(a, b):
    if b == -1:
        x = a[1]
        y = a[0]
        z = (x + y) * (x + y - 1) // 2 - x * (x - 1) // 2 - y * (
            y - 1) // 2 - a[2]
        return (x, y, z)
    else:
        return a


h = lambda a, b: a * b
ti = (0, 0, 0)
ei = 1



LST = LazySegmentTree(array=array, ti=ti, ei=ei, f=f, g=g, h=h)

for t, l, r in zip(T, L, R):
    r += 1
    if t == 1:
        LST.update(l, r, -1)
    else:
        print(LST.query(l, r)[2])

Solution (Python):
import os
import sys

import numpy as np


def solve(inp):
    SEGTREE_TABLES = []
    COMMON_STACK = np.zeros(10 ** 7, dtype=np.int64)

    def bit_length(n):
        ret = 0
        while n:
            n >>= 1
            ret += 1
        return ret

    def segtree_init(n):
        n2 = 1 << bit_length(n)
        table = np.zeros((n2 << 1, 4), dtype=np.int64)
        SEGTREE_TABLES.append(table)
        return len(SEGTREE_TABLES) - 1

    def segtree_build(ins, arr):
        table = SEGTREE_TABLES[ins]
        offset = table.shape[0] >> 1
        table[:, 1] = 1
        table[offset:offset + len(arr), 0] = 1 - arr
        table[offset:offset + len(arr), 1] = arr
        for i in range(offset - 1, 0, -1):
            ch = i << 1
            table[i, 0] = table[ch, 0] + table[ch + 1, 0]
            table[i, 1] = table[ch, 1] + table[ch + 1, 1]
            table[i, 2] = table[ch, 2] + table[ch + 1, 2] + table[ch, 1] * table[ch + 1, 0]

    def segtree_eval(table, offset, i):
        if table[i, 3] == 0:
            return
        if i < offset:
            ch = i << 1
            table[ch, 3] ^= 1
            table[ch + 1, 3] ^= 1
        table[i, 0], table[i, 1] = table[i, 1], table[i, 0]
        table[i, 2] = table[i, 0] * table[i, 1] - table[i, 2]
        table[i, 3] = 0

    def segtree_bottomup(table, i):
        lch = i << 1
        rch = lch + 1
        l0, l1, l2 = table[lch, 0], table[lch, 1], table[lch, 2]
        r0, r1, r2 = table[rch, 0], table[rch, 1], table[rch, 2]
        if table[lch, 3]:
            l0, l1 = l1, l0
            l2 = l0 * l1 - l2
        if table[rch, 3]:
            r0, r1 = r1, r0
            r2 = r0 * r1 - r2
        table[i, 0] = l0 + r0
        table[i, 1] = l1 + r1
        table[i, 2] = l2 + r2 + l1 * r0

    def segtree_range_swap(ins, l, r):
        """ i for [l, r),  Ai ← ~Ai """
        table = SEGTREE_TABLES[ins]
        offset = table.shape[0] >> 1
        stack = COMMON_STACK
        stack[:3] = (1, 0, offset)
        si = 3
        updated = []
        while si:
            i, a, b = stack[si - 3:si]
            segtree_eval(table, offset, i)

            if b <= l or r <= a:
                si -= 3
                continue

            if l <= a and b <= r:
                table[i, 3] ^= 1
                si -= 3
                continue

            updated.append(i)

            m = (a + b) // 2
            stack[si - 3:si] = (i << 1, a, m)
            stack[si:si + 3] = ((i << 1) + 1, m, b)
            si += 3

        while updated:
            i = updated.pop()
            segtree_bottomup(table, i)

    def segtree_query(ins, l, r):
        """ sum [l, r) """
        table = SEGTREE_TABLES[ins]
        offset = table.shape[0] >> 1
        stack = COMMON_STACK
        stack[:3] = (1, 0, offset)
        si = 3
        pick = []
        updated = []

        while si:
            i, a, b = stack[si - 3:si]

            segtree_eval(table, offset, i)

            if b <= l or r <= a:
                si -= 3
                continue

            if l <= a and b <= r:
                pick.append((a, i))
                si -= 3
                continue

            updated.append(i)

            m = (a + b) // 2
            stack[si - 3:si] = (i << 1, a, m)
            stack[si:si + 3] = ((i << 1) + 1, m, b)
            si += 3

        while updated:
            i = updated.pop()
            segtree_bottomup(table, i)

        pick.sort()
        cnt0, cnt1 = 0, 0
        res = 0
        for a, i in pick:
            r0, r1, r2 = table[i, 0], table[i, 1], table[i, 2]
            res += r2 + cnt1 * r0
            cnt0 += r0
            cnt1 += r1
        return res

    def segtree_debug_print(ins):
        table = SEGTREE_TABLES[ins]
        offset = table.shape[0] >> 1
        for t in range(4):
            i = 1
            while i <= offset:
                print(table[i:2 * i, t])
                i <<= 1

    n = inp[0]
    aaa = inp[2:n + 2]

    ins = segtree_init(n)
    segtree_build(ins, aaa)

    qi = n + 2
    ans = []
    while qi < inp.size:
        t = inp[qi]
        if t == 1:
            segtree_range_swap(ins, inp[qi + 1] - 1, inp[qi + 2])
            qi += 3
        else:
            ans.append(segtree_query(ins, inp[qi + 1] - 1, inp[qi + 2]))
            qi += 3

    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))

Solution (Python):
import os
import sys

import numpy as np


def solve(inp):
    SEGTREE_TABLES = []
    COMMON_STACK = np.zeros(10 ** 7, dtype=np.int64)

    def bit_length(n):
        ret = 0
        while n:
            n >>= 1
            ret += 1
        return ret

    def segtree_init(n):
        n2 = 1 << bit_length(n)
        table = np.zeros((4, n2 << 1), dtype=np.int64)
        SEGTREE_TABLES.append(table)
        return len(SEGTREE_TABLES) - 1

    def segtree_build(ins, arr):
        table = SEGTREE_TABLES[ins]
        offset = table.shape[1] >> 1
        table[1] = 1
        table[0, offset:offset + len(arr)] = 1 - arr
        table[1, offset:offset + len(arr)] = arr
        for i in range(offset - 1, 0, -1):
            ch = i << 1
            table[0, i] = table[0, ch] + table[0, ch + 1]
            table[1, i] = table[1, ch] + table[1, ch + 1]
            table[2, i] = table[2, ch] + table[2, ch + 1] + table[1, ch] * table[0, ch + 1]

    def segtree_eval(table, offset, i):
        if table[3, i] == 0:
            return
        if i < offset:
            ch = i << 1
            table[3, ch] ^= 1
            table[3, ch + 1] ^= 1
        table[0, i], table[1, i] = table[1, i], table[0, i]
        table[2, i] = table[0, i] * table[1, i] - table[2, i]
        table[3, i] = 0

    def segtree_bottomup(table, i):
        lch = i << 1
        rch = lch + 1
        l0, l1, l2 = table[0, lch], table[1, lch], table[2, lch]
        r0, r1, r2 = table[0, rch], table[1, rch], table[2, rch]
        if table[3, lch]:
            l0, l1 = l1, l0
            l2 = l0 * l1 - l2
        if table[3, rch]:
            r0, r1 = r1, r0
            r2 = r0 * r1 - r2
        table[0, i] = l0 + r0
        table[1, i] = l1 + r1
        table[2, i] = l2 + r2 + l1 * r0

    def segtree_range_swap(ins, l, r):
        """ i for [l, r),  Ai ← ~Ai """
        table = SEGTREE_TABLES[ins]
        offset = table.shape[1] >> 1
        stack = COMMON_STACK
        stack[:3] = (1, 0, offset)
        si = 3
        updated = []
        while si:
            i, a, b = stack[si - 3:si]
            segtree_eval(table, offset, i)

            if b <= l or r <= a:
                si -= 3
                continue

            if l <= a and b <= r:
                table[3, i] ^= 1
                si -= 3
                continue

            updated.append(i)

            m = (a + b) // 2
            stack[si - 3:si] = (i << 1, a, m)
            stack[si:si + 3] = ((i << 1) + 1, m, b)
            si += 3

        while updated:
            i = updated.pop()
            segtree_bottomup(table, i)

    def segtree_query(ins, l, r):
        """ sum [l, r) """
        table = SEGTREE_TABLES[ins]
        offset = table.shape[1] >> 1
        stack = COMMON_STACK
        stack[:3] = (1, 0, offset)
        si = 3
        pick = []
        updated = []

        while si:
            i, a, b = stack[si - 3:si]

            segtree_eval(table, offset, i)

            if b <= l or r <= a:
                si -= 3
                continue

            if l <= a and b <= r:
                pick.append((a, i))
                si -= 3
                continue

            updated.append(i)

            m = (a + b) // 2
            stack[si - 3:si] = (i << 1, a, m)
            stack[si:si + 3] = ((i << 1) + 1, m, b)
            si += 3

        while updated:
            i = updated.pop()
            segtree_bottomup(table, i)

        pick.sort()
        cnt0, cnt1 = 0, 0
        res = 0
        for a, i in pick:
            r0, r1, r2 = table[0, i], table[1, i], table[2, i]
            res += r2 + cnt1 * r0
            cnt0 += r0
            cnt1 += r1
        return res

    def segtree_debug_print(ins):
        table = SEGTREE_TABLES[ins]
        offset = table.shape[1] >> 1
        for t in range(4):
            i = 1
            while i <= offset:
                print(table[t, i:2 * i])
                i <<= 1

    n = inp[0]
    aaa = inp[2:n + 2]

    ins = segtree_init(n)
    segtree_build(ins, aaa)

    qi = n + 2
    ans = []
    while qi < inp.size:
        t = inp[qi]
        if t == 1:
            segtree_range_swap(ins, inp[qi + 1] - 1, inp[qi + 2])
            qi += 3
        else:
            ans.append(segtree_query(ins, inp[qi + 1] - 1, inp[qi + 2]))
            qi += 3

    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))

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 s.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(s, 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(s, 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 g(x):
  return x[2] <= 1

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

  
  seg.set(0, [1, 0, 0])
  g1 = seg.get(0)
  seg.set(0, [0, 1, 0])
  g2 = seg.get(0)
  a = seg.all_prod()
  r = seg.max_right(0, g)
  l = seg.min_left(N, g)
  

main()