Problem:


Score : 100 points

Problem Statement

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

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

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

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

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

Constraints

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

0 \leq A_i \leq 1

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

1 \leq T_i \leq 2

1 \leq L_i \leq R_i \leq N

All values in Input are integer.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

2
0
1

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

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

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

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

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



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


Sample output:
2
0
1

Submission status: Time Limit Exceeded

Solution code:
#region bcf
# code section by Barry Fam
#
# pylint: disable= reimported
#region rangedata.py
#region hyperlist.py
import itertools

# def hyperlist(*dim, default_factory=None):
def hyperlist(*dim, **kwarg):
    default_factory = kwarg.pop("default_factory", None)

    ranges = [range(n) for n in dim]

    h = [None]*dim[0]
    for dd in range(1, len(dim)):
        for u in itertools.product(*ranges[:dd]):
            hyperlist_setitem(h, u, [None]*dim[dd])

    if default_factory:
        for u in itertools.product(*ranges):
            hyperlist_setitem(h, u, default_factory())

    return h

def hyperlist_setitem(h, u, a):
    ptr = h
    for i in u[:-1]: ptr = ptr[i]
    ptr[u[-1]] = a

def hyperlist_getitem(h, u):
    ptr = h
    for i in u: ptr = ptr[i]
    return ptr

#endregion hyperlist.py
###############################################################################
import operator
import collections
import itertools
import functools
import math as m
try: m.prod
except AttributeError:
    def _prod(iterable, start=1):
        for x in iterable: start *= x
        return start
    m.prod = _prod


# class RangeOperators:
class RangeOperators(object):  # pylint: disable= useless-object-inheritance
    '''
    Data class to define the behavior of a range data structure

    new() := factory for zero values, e.g. int(). required in most cases

    query(a, b) := the binary query function of the tree. e.g. operator.add() for a cumulative sum
    q_inverse(a, b) := the inverse of the query function, if it exists. required for a Fenwick tree
    q_commutative: bool := True if the query operation is commutative

    update(t, x) := define how the tree will be updated: return the new value of t if updated with x
    u_distributive(t, x, w) := return the new value of t if its w leaves are updated by x. required for lazy propagation
    u_composition(x1, x2) := return an update x that is equivalent to updating by x1 and then by x2. required for lazy propagation
    u_commutative: bool := True if the update operation is commutative. e.g. add() is; but "set to" is not
    '''

    __slots__ = [
        "new",
        "query",
        "q_inverse",
        "q_commutative",
        "update",
        "u_distributive",
        "u_composition",
        "u_commutative",
    ]

    _defaults = dict(
        new= int,
        query= operator.add,
        q_commutative= True,
        q_inverse= operator.sub,
        update= operator.add,
        u_distributive= lambda t, x, w: t + x*w,
        u_composition= lambda x1, x2: x1 + x2,
        u_commutative= True,
    )

    def __init__(self, **kwarg):
        d = kwarg or self._defaults
        for k, v in d.items():
            setattr(self, k, v)

MAXQUERY = RangeOperators(
    new= int,
    query= max,
    q_inverse= None,
    q_commutative= True,
    update= operator.add,
    u_distributive= lambda t, x, w: t + x,
    u_composition= lambda x1, x2: x1 + x2,
    u_commutative= True,
)

MINQUERY = RangeOperators(
    new= int,
    query= min,
    q_inverse= None,
    q_commutative= True,
    update= operator.add,
    u_distributive= lambda t, x, w: t + x,
    u_composition= lambda x1, x2: x1 + x2,
    u_commutative= True,
)

SETUPDATE = RangeOperators(
    new= int,
    query= operator.add,
    q_inverse= operator.sub,
    q_commutative= True,
    update= lambda t, x: x,
    u_distributive= lambda t, x, w: x*w,
    u_composition= lambda x1, x2: x2,
    u_commutative= False,
)


