Cool segment tree

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

const int N = (int)5e5+111;

int n;
int t[2][4*N];
int w[2][4*N];
int a[2][N];
int sz[2];

void build(int v,int l,int r,int T){
    if(l == r){
        t[T][v] = a[T][l];
        return;
    }
    int m = (l+r)>>1;
    build(v<<1,l,m,T);
    build(v<<1|1,m+1,r,T);
    t[T][v] = t[T][v<<1] + t[T][v<<1|1];
    return;
}

void push(int v,int l,int r,int T){
    if(w[T][v] == 0)
        return;
    int m = (l+r)>>1;
    t[T][v<<1] = m-l+1-t[T][v<<1];
    t[T][v<<1|1] = r-m-t[T][v<<1|1];
    w[T][v<<1] ^= 1;
    w[T][v<<1|1] ^= 1;
    w[T][v] = 0;
    return;
}

int get(int v,int l,int r,int tl,int tr,int T){
    if(l > r || tl > tr)
        return 0;
    if(l == tl && r == tr)
        return t[T][v];
    push(v,l,r,T);
    int m = (l+r)>>1;
    return get(v<<1,l,m,tl,min(tr,m),T)
        +  get(v<<1|1,m+1,r,max(tl,m+1),tr,T);
}

void upd(int v,int l,int r,int tl,int tr,int T){
    if(l > r || tl > tr)
        return;
    if(l == tl && r == tr){
        t[T][v] = r-l+1 - t[T][v];
        w[T][v] ^= 1;
        return;
    }
    push(v,l,r,T);
    int m = (l+r)>>1;
    upd(v<<1,l,m,tl,min(m,tr),T);
    upd(v<<1|1,m+1,r,max(tl,m+1),tr,T);
    t[T][v] = t[T][v<<1] + t[T][v<<1|1];
    return;
}

int get(int l,int r,int T){
    return get(1,1,sz[T],l,r,T);
}

void upd(int l,int r,int T){
    upd(1,1,sz[T],l,r,T);
    return;
}

int get0(int l,int r){
    if(l % 2 == 1)
        l++;
    if(r % 2 == 1)
        r--;
    if(l > r)
        return 0;
    l = (l+1)/2;
    r = (r+1)/2;
    return get(l,r,0);
}

int get1(int l,int r){
    if(l % 2 == 0)
        l++;
    if(r % 2 == 0)
        r--;
    if(l > r)
        return 0;
    l = (l+1)/2;
    r = (r+1)/2;
    return get(l,r,1);
}

int get(int l,int r){
    return get0(l,r) + get1(l,r);
}

void upd0(int l,int r){
    if(l % 2 == 1)
        l++;
    if(r % 2 == 1)
        r--;
    if(l > r)
        return;
    l = (l+1)/2;
    r = (r+1)/2;
    upd(l,r,0);
    return;
}
void upd1(int l,int r){
    if(l % 2 == 0)
        l++;
    if(r % 2 == 0)
        r--;
    if(l > r)
        return;
    l = (l+1)/2;
    r = (r+1)/2;
//    cerr << "upd1: l,r = " << l << " " << r << "\n";
    upd(l,r,1);
    return;
}

void upd(int l,int r){
    if(l % 2 == 1)
        upd1(l,r);
    else
        upd0(l,r);
    return;
}

void solve(){
    int q;
    cin >> n >> q;

    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;
        a[i%2][++sz[i%2]] = x;
    }

    build(1,1,sz[0],0);
    build(1,1,sz[1],1);

    while(q--){
        int tp,l,r;
        cin >> tp >> l >> r;
        if(tp == 1){
            upd(l,r);
        } else {
//            cout << "ANS = ";
            cout << get(l,r) << "\n";
        }
//        cerr << "A = ";
//        cerr << get(1,1) << " ";
//        cerr << get(2,2) << " ";
//        cerr << get(3,3) << "\n";
//        cerr << get(1,1,sz[1],1,1,1) << " ";
//        cerr << get(1,1,sz[0],1,1,0) << " ";
//        cerr << get(1,1,sz[1],2,2,1) << "\n";
    }

    return;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int tests = 1;
//    cin >> tests;
    while(tests--){
        solve();
    }
}
/**
1 1 2 2 3 3 4 4 5 5 6 6
1 2 3 4 5 6 7 8 9 10 11

2*k-1

10









1 4 2 8 7 6 9 5 3


5 10 27
4 5 25
2 8 14
1 7 3
7 8 20
6 1 3
5 9 28
3 6 11
8 10 32

3 4 20
9 10 3
2 7 31
5 7 14
8 9 2
2 8 6
6 7 25
4 9 10
1 8 23

**/