沙发

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100005;
int n, m, w[N];
struct Seg{
int L0, R0, L1, R1, C0, C1, R[2][2], L[2][2];
LL res;
void init() {
L0 = R0 = L1 = R1 = C0 = C1 = res = 0;
memset(R, 0, sizeof R), memset(L, 0, sizeof L);
}
Seg(){}
Seg(int x){
init();
if (x) L1 = R1 = C1 = L[0][1] = R[0][1] = res = 1;
else L0 = R0 = C0 = L[1][0] = R[1][0] = 1;
}
Seg(Seg A, Seg B, int mid) {
init();
C0 = A.C0 + B.C0, C1 = A.C1 + B.C1;
L0 = A.L0 + (!A.C1 ? B.L0 : 0), R0 = B.R0 + (!B.C1 ? A.R0 : 0);
L1 = A.L1 + (!A.C1 ? B.L1 : 0) + (A.C1 == 1 ? B.L0 : 0);
R1 = B.R1 + (!B.C1 ? A.R1 : 0) + (B.C1 == 1 ? A.R0 : 0);
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
L[i][j] = A.L[i][j] + (i >= A.C0 ? B.L[i - A.C0][j ^ (A.C1 & 1)] : 0);
R[i][j] = B.R[i][j] + (i >= B.C0 ? A.R[i - B.C0][j ^ (B.C1 & 1)] : 0);
}
}
res = A.res + B.res;
res += (LL)A.R0 * B.L1 + (LL)A.R1 * B.L0;
res += (LL)A.R[0][0] * (B.L[0][1] + B.L[1][1]) + (LL)A.R[0][1] * (B.L[0][0] + B.L[1][0]);
res += (LL)A.R[1][0] * B.L[0][1] + (LL)A.R[1][1] * B.L[0][0];
if (w[mid] + w[mid + 1] == 1) res--;
}
} v[N << 2];

void build(int p, int l, int r) {
if (l == r) { v[p] = Seg(w[l]); return; }
int mid = (l + r) >> 1;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
v[p] = Seg(v[p << 1], v[p << 1 | 1], mid);
}

void change(int p, int l, int r, int x) {
if (l == r) { v[p] = Seg(w[l]); return; }
int mid = (l + r) >> 1;
if (x <= mid) change(p << 1, l, mid, x);
else change(p << 1 | 1, mid + 1, r, x);
v[p] = Seg(v[p << 1], v[p << 1 | 1], mid);
}

Seg query(int p, int l, int r, int x, int y) {
if (x <= l && r <= y) return v[p];
int mid = (l + r) >> 1;
if (y <= mid) return query(p << 1, l, mid, x, y);
if (mid < x) return query(p << 1 | 1, mid + 1, r, x, y);
return Seg(query(p << 1, l, mid, x, y), query(p << 1 | 1, mid + 1, r, x, y), mid);
}

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", w + i);
build(1, 1, n);
scanf("%d", &m);
while (m--) {
int opt; scanf("%d", &opt);
if (opt == 1) {
int x; scanf("%d", &x);
w[x] ^= 1, change(1, 1, n, x);
} else {
int l, r; scanf("%d%d", &l, &r);
LL sum = (LL)(r - l + 1) * (r - l + 2) / 2;
printf("%lld\n", sum - query(1, 1, n, l, r).res);
}
}
return 0;
}