分析
二进制下每一位模 $3$ 的余数是 $1,2,1,2,\cdots$，也可以看成 $1,-1,1,-1,\cdots$。
假设有 $k$ 个 $1$，我们要将其分配到 $\lceil\frac{n}{2}\rceil$ 个 $1$ 和 $\lfloor\frac{n}{2}\rfloor$ 个 $-1$ 上，使得分配到的 $1$ 和 $-1$ 的和是 $3$ 的倍数。
如果 $k$ 是偶数，显然是可以的；否则我们会把 $k-3$ 个 $1$ 均匀分配，剩下的给 $1$（因为 $1$ 不会比 $-1$ 少）。
那么就是要有 $\frac{k+3}{2}\leq\lceil\frac{n}{2}\rceil$。综合一下可以得到：
- 如果 $0$ 的个数 $\geq 3$ 且 $1$ 的个数 $\geq 2$，那么存在满足条件的重排方式；
- 如果 $0$ 的个数为 $2$ 且 $k$ 为奇数，那么也存在满足条件的重排方式。
考虑不合法的情况，有
- 只有一个 $1$ 的区间；
- 出现了奇数个 $1$ 且 $0$ 的个数 $\leq 1$ 的区间。
为了不重复统计，给上面的加上限制条件：$0$ 的个数 $\geq 2$。
用线段树维护整个序列。对于每个节点，维护以下信息：
- $dl_{0/1,0/1}$ 表示包含 $0/1$ 个 $0$、$1$ 有奇数 / 偶数个的前缀数，$dr_{0/1,0/1}$ 类似；
- $fl_{0,1,2}$ 表示含有 $1$ 个 $1$、$0/1/\geq 2$ 个 $0$ 的前缀数，$fr_{0,1,2}$ 类似。
- $l_0$ 表示最长的前缀 $0$ 的数量，$r_0$ 同理。
- $s_0$ 表示 $0$ 的数量，$s_1$ 表示 $1$ 的数量。
- $s$ 表示不合法的子区间的数量。
根据上面的结论合并即可合并两个区间。
代码
// ====================================
// author: M_sea
// website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;
int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=100000+10;
int n,Q,a[N];
#define ls (o<<1)
#define rs (o<<1|1)
struct node {
ll dl[2][2],dr[2][2],fl[3],fr[3],s;
int l0,r0,s0,s1;
node() {
memset(dl,0,sizeof(dl)),memset(dr,0,sizeof(dr));
fl[0]=fl[1]=fl[2]=fr[0]=fr[1]=fr[2]=s=l0=r0=s0=s1=0;
}
node(int w) {
*this=node();
if (w) dl[0][1]=dr[0][1]=fl[0]=fr[0]=s=s1=1;
else dl[1][0]=dr[1][0]=l0=r0=s0=1;
}
} t[N<<2];
node operator +(node a,node b) {
node c;
for (int i=0;i<2;++i)
for (int j=0;j<2;++j) {
c.dl[i][j]+=a.dl[i][j],c.dr[i][j]+=b.dr[i][j];
if (i>=a.s0) c.dl[i][j]+=b.dl[i-a.s0][j^(a.s1&1)];
if (i>=b.s0) c.dr[i][j]+=a.dr[i-b.s0][j^(b.s1&1)];
}
for (int i=0;i<=2;++i) {
c.fl[i]+=a.fl[i],c.fr[i]+=b.fr[i];
if (!a.s1) c.fl[min(2,i+a.s0)]+=b.fl[i];
if (!b.s1) c.fr[min(2,i+b.s0)]+=a.fr[i];
}
if (a.s1==1&&b.l0) ++c.fl[min(2,a.s0+b.l0)],c.fl[2]+=b.l0-1;
if (b.s1==1&&a.r0) ++c.fr[min(2,b.s0+a.r0)],c.fr[2]+=a.r0-1;
c.l0=a.s1?a.l0:a.s0+b.l0,c.r0=b.s1?b.r0:b.s0+a.r0;
c.s0=a.s0+b.s0,c.s1=a.s1+b.s1;
c.s=a.s+b.s;
c.s+=a.dr[0][0]*(b.dl[0][1]+b.dl[1][1]);
c.s+=a.dr[0][1]*(b.dl[0][0]+b.dl[1][0]);
c.s+=a.dr[1][0]*b.dl[0][1];
c.s+=a.dr[1][1]*b.dl[0][0];
if (b.l0) c.s+=b.l0*(a.fr[0]+a.fr[1]+a.fr[2])-a.fr[0];
if (a.r0) c.s+=a.r0*(b.fl[0]+b.fl[1]+b.fl[2])-b.fl[0];
return c;
}
void pushup(int o) { t[o]=t[ls]+t[rs]; }
void build(int o,int l,int r) {
if (l==r) { t[o]=node(a[l]); return; }
int mid=(l+r)>>1;
build(ls,l,mid),build(rs,mid+1,r);
pushup(o);
}
void modify(int o,int l,int r,int p,int w) {
if (l==r) { t[o]=node(w); return; }
int mid=(l+r)>>1;
if (p<=mid) modify(ls,l,mid,p,w);
else modify(rs,mid+1,r,p,w);
pushup(o);
}
node query(int o,int l,int r,int ql,int qr) {
if (ql<=l&&r<=qr) return t[o];
int mid=(l+r)>>1;
if (qr<=mid) return query(ls,l,mid,ql,qr);
else if (ql>mid) return query(rs,mid+1,r,ql,qr);
else return query(ls,l,mid,ql,mid)+query(rs,mid+1,r,mid+1,qr);
}
#undef ls
#undef rs
int main() {
n=read();
for (int i=1;i<=n;++i) a[i]=read();
build(1,1,n);
Q=read();
while (Q--) {
int op=read();
if (op==1) {
int p=read(); a[p]^=1;
modify(1,1,n,p,a[p]);
} else {
int l=read(),r=read();
printf("%lld\n",1ll*(r-l+1)*(r-l+2)/2-query(1,1,n,l,r).s);
}
}
return 0;
}