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

if False:
    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


mm = 262143
mmm = 68719214592
def f(x, y):
    return x + y + ((x & mm) * (y & mmm) << 18)
def g(x, a, s):
    x0, x1, x2 = x >> 36, (x >> 18) & mm, x & mm
    return (x1 * x2 - x0 << 36) + (x2 << 18) + x1 if a else x
def h(a, b):
    return a ^ b
unitX = 0
unitA = 0

N, Q = map(int, input().split())
A = [(1 << 18) if int(a) == 0 else 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) >> 36)

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

if False:
    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


mm = 262143
def f(x, y):
    x0, x1, x2 = x >> 36, (x >> 18) & mm, x & mm
    y0, y1, y2 = y >> 36, (y >> 18) & mm, y & mm
    return (x0 + y0 + x2 * y1 << 36) + (x1 + y1 << 18) + (x2 + y2)
def g(x, a, s):
    x0, x1, x2 = x >> 36, (x >> 18) & mm, x & mm
    return (x1 * x2 - x0 << 36) + (x2 << 18) + x1 if a else x
def h(a, b):
    return a ^ b
unitX = 0
unitA = 0

N, Q = map(int, input().split())
A = [(1 << 18) if int(a) == 0 else 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) >> 36)

Solution (Python):
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:
            
            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 
        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



            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



        return ans
n,q = list(map(int, input().split()))
a = list(map(int, input().split()))