# class SegmentTree:
class SegmentTree(object):  # pylint: disable= useless-object-inheritance
    """
    SegmentTree(n: int) -> new tree of size n
    SegmentTree(iterable) -> new tree, initialized

    Methods:

    update_point(i, value)
    update_range(start, stop, value)
    update_consecutive_points(start, stop, iterable)

    query_point(i)
    query_range(start, stop)
    """

    def __init__(self, arg, sparse=False, ops=RangeOperators(), **kwarg):
        # super().__init__(**kwarg)
        super(SegmentTree, self).__init__(**kwarg)

        try:
            init = list(arg)
            dim = len(init)
        except TypeError:
            init = None
            dim = arg

        self.ops = ops

        if not self.ops.q_commutative:
            h = dim.bit_length()
            if dim != 1 << h-1:
                dim = 1 << h
        self.dim = dim

        self._lazy = self.ops.u_distributive is not None
        self._clean = True

        if sparse:
            self._tree = collections.defaultdict(ops.new)

            @functools.lru_cache(maxsize=dim)
            def seglen(u):
                if u >= self.dim: return 1
                return seglen(u<<1) + seglen(u<<1|1)

            self._seglen = seglen

            if self._lazy:
                self._pending = collections.defaultdict(lambda: None)

        else:
            if init:
                self._tree = [None]*(dim*2)
            else:
                self._tree = [ops.new() for _ in range(dim*2)]

            seglen_precomp = [1]*dim*2
            for u in reversed(range(1, dim)):
                seglen_precomp[u] = seglen_precomp[u<<1] + seglen_precomp[u<<1|1]

            self._seglen = seglen_precomp.__getitem__

            if self._lazy:
                self._pending = [None]*dim

        if init:
            # write leaves
            for u, value in enumerate(init, start=dim):
                self._tree[u] = value
            for u in range(u+1, dim*2):
                self._tree[u] = self.ops.new()

            # build
            self._build_fill(0, dim)


    # Iterators

    def _downward_path(self, i):
        """Iterate over tree indexes from root to just above raw index i"""
        u = self.dim + i
        for s in range(u.bit_length()-1, 0, -1):
            yield u >> s

    def _upward_path(self, i):
        """Iterate over tree indexes from just above raw index i to root"""
        u = self.dim + i
        while u > 1:
            u >>= 1
            yield u

    def _downward_fill(self, i, j):
        """Iterate over every tree index that is an ancestor of raw index range [i,j), from root downwards"""
        n = self.dim
        l = n+i
        r = n+j-1
        for s in range(l.bit_length()-1, 0, -1):
            for u in range(l>>s, (r>>s)+1):
                yield u

    def _upward_fill(self, i, j):
        """Iterate over every tree index that is an ancestor of raw index range [i,j), from just above leaves upwards"""
        n = self.dim
        l = n+i
        r = n+j-1
        while l > 1:
            l >>= 1
            r >>= 1
            for u in reversed(range(l, r+1)):
                yield u

    def _cover_nodes(self, i, j):
        """Iterate over the set of tree indexes whose segments optimally cover raw index range [i,j)"""
        n = self.dim
        l = n+i
        r = n+j
        while l < r:
            if l&1:
                yield l
                l += 1
            if r&1:
                r -= 1
                yield r
            l >>= 1
            r >>= 1

    @staticmethod
    def _left_right_sorted(iterator):
        """For non-commutative query operators, rearrange operands into the correct order"""
        i_list = list(iterator)
        bl = max(i.bit_length() for i in i_list)
        i_list.sort(key=lambda i: i << (bl - i.bit_length()))
        return iter(i_list)

    # Node modification

    def _lazy_update(self, u, value):
        """Update tree index u as if its child leaves had been updated with value"""
        self._tree[u] = self.ops.u_distributive(self._tree[u], value, self._seglen(u))
        if u < self.dim:
            self._clean = False
            if self._pending[u] is None:
                self._pending[u] = value
            else:
                self._pending[u] = self.ops.u_composition(self._pending[u], value)

    def _push1(self, u):
        """Apply any pending lazy update at tree index u to its two immediate children"""
        assert u < self.dim
        if self._clean: return

        value = self._pending[u]
        if value is not None:
            for v in (u<<1, u<<1|1):
                self._lazy_update(v, value)

            self._pending[u] = None

    def _build1(self, u):
        """Calculate the query function at tree index u from its two immediate children"""
        assert u < self.dim
        self._push1(u)
        self._tree[u] = self.ops.query(self._tree[u<<1], self._tree[u<<1|1])


    # Node-set modification

    def _push_path(self, i):
        """Push lazy updates from root to raw index i"""
        if self._clean: return
        for u in self._downward_path(i):
            self._push1(u)

    def _push_fill(self, i, j):
        """Push lazy updates from root to raw index range [i,j)"""
        if self._clean: return
        for u in self._downward_fill(i, j):
            self._push1(u)

        if j-i == self.dim: self._clean = True

    def _build_path(self, i):
        """Update tree nodes from raw index i to root"""
        for u in self._upward_path(i):
            self._build1(u)

    def _build_fill(self, i, j):
        """Update all tree ancestors of raw index range [i,j)"""
        for u in self._upward_fill(i, j):
            self._build1(u)

        if j-i == self.dim: self._clean = True


    # Interface

    def update_consecutive_points(self, start, stop, iterable):
        assert 0 <= start < stop <= self.dim

        # push if necessary
        if not self.ops.u_commutative:
            self._push_fill(start, stop-1)

        # write leaves
        for u, value in zip(range(self.dim + start, self.dim + stop), iterable):
            self._tree[u] = self.ops.update(self._tree[u], value)

        # build
        self._build_fill(start, stop-1)

    def query_range(self, start, stop):
        assert start < stop

        for i in {start, stop-1}:
            self._push_path(i)

        cover_nodes = self._cover_nodes(start, stop)
        if not self.ops.q_commutative:
            cover_nodes = self._left_right_sorted(cover_nodes)

        node_values = (self._tree[u] for u in cover_nodes)
        return functools.reduce(self.ops.query, node_values)

    def update_range(self, start, stop, value):
        assert start < stop

        # if no lazy propagation, fall back to writing to leaves
        if not self._lazy:
            self.update_consecutive_points(start, stop, itertools.repeat(value))
            return

        # push if necessary
        if not self.ops.u_commutative:
            for i in {start, stop-1}:
                self._push_path(i)

        # write cover nodes
        for u in self._cover_nodes(start, stop):
            self._lazy_update(u, value)

        # build
        for i in {start, stop-1}:
            self._build_path(i)

    def query_point(self, i):
        return self.query_range(i, i+1)

    def update_point(self, i, value):
        self.update_range(i, i+1, value)


