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

Solution code:
import sys
input = sys.stdin.readline

class Lazysegtree:
    def __init__(self, A, fx, ex, fm, em, fa, initialize = True):
        # Aの入力形式は要素が(0の数,1の数,転倒数)のtupleになっている配列
        self.n = len(A)
        self.n0 = 2**(self.n-1).bit_length() 
        self.fm = fm # fm:モノイド関数を指定
        self.ex = ex # 単位元と遅延評価用の数字を突っ込むためのtuple
        self.em = em # 遅延評価後のtreeに仕込む元
        self.lazy = [em]*(2*self.n0) # 遅延評価後のtree配列
        if initialize: # Aをself.dataに仕込む
            self.data = [self.ex]*self.n0 + A + [self.ex]*(self.n0 - self.n)
            for i in range(self.n0-1, -1, -1):
                self.data[i] = self.fx(self.data[i*2], self.data[i*2+1])
                # 偶数index × 奇数indexをしてtreeの上側を更新
        else: # Aを仕込まないときは元で穴埋め
            self.data = [self.ex]*(2*self.n0)
    def fx(self, x, y): # クエリ関数、今回は転倒数
        return (x[0]+y[0], x[1]+y[1], x[2]+y[2]+x[1]*y[0])

    def fa(self, ope, idx):
        if ope == 0:
            return self.data[idx]
        zero, one, t = self.data[idx]
        return (one, zero, (one+zero)*(one+zero-1)//2 - one*(one-1)//2 - zero*(zero-1)//2 - t)

    def _ascend(self, k): # treeを登って更新
        k = k >> 1
        c = k.bit_length()
        for j in range(c):
            idx = k >> j
            self.data[idx] = self.fx(self.data[2*idx], self.data[2*idx+1])
            
    def _descend(self, k):  # treeを降りて更新
        k = k >> 1          # 降りるときに遅延評価後のtreeも更新
        idx = 1
        c = k.bit_length()
        for j in range(1, c+1):
            idx = k >> (c - j)
            if self.lazy[idx] == self.em:
                continue
            self.data[2*idx] = self.fa(self.lazy[idx], 2*idx) 
            self.data[2*idx+1] = self.fa(self.lazy[idx], 2*idx+1)
            self.lazy[2*idx] = self.fm(self.lazy[idx], self.lazy[2*idx])
            self.lazy[2*idx+1] = self.fm(self.lazy[idx], self.lazy[2*idx+1])
            self.lazy[idx] = self.em

    def query(self, l, r): # [l,r)のクエリ関数の出力
        L = l+self.n0
        R = r+self.n0
        self._descend(L//(L & -L))
        self._descend(R//(R & -R)-1)
        
        sl = self.ex
        sr = self.ex                                                                   

        while L < R:
            if R & 1:
                R -= 1
                sr = self.fx(self.data[R], sr)
            if L & 1:
                sl = self.fx(sl, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return self.fx(sl, sr)
    
    def operate(self, l, r, x): # [l,r)の各yに対してfm(x,y)をする
        L = l+self.n0
        R = r+self.n0
        Li = L//(L & -L)
        Ri = R//(R & -R)
        self._descend(Li)
        self._descend(Ri-1)
        
        while L < R :
            if R & 1:
                R -= 1
                self.data[R] = self.fa(x, R)
                self.lazy[R] = self.fm(x, self.lazy[R])
            if L & 1:
                self.data[L] = self.fa(x, L)
                self.lazy[L] = self.fm(x, self.lazy[L])
                L += 1
            L >>= 1
            R >>= 1
        
        self._ascend(Li)
        self._ascend(Ri-1)

N, Q = map(int, input().split())
*A, = map(int, input().split())
A = [(0, 1, 0) if a == 1 else (1, 0, 0) for a in A]
segtree = Lazysegtree(A, None, (0, 0, 0), lambda x,y:x^y, 0, None, initialize = True)

ans = []
for i in range(Q):
    t,l,r = map(int, input().split())
    if t == 1:
        segtree.operate(l-1, r, 1)
    else:
        ans.append(segtree.query(l-1, r)[2])

for i in range(len(ans)):
    print(ans[i])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


class LazySegTree():  # モノイドに対して適用可能、Nが2冪でなくても良い
    def __init__(self,N,X_func,A_func,operate,X_unit,A_unit):
        self.N = N
        self.X_func = X_func
        self.A_func = A_func
        self.operate = operate
        self.X_unit = X_unit
        self.A_unit = A_unit
        self.X = [self.X_unit]*(2*self.N)
        self.A = [self.A_unit]*(2*self.N)
        self.size = [0]*(2*self.N)

    def build(self,init_value):  # 初期値を[N,2N)に格納
        for i in range(self.N):
            self.X[self.N+i] = init_value[i]
            self.size[self.N+i] = 1
        for i in range(self.N-1,0,-1):
            self.X[i] = self.X_func(self.X[i << 1],self.X[i << 1 | 1])
            self.size[i] = self.size[i << 1] + self.size[i << 1 | 1]

    def update(self,i,x):  # i番目(0-index)の値をxに変更
        i += self.N
        self.X[i] = x
        i >>= 1
        while i:
            self.X[i] = self.X_func(self.X[i << 1],self.X[i << 1 | 1])
            i >>= 1

    def eval_at(self,i):  # i番目で作用を施した値を返す
        return self.operate(self.X[i],self.A[i],self.size[i])

    def eval_above(self,i):  # i番目より上の値を再計算する
        i >>= 1
        while i:
            self.X[i] = self.X_func(self.eval_at(i << 1),self.eval_at(i << 1 | 1))
            i >>= 1

    def propagate_at(self,i):  # i番目で作用を施し、1つ下に作用の情報を伝える
        self.X[i] = self.eval_at(i)
        self.A[i << 1] = self.A_func(self.A[i << 1],self.A[i])
        self.A[i << 1 | 1] = self.A_func(self.A[i << 1 | 1], self.A[i])
        self.A[i] = self.A_unit

    def propagate_above(self,i):  # i番目より上で作用を施す
        H = i.bit_length()
        for h in range(H,0,-1):
            self.propagate_at(i >> h)

    def fold(self,L,R):  # [L,R)の区間取得
        L += self.N
        R += self.N
        L0 = L // (L & -L)
        R0 = R // (R & -R) - 1
        self.propagate_above(L0)
        self.propagate_above(R0)
        vL = self.X_unit
        vR = self.X_unit
        while L < R:
            if L & 1:
                vL = self.X_func(vL,self.eval_at(L))
                L += 1
            if R & 1:
                R -= 1
                vR = self.X_func(self.eval_at(R),vR)
            L >>= 1
            R >>= 1
        return self.X_func(vL,vR)

    def operate_range(self,L,R,x):  # [L,R)にxを作用
        L += self.N
        R += self.N
        L0 = L // (L & -L)
        R0 = R // (R & -R) - 1
        self.propagate_above(L0)
        self.propagate_above(R0)
        while L < R:
            if L & 1:
                self.A[L] = self.A_func(self.A[L],x)
                L += 1
            if R & 1:
                R -= 1
                self.A[R] = self.A_func(self.A[R],x)
            L >>= 1
            R >>= 1
        self.eval_above(L0)
        self.eval_above(R0)


N,Q = MI()
A = LI()
B = []
for i in range(N):
    if A[i] == 0:
        B.append((0,1,0))
    else:
        B.append((0,0,1))
# (その区間の転倒数,0の個数,1の個数)


def X_func(x,y):
    x0,x1,x2 = x
    y0,y1,y2 = y
    return (x0+y0+x2*y1,x1+y1,x2+y2)


def A_func(a,b):
    return a ^ b


def operate(x,a,r):  # 右作用
    if a == 0:
        return x
    x0,x1,x2 = x
    return (x1*x2-x0,x2,x1)


X_unit = (0,0,0)
A_unit = 0


LST = LazySegTree(N,X_func,A_func,operate,X_unit,A_unit)
LST.build(B)

for i in range(Q):
    T,L,R = MI()
    if T == 1:
        LST.operate_range(L-1,R,1)
    else:
        print(LST.fold(L-1,R)[0])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


class LazySegTree():  # モノイドに対して適用可能、Nが2冪でなくても良い
    def __init__(self,N,X_func,A_func,operate,X_unit,A_unit):
        self.N = N
        self.X_func = X_func
        self.A_func = A_func
        self.operate = operate
        self.X_unit = X_unit
        self.A_unit = A_unit
        self.X = [self.X_unit]*(2*self.N)
        self.A = [self.A_unit]*(2*self.N)
        self.size = [0]*(2*self.N)

    def build(self,init_value):  # 初期値を[N,2N)に格納
        for i in range(self.N):
            self.X[self.N+i] = init_value[i]
            self.size[self.N+i] = 1
        for i in range(self.N-1,0,-1):
            self.X[i] = self.X_func(self.X[i << 1],self.X[i << 1 | 1])
            self.size[i] = self.size[i << 1] + self.size[i << 1 | 1]

    def update(self,i,x):  # i番目(0-index)の値をxに変更
        i += self.N
        self.X[i] = x
        i >>= 1
        while i:
            self.X[i] = self.X_func(self.X[i << 1],self.X[i << 1 | 1])
            i >>= 1

    def eval_at(self,i):  # i番目で作用を施した値を返す
        return self.operate(self.X[i],self.A[i],self.size[i])

    def eval_above(self,i):  # i番目より上の値を再計算する
        i >>= 1
        while i:
            self.X[i] = self.X_func(self.eval_at(i << 1),self.eval_at(i << 1 | 1))
            i >>= 1

    def propagate_at(self,i):  # i番目で作用を施し、1つ下に作用の情報を伝える
        self.X[i] = self.operate(self.X[i],self.A[i],self.size[i])
        self.A[i << 1] = self.A_func(self.A[i << 1],self.A[i])
        self.A[i << 1 | 1] = self.A_func(self.A[i << 1 | 1], self.A[i])
        self.A[i] = self.A_unit

    def propagate_above(self,i):  # i番目より上で作用を施す
        H = i.bit_length()
        for h in range(H,0,-1):
            self.propagate_at(i >> h)

    def fold(self,L,R):  # [L,R)の区間取得
        L += self.N
        R += self.N
        L0 = L // (L & -L)
        R0 = R // (R & -R) - 1
        self.propagate_above(L0)
        self.propagate_above(R0)
        vL = self.X_unit
        vR = self.X_unit
        while L < R:
            if L & 1:
                vL = self.X_func(vL,self.eval_at(L))
                L += 1
            if R & 1:
                R -= 1
                vR = self.X_func(self.eval_at(R),vR)
            L >>= 1
            R >>= 1
        return self.X_func(vL,vR)

    def operate_range(self,L,R,x):  # [L,R)にxを作用
        L += self.N
        R += self.N
        L0 = L // (L & -L)
        R0 = R // (R & -R) - 1
        self.propagate_above(L0)
        self.propagate_above(R0)
        while L < R:
            if L & 1:
                self.A[L] = self.A_func(self.A[L],x)
                L += 1
            if R & 1:
                R -= 1
                self.A[R] = self.A_func(self.A[R],x)
            L >>= 1
            R >>= 1
        self.eval_above(L0)
        self.eval_above(R0)


N,Q = MI()
A = LI()
B = []
for i in range(N):
    if A[i] == 0:
        B.append((0,1,0))
    else:
        B.append((0,0,1))
# (その区間の転倒数,0の個数,1の個数)


def X_func(x,y):
    x0,x1,x2 = x
    y0,y1,y2 = y
    return (x0+y0+x2*y1,x1+y1,x2+y2)


def A_func(a,b):
    return a ^ b


def operate(x,a,r):  # 右作用
    if a == 0:
        return x
    x0,x1,x2 = x
    return (x1*x2-x0,x2,x1)


X_unit = (0,0,0)
A_unit = 0


LST = LazySegTree(N,X_func,A_func,operate,X_unit,A_unit)
LST.build(B)

for i in range(Q):
    T,L,R = MI()
    if T == 1:
        LST.operate_range(L-1,R,1)
    else:
        print(LST.fold(L-1,R)[0])

Submission status: Accepted

Solution code:
class SegmentTreeLazy():
    def __init__(self, arr, ti, ei, func, op, merge):
        self.h = (len(arr) - 1).bit_length()
        self.n = 2**self.h
        self.func = func
        self.op = op
        self.merge = merge
        self.ti = ti
        self.ei = ei
        self.val = [ti for _ in range(2 * self.n)]
        for i in range(len(arr)):
            self.val[self.n + i] = arr[i]
        for i in range(1, self.n)[::-1]:
            self.val[i] = self.func(self.val[2 * i], self.val[2 * i + 1])
        self.laz = [ei for _ in range(2 * self.n)]

    def reflect(self, k):
        if self.laz[k] == self.ei:
            return self.val[k]
        return self.op(self.val[k], self.laz[k])

    def propagate(self, k):
        if self.laz[k] == self.ei: return
        self.laz[2 * k] = self.merge(self.laz[2 * k], self.laz[k])
        self.laz[2 * k + 1] = self.merge(self.laz[2 * k + 1], self.laz[k])
        self.val[k] = self.reflect(k)
        self.laz[k] = self.ei

    def thrust(self, k):
        for i in range(1, self.h + 1)[::-1]:
            self.propagate(k >> i)

    def recalc(self, k):
        while k:
            k >>= 1
            self.val[k] = self.func(self.reflect(2 * k), self.reflect(2 * k + 1))

    def update(self, lt, rt, x):
        lt += self.n
        rt += self.n
        vl = lt
        vr = rt
        self.thrust(lt)
        self.thrust(rt - 1)
        while rt - lt > 0:
            if lt & 1:
                self.laz[lt] = self.merge(self.laz[lt], x)
                lt += 1
            if rt & 1:
                rt -= 1
                self.laz[rt] = self.merge(self.laz[rt], x)
            lt >>= 1
            rt >>= 1
        self.recalc(vl)
        self.recalc(vr - 1)

    def query(self, lt, rt):
        lt += self.n
        rt += self.n
        self.thrust(lt)
        self.thrust(rt - 1)
        vl = vr = self.ti
        while rt - lt > 0:
            if lt & 1:
                vl = self.func(vl, self.reflect(lt))
                lt += 1
            if rt & 1:
                rt -= 1
                vr = self.func(self.reflect(rt), vr)
            lt >>= 1
            rt >>= 1
        return self.func(vl, vr)

import sys
input = sys.stdin.readline

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

def func(x, y):
    x0, x1, x2 = x
    y0, y1, y2 = y
    return x0 + y0, x1 + y1, x2 + y2 + x1 * y0

def op(x, p):
    x0, x1, x2 = x
    if p:
        return x1, x0, x0 * x1 - x2
    else:
        return x0, x1, x2

def merge(p, q):
    return p ^ q

arr = [(1 - a, a, 0) for a in A]
ti = (0, 0, 0)
ei = 0

st = SegmentTreeLazy(arr, ti, ei, func, op, merge)
res = list()

for _ in range(Q):
    t, l, r = map(int, input().split())
    if t == 1:
        st.update(l - 1, r, 1)
    else:
        res.append(st.query(l - 1, r)[2])

print('\n'.join(map(str, res)))

Submission status: Accepted

Solution code:
# self.data: 1-indexed
#    __1__
#  _2_   _3_
# 4   5 6   7

# f(f(a, b), c) == f(a, f(b, c))

class LazySegmentTree:
    # a = [default] * n
    # O(n)
    def __init__(self, n, f, default=(0, 0, 1)):
        self.num_leaf = 2 ** (n-1).bit_length()
        self.data = [default] * (2*self.num_leaf)
        self.lazy = [True] * (2*self.num_leaf)
        self.f = f

    # You can use first_update before you use update.
    # a[i] = x
    # O(log(n))
    def first_update(self, i, x):
        i += self.num_leaf
        self.data[i] = x
        i >>= 1
        while i > 0:
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
            i >>= 1

    def gindex(self, l, r):
        lis = []
        l += self.num_leaf
        r += self.num_leaf
        lm = (l // (l & -l)) >> 1
        rm = (r // (r & -r)) >> 1
        while l < r:
            if l <= lm:
                lis.append(l)
            if r <= rm:
                lis.append(r)
            l >>= 1
            r >>= 1
        while l:
            lis.append(l)
            l >>= 1
        lis.reverse()
        return lis

    def lazy_processing(self, i):
        inversion, num_0, num_1 = self.data[i]
        self.data[i] = (num_0 * num_1 - inversion, num_1, num_0)
        self.lazy[i] = not self.lazy[i]

    # from parent to children
    def propagate(self, lis):
        for i in lis:
            if self.lazy[i]:
                continue
            self.lazy_processing(2*i)
            self.lazy_processing(2*i+1)
            self.lazy[i] = True

    # update a[l:r]
    def update(self, l, r):
        lis = self.gindex(l, r)

        # top-down propagation
        self.propagate(lis)

        l += self.num_leaf
        r += self.num_leaf - 1
        while l < r:
            if l & 1:
                self.lazy_processing(l)
                l += 1
            if not r & 1:
                self.lazy_processing(r)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            self.lazy_processing(l)

        # bottom-up propagation
        lis.reverse()
        for i in lis:
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])

    # return f(a[l:r])
    def query(self, l, r):
        # top-down propagation
        self.propagate(self.gindex(l, r))

        l += self.num_leaf
        r += self.num_leaf - 1
        lres, rres = (0, 1, 0), self.data[0] # self.data[0] == default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.data[l])
                l += 1
            if not r & 1:
                rres = self.f(self.data[r], rres)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            res = self.f(self.f(lres, self.data[l]), rres)
        else:
            res = self.f(lres, rres)
        return res

from sys import stdin
input = stdin.buffer.readline

def main():
    n, q = map(int, input().split())
    a = list(map(int, input().split()))

    # tup = (inversion, num_0, num_1)
    def f(tup1, tup2):
        return (tup1[0] + tup2[0] + tup1[2] * tup2[1], tup1[1] + tup2[1], tup1[2] + tup2[2])

    lst = LazySegmentTree(n, f=f)

    for i, x in enumerate(a):
        lst.first_update(i, (0, 1-x, x))

    ans = []
    for _ in range(q):
        t, l, r = list(map(int, input().split()))
        if t == 1:
            lst.update(l-1, r)
        else:
            ans.append(lst.query(l-1, r)[0])

    for i in ans:
        print(i)

main()

Submission status: Accepted

Solution code:
# self.data: 1-indexed
#    __1__
#  _2_   _3_
# 4   5 6   7

# f(f(a, b), c) == f(a, f(b, c))

class LazySegmentTree:
    # a = [default] * n
    # O(n)
    def __init__(self, n, f, default=(0, 0, 1)):
        self.num_leaf = 2 ** (n-1).bit_length()
        self.data = [default] * (2*self.num_leaf)
        self.lazy = [True] * (2*self.num_leaf)
        self.f = f

    # You can use first_update before you use update.
    # a[i] = x
    # O(log(n))
    def first_update(self, i, x):
        i += self.num_leaf
        self.data[i] = x
        i >>= 1
        while i > 0:
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
            i >>= 1

    def gindex(self, l, r):
        lis = []
        l += self.num_leaf
        r += self.num_leaf
        lm = (l // (l & -l)) >> 1
        rm = (r // (r & -r)) >> 1
        while l < r:
            if l <= lm:
                lis.append(l)
            if r <= rm:
                lis.append(r)
            l >>= 1
            r >>= 1
        while l:
            lis.append(l)
            l >>= 1
        lis.reverse()
        return lis

    def lazy_processing(self, i):
        self.data[i] = (self.data[i][1] * self.data[i][2] - self.data[i][0], self.data[i][2], self.data[i][1])
        self.lazy[i] = not self.lazy[i]

    # from parent to children
    def propagate(self, lis):
        for i in lis:
            if self.lazy[i]:
                continue
            self.lazy_processing(2*i)
            self.lazy_processing(2*i+1)
            self.lazy[i] = True

    # update a[l:r]
    def update(self, l, r):
        lis = self.gindex(l, r)

        # top-down propagation
        self.propagate(lis)

        l += self.num_leaf
        r += self.num_leaf - 1
        while l < r:
            if l & 1:
                self.lazy_processing(l)
                l += 1
            if not r & 1:
                self.lazy_processing(r)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            self.lazy_processing(l)

        # bottom-up propagation
        lis.reverse()
        for i in lis:
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])

    # return f(a[l:r])
    def query(self, l, r):
        # top-down propagation
        self.propagate(self.gindex(l, r))

        l += self.num_leaf
        r += self.num_leaf - 1
        lres, rres = (0, 1, 0), self.data[0] # self.data[0] == default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.data[l])
                l += 1
            if not r & 1:
                rres = self.f(self.data[r], rres)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            res = self.f(self.f(lres, self.data[l]), rres)
        else:
            res = self.f(lres, rres)
        return res

from sys import stdin
input = stdin.buffer.readline

def main():
    n, q = map(int, input().split())
    a = list(map(int, input().split()))

    def f(tup1, tup2):
        return (tup1[0] + tup2[0] + tup1[2] * tup2[1], tup1[1] + tup2[1], tup1[2] + tup2[2])

    lst = LazySegmentTree(n, f=f)

    for i, x in enumerate(a):
        lst.first_update(i, (0, 1-x, x))

    ans = []
    for _ in range(q):
        t, l, r = list(map(int, input().split()))
        if t == 1:
            lst.update(l-1, r)
        else:
            ans.append(lst.query(l-1, r)[0])

    for i in ans:
        print(i)

main()

Submission status: Accepted

Solution code:
# もしかしてコードの順番が関係あったりしますか

# 同じインデックスの重複を除くので、関数の呼び出し回数が少し少ないはず。
# ただ、重複を除く分のオーバーヘッドがあるので、
# fmm, fmo, fooが軽い関数だと、スピードはそこまで出ない。


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

        # propagation
        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

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

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

        # propagation
        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

        # effect
        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

        # recalculation
        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

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

        # fold
        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():
    # Monoid:   ((0の数), (1の数), (転倒数))
    # Operator: 反転するか? (1 or 0) 

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