ninf = (0,0,0) 
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, [((0,1,0) if item==0 else (0,0,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)[0])

write("\n".join(map(str, ans)))

Solution (Python):
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
        while num<=n:
            num *= 2
        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:
            
            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
        q = [k] 
        
        while q:
            k = q.pop()
            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:
                    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
        q = [k]
        ans = ninf
        
        while q:
            k = q.pop()
            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:
                q.append(2*k+2)
                q.append(2*k+1)

        return ans
n,q = list(map(int, input().split()))
a = list(map(int, input().split()))




ninf = (0,0,0) 
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, [((0,1,0) if item==0 else (0,0,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)[0])

write("\n".join(map(str, ans)))

Solution (Python):
header_code = """










namespace aclython {

template <class S, S (*op)(S, S), S (*e)()> struct segtree {
  public:
    segtree() : segtree(0) {}
    segtree(int n) : segtree(std::vector<S>(n, e())) {}
    segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = atcoder::internal::ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        return d[p + size];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;

        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

    S all_prod() { return d[1]; }

    template <bool (*f)(S)> int max_right(int l, S b) {
        return max_right(l, b, [](S x, S y) { return f(x, y); });
    }
    template <class F> int max_right(int l, S b, F f) {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]), b)) {
                while (l < size) {
                    l = (2 * l);
                    if (f(op(sm, d[l]), b)) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*f)(S)> int min_left(int r, S b) {
        return min_left(r, b, [](S x, S y) { return f(x, y); });
    }
    template <class F> int min_left(int r, S b, F f) {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm), b)) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm), b)) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    std::vector<S> d;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};



int min_op(int n, int m){
    return std::min(n, m);
}

int min_e(){
    return (int)1e9;
}

struct segtree_min {
    public:
        segtree_min() : segtree_min(0) {}
        segtree_min(int n) : segtree_min(std::vector<int>(n, min_e())) {}
        segtree_min(const std::vector<int>& vec) : seg(vec) {}

        void set(int p, int x) {seg.set(p, x);}
        int get(int p) {return seg.get(p);}
        int prod(int l, int r) {return seg.prod(l, r);}
        int all_prod() {return seg.all_prod();}

        int max_right(int l, int v) {return seg.max_right(l, v, [](int x, int y) { return x<y; });}
        int min_left(int r, int v) {return seg.min_left(r, v, [](int x, int y) { return x<y; });}

    private:
        segtree<int, min_op, min_e> seg;
};

int max_op(int n, int m){
    return std::max(n, m);
}

int max_e(){
    return 0;
}

struct segtree_max {
    public:
        segtree_max() : segtree_max(0) {}
        segtree_max(int n) : segtree_max(std::vector<int>(n, max_e())) {}
        segtree_max(const std::vector<int>& vec) : seg(vec) {}

        void set(int p, int x) {seg.set(p, x);}
        int get(int p) {return seg.get(p);}
        int prod(int l, int r) {return seg.prod(l, r);}
        int all_prod() {return seg.all_prod();}

        int max_right(int l, int v) {return seg.max_right(l, v, [](int x, int y) { return x<y; });}
        int min_left(int r, int v) {return seg.min_left(r, v, [](int x, int y) { return x<y; });}

    private:
        segtree<int, max_op, max_e> seg;
};


struct S {
    S(long long a, long long b, long long c) : zero(a), one(b), inversion(c){}
    S(const S &s) : zero(s.zero), one(s.one), inversion(s.inversion){}
    // 
    long long zero, one, inversion;
};

// swapping flag
using F = bool;

S op(S l, S r) {
    return S{
        l.zero + r.zero,
        l.one + r.one,
        l.inversion + r.inversion + l.one * r.zero,
    };
}

S e() { return S{0, 0, 0}; }

S mapping(F l, S r) {
    if (!l) return r;
    // swap
    return S{r.one, r.zero, r.one * r.zero - r.inversion};
}

F composition(F l, F r) { return (l && !r) || (!l && r); }

F id() { return false; }

struct lazy_segtree{
    lazy_segtree() : lazy_segtree(0) {}
    lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
    lazy_segtree(const std::vector<S>& vec) : seg(vec) {}
    void set(int p, S x) { seg.set(p, x); }
    S get(int p) { return seg.get(p); }
    S prod(int l, int r) { return seg.prod(l, r); }
    S all_prod() { return seg.all_prod(); }
    void apply(int p, F f) { seg.apply(p, f); }
    void apply(int l, int r, F f) { seg.apply(l, r, f); }
    private:
        atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg;
};

}
"""

code = """






from libcpp cimport bool
from libcpp.vector cimport vector
from libcpp.string cimport string
from libc.stdio cimport getchar, printf
cpdef inline vector[int] ReadInt(int n):
    cdef int b, c
    cdef vector[int] *v = new vector[int]()
    for i in range(n):
        c = 0
        while 1:
            b = getchar() - 48
            if b < 0: break
            c = c * 10 + b
        v.push_back(c)
    return v[0]

cpdef inline vector[string] Read(int n):
    cdef char c
    cdef vector[string] *vs = new vector[string]()
    cdef string *s
    for i in range(n):
        s = new string()
        while 1:
            c = getchar()
            if c<=32: break
            s.push_back(c)
        vs.push_back(s[0])
    return vs[0]

cpdef inline void PrintLongN(vector[long] l, int n):
    for i in range(n): printf("%ld\\n", l[i])

cpdef inline void PrintLong(vector[long] l, int n):
    for i in range(n): printf("%ld ", l[i])
cdef extern from "./intermediate.hpp" namespace "aclython" nogil:
    cdef cppclass segtree_min:
        segtree_min(vector[int] v)
        void set(int p, int x)
        int get(int p)
        int prod(int l, int r)
        int all_prod()
        int max_right(int l, int v)
        int min_left(int r, int v)

cdef class SegTreeMin:
    cdef segtree_min *_thisptr
    def __cinit__(self, vector[int] v):
        self._thisptr = new segtree_min(v)
    cpdef void set(self, int p, int x):
        self._thisptr.set(p, x)
    cpdef int get(self, int p):
        return self._thisptr.get(p)
    cpdef int prod(self, int l, int r):
        return self._thisptr.prod(l, r)
    cpdef int all_prod(self):
        return self._thisptr.all_prod()
    cpdef int max_right(self, int l, int v):
        return self._thisptr.max_right(l, v)
    cpdef int min_left(self, int r, int v):
        self._thisptr.min_left(r, v)

cdef extern from "./intermediate.hpp" namespace "aclython" nogil:
    cdef cppclass segtree_max:
        segtree_max(vector[int] v)
        void set(int p, int x)
        int get(int p)
        int prod(int l, int r)
        int all_prod()
        int max_right(int l, int v)
        int min_left(int r, int v)

cdef class SegTreeMax:
    cdef segtree_max *_thisptr
    def __cinit__(self, vector[int] v):
        self._thisptr = new segtree_max(v)
    cpdef void set(self, int p, int x):
        self._thisptr.set(p, x)
    cpdef int get(self, int p):
        return self._thisptr.get(p)
    cpdef int prod(self, int l, int r):
        return self._thisptr.prod(l, r)
    cpdef int all_prod(self):
        return self._thisptr.all_prod()
    cpdef int max_right(self, int l, int v):
        return self._thisptr.max_right(l, v)
    cpdef int min_left(self, int r, int v):
        self._thisptr.min_left(r, v)


def SegTree(v, op):
    if op=="min":
        return SegTreeMin(v)
    elif op=="max":
        return SegTreeMax(v)

cdef extern from *:
    ctypedef long long ll "long long"

cdef extern from "./intermediate.hpp" namespace "aclython" nogil:
    cdef cppclass S:
        S(ll, ll, ll)
        S(S &)
        ll zero
        ll one
        ll inversion
    ctypedef bool F
    cdef cppclass lazy_segtree:
        lazy_segtree(vector[S] v)
        void set(int p, S x)
        S get(int p)
        S prod(int l, int r)
        S all_prod()
        void apply(int p, F f)
        void apply(int l, int r, F f)

cdef class LazySegTree:
    cdef lazy_segtree *_thisptr
    def __cinit__(self, vector[vector[ll]] v):
        cdef int n = v.size()
        cdef vector[S] *sv = new vector[S]()
        cdef S *s
        for i in range(n):
            s = new S(v.at(i).at(0), v.at(i).at(1), v.at(i).at(2))
            sv.push_back(s[0])
        self._thisptr = new lazy_segtree(sv[0])
    cpdef void set(self, int p, vector[ll] v):
        cdef S *s = new S(v.at(0), v.at(1), v.at(2))
        self._thisptr.set(p, s[0])
    cpdef vector[ll] get(self, int p):
        cdef S *s = new S(self._thisptr.get(p))
        cdef vector[ll] *v = new vector[ll]()
        v.push_back(s.zero)
        v.push_back(s.one)
        v.push_back(s.inversion)
        return v[0]
    cpdef vector[ll] prod(self, int l, int r):
        cdef S *s = new S(self._thisptr.prod(l, r))
        cdef vector[ll] *v = new vector[ll]()
        v.push_back(s.zero)
        v.push_back(s.one)
        v.push_back(s.inversion)
        return v[0]
    cpdef vector[ll] all_prod(self):
        cdef S *s = new S(self._thisptr.all_prod())
        cdef vector[ll] *v = new vector[ll]()
        v.push_back(s.zero)
        v.push_back(s.one)
        v.push_back(s.inversion)
        return v[0]
    cpdef void apply(self, int p, F f):
        self._thisptr.apply(p, f)
    cpdef void apply_range(self, int l, int r, F f):
        self._thisptr.apply(l, r, f)
"""


import os, sys, getpass

if sys.argv[-1] == 'ONLINE_JUDGE':
    code = code.replace("USERNAME", getpass.getuser())
    open('intermediate.hpp','w').write(header_code)
    open('atcoder.pyx','w').write(code)
    os.system('cythonize -i -3 -b atcoder.pyx')
    sys.exit(0)


from atcoder import ReadInt, LazySegTree, PrintLongN

def main():
    N,Q = ReadInt(2)

    A = ReadInt(N)

    AS = [[1,0,0] if a==0 else [0,1,0] for a in A]
    ST = LazySegTree(AS)
    for i in range(Q):
        t, l, r = ReadInt(3)
        l -= 1
        if t==1:
            ST.apply_range(l, r, True)
        else:
            PrintLongN([ST.prod(l, r)[2]], 1)

if __name__=="__main__":
    main()