# class FenwickTree:
class FenwickTree(object):  # pylint: disable= useless-object-inheritance
    """
    ft1d = FenwickTree(dim)
    ft3d = FenwickTree(dim1, dim2, dim3)
    etc.

    Methods:

    ft1d.iadd(i, update_value)
    ft3d.iadd((i,j,k), update_value)

    ft1d[i] = set_value
    fr3d[i,j,k] = set_value

    query = ft1d[i1:i2]
    query = ft3d[i1:i2, j1:j2, k1:k2]
    """

    # def __init__(self, *dim, sparse=False, **kwarg):
    def __init__(self, *dim, **kwarg):
        sparse = kwarg.pop("sparse", False)

        # super().__init__(**kwarg)
        super(FenwickTree, self).__init__(**kwarg)

        self.dim = dim
        self.d = len(dim)

        if sparse:
            self._tree = collections.defaultdict(int)
            if self.d > 1:
                self._tree_setitem = self._tree.__setitem__
                self._tree_getitem = self._tree.__getitem__
        else:
            self._tree = hyperlist(*dim, default_factory=int)
            if self.d > 1:
                self._tree_setitem = functools.partial(hyperlist_setitem, self._tree)
                self._tree_getitem = functools.partial(hyperlist_getitem, self._tree)

        if self.d == 1:
            self.iadd = self._iadd_1d
            self._getitem = self._getitem_1d
        else:
            self.iadd = self._iadd_dd
            self._getitem = self._getitem_dd

    def __setitem__(self, key, value):
        self.iadd(key, value-self[key])

    def __getitem__(self, key):
        return self._getitem(key)

    @staticmethod
    def _set_index_iter(i, n):
        """Iterate over the tree indices < n which are affected when setting raw index i"""
        if i == 0:
            yield 0
            return

        while True:
            yield i
            i += i & -i  # increment LSB
            if i >= n: return

    @staticmethod
    def _get_index_iter(i, j):
        """
        Iterate over the tree indices whose sum equals the sum over the raw range (j,i] -- note that i > j
        Each index is returned as (index, sign) where sign is +1 or -1 for inclusion-exclusion
        """
        if i < 0: return
        if j < 0:
            yield 0, +1
            j = 0

        while i > j:
            yield i, +1
            i &= i-1  # decrement LSB
        while j > i:
            yield j, -1
            j &= j-1  # decrement LSB

    def _iadd_1d(self, key, value):
        assert 0 <= key < self.dim[0]

        for i in self._set_index_iter(key, self.dim[0]):
            self._tree[i] += value

    def _iadd_dd(self, key, value):
        assert len(key) == self.d
        assert all(0 <= i < self.dim[dd] for dd, i in enumerate(key)), "index out of range"

        index_iters = [self._set_index_iter(i, self.dim[dd]) for dd, i in enumerate(key)]
        for u in itertools.product(*index_iters):
            g = self._tree_getitem(u)
            self._tree_setitem(u, g+value)

    def _getitem_1d(self, key):
        if isinstance(key, slice):
            assert key.step is None
            start, stop, _ = key.indices(self.dim[0])
            if stop < start: stop = start
            i, j = stop-1, start-1
        else:
            i, j = key, key-1

        assert -1 <= j <= i < self.dim[0], "index out of range"

        sigma = 0
        for k, sign in self._get_index_iter(i, j):
            sigma += sign * self._tree[k]

        return sigma

    def _getitem_dd(self, key):
        index_iters = []
        for dd, k in enumerate(key):
            if isinstance(k, slice):
                assert k.step is None
                start, stop, _ = k.indices(self.dim[dd])
                if stop < start: stop = start
                itr = self._get_index_iter(stop-1, start-1)
            else:
                assert 0 <= k < self.dim[dd], "index out of range"
                itr = self._get_index_iter(k, k-1)

            index_iters.append(itr)

        assert len(index_iters) == self.d, "mismatched key dimensions"

        sigma = 0
        for i_sign_pairs in itertools.product(*index_iters):
            u, signs = zip(*i_sign_pairs)
            sign = m.prod(signs)

            sigma += sign * self._tree_getitem(u)

        return sigma

#endregion rangedata.py
#endregion bcf
###############################################################################

import sys
def input(itr=iter(sys.stdin.readlines())):  # pylint: disable= redefined-builtin
    return next(itr).rstrip('\n\r')
###############################################################################

import collections

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

ArrayInfo = collections.namedtuple('ArrayInfo', 'zeros ones inversion xinversion')
def query(a, b):
    return ArrayInfo(
        a.zeros + b.zeros,
        a.ones + b.ones,
        a.inversion + b.inversion + (a.ones * b.zeros),
        a.xinversion + b.xinversion + (a.zeros * b.ones)
    )

def update(t, x, _=None):
    return ArrayInfo(t.ones, t.zeros, t.xinversion, t.inversion) if x else t

ops = RangeOperators(
    new= lambda: ArrayInfo(0, 0, 0, 0),
    query= query,
    q_inverse= None,
    q_commutative= False,
    update= update,
    u_distributive= update,
    u_composition= lambda x1, x2: x1^x2,
    u_commutative= True,
)

st = SegmentTree((ArrayInfo(a^1, a, 0, 0) for a in A), ops=ops)

responses = []
for _ in range(Q):
    T, L, R = map(int, input().split())
    if T == 1:
        st.update_range(L-1, R-1+1, 1)
    elif T == 2:
        responses.append(st.query_range(L-1, R-1+1).inversion)

print(*responses, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
class lazy_segtree:
  #遅延評価セグメント木
  def __init__(s, op, e, 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)
  
  # 1点更新
  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)
 
  # 1点取得
  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 s.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]
 
  # 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)
   
  # L固定時の最長区間のR
  def max_right(s, l, g):
    if l == s._n: return s._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
 
  # R固定時の最長区間のL
  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 array.array("l", [l[0] + r[0], l[1] + r[1], l[2] + r[2] + l[1] * r[0]])
 
def e():
  return array.array("l", [0, 0, 0])
 
def mapping(l, r):
  if (not l): return r
  return array.array("l", [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
 
import array
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(array.array("l", [1, 0, 0]))
  else:
    a.append(array.array("l", [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])

Submission status: Time Limit Exceeded

Solution code:
#-------最強ライブラリLazy Segtree(Python)------
#Please don't say you are lazy ｗｗｗｗｗｗｗｗ
#だって Python なら TLE ｗｗｗｗｗｗｗｗｗ

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)
  
  # 1点更新
  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)

  # 1点取得
  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]

  # 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)
   
  # L固定時の最長区間のR
  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

  # R固定時の最長区間のL
  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()

Submission status: Accepted

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((numba.types.optional(i8[:]), ) * 2, cache=True)
def seg_f(x, y):
    if x is None:
        return y
    if y is None:
        return x
    a0, a1, ainv = x
    b0, b1, binv = y
    c0, c1, cinv = a0 + b0, a1 + b1, ainv + binv + a1 * b0
    return np.array([c0, c1, cinv], np.int64)


@njit((b1, b1), cache=True)
def lazy_f(a, b):
    return a ^ b


@njit((i8[:], b1), cache=True)
def operate_f(x, a):
    if not a:
        return x
    x0, x1, xinv = x
    x0, x1, xinv = x1, x0, x0 * x1 - xinv
    return np.array([x0, x1, xinv], np.int64)


@njit((i8[:, :], b1[:], i8), cache=True)
def _eval_at(seg, lazy, i):
    return operate_f(seg[i], lazy[i])


@njit((i8[:, :], b1[:], i8), cache=True)
def _propagate_at(seg, lazy, i):
    seg[i] = _eval_at(seg, lazy, i)
    lazy[i << 1] = lazy_f(lazy[i << 1], lazy[i])
    lazy[i << 1 | 1] = lazy_f(lazy[i << 1 | 1], lazy[i])
    lazy[i] = 0


@njit((i8[:, :], ), cache=True)
def build(raw_data):
    N = len(raw_data)
    seg = np.empty((N + N, 3), np.int64)
    seg[N:] = raw_data
    for i in range(N - 1, 0, -1):
        seg[i] = seg_f(seg[i << 1], seg[i << 1 | 1])
    return seg


@njit((i8[:, :], b1[:], i8), cache=True)
def _propagate_above(seg, lazy, i):
    H = 0
    while 1 << H <= i:
        H += 1
    for h in range(H - 1, 0, -1):
        _propagate_at(seg, lazy, i >> h)


@njit((i8[:, :], b1[:], i8), cache=True)
def _recalc_above(seg, lazy, i):
    while i > 1:
        i >>= 1
        seg[i] = seg_f(_eval_at(seg, lazy, i << 1),
                       _eval_at(seg, lazy, i << 1 | 1))


@njit((i8[:, :], b1[:], i8, i8), cache=True)
def set_val(seg, lazy, i, x):
    N = len(seg) // 2
    i += N
    _propagate_above(seg, lazy, i)
    seg[i], lazy[i] = x, 0
    _recalc_above(seg, lazy, i)


@njit((i8[:, :], b1[:], i8, i8), cache=True)
def fold(seg, lazy, l, r):
    N = len(seg) // 2
    l, r = l + N, r + N
    _propagate_above(seg, lazy, l // (l & -l))
    _propagate_above(seg, lazy, r // (r & -r) - 1)
    vl = vr = None
    while l < r:
        if l & 1:
            vl = seg_f(vl, _eval_at(seg, lazy, l))
            l += 1
        if r & 1:
            r -= 1
            vr = seg_f(_eval_at(seg, lazy, r), vr)
        l, r = l >> 1, r >> 1
    return seg_f(vl, vr)


@njit((i8[:, :], b1[:], i8, i8, i8), cache=True)
def operate_range(seg, lazy, l, r, x):
    N = len(seg) // 2
    l, r = l + N, r + N
    l0, r0 = l // (l & -l), r // (r & -r) - 1
    _propagate_above(seg, lazy, l0)
    _propagate_above(seg, lazy, r0)
    while l < r:
        if l & 1:
            lazy[l] = lazy_f(lazy[l], x)
            l += 1
        if r & 1:
            r -= 1
            lazy[r] = lazy_f(lazy[r], x)
        l, r = l >> 1, r >> 1
    _recalc_above(seg, lazy, l0)
    _recalc_above(seg, lazy, r0)

@njit((i8, i8[:], i8[:]), cache=True)
def main(N, A, TLR):
    seg_raw = np.empty((N, 3), np.int64)
    for i in range(N):
        if A[i] == 0:
            seg_raw[i] = (1, 0, 0)
        elif A[i] == 1:
            seg_raw[i] = (0, 1, 0)
    seg = build(seg_raw)
    lazy = np.zeros(len(seg), np.bool_)
    for i in range(0, len(TLR), 3):
        t, l, r = TLR[i:i + 3]
        l -= 1
        if t == 1:
            operate_range(seg, lazy, l, r, 1)
        else:
            print(fold(seg, lazy, l, r)[2])

N, Q = map(int, readline().split())
A = np.array(readline().split(), np.int64)
TLR = np.array(read().split(), np.int64)

main(N, A, TLR)