题解

结论与判定

• 对一个只含 0/1 的串，若它可以任意重排后组成 3 的倍数，则只与 1 的个数、长度以及重排后偶数位能摆入的 1 数量有关。把长度设为 L，1 的数量为 cnt1。我们可把 x 个 1 放在偶数位，其余放在奇数位，得到的值模 3 即 2x - cnt1。因此只要存在整数
  lo ≤ x ≤ hi 且 x ≡ (-cnt1) (mod 3)，就能重排成功，其中
  lo = max(0, cnt1 - ⌊L/2⌋)，hi = min(cnt1, ⌈L/2⌉)。
• 推导可得：除了以下三种特殊情况外，总能找到满足的 x。因此一个区间是“不可行”当且仅当满足：
  1. cnt1 = 1（只有一位是 1）；
  2. 全部都是 1 且长度为奇数（此时 lo = hi = (L+1)/2，但 2x - cnt1 ≡ 1)；
  3. 仅有一个 0 且长度为偶数（对偶数长度，唯一可行的 x 与模 3 要求不符）。
• 设区间 [l,r] 中共有 tot = (len)*(len+1)/2 个子区间。我们只需求出三类“不可行”子区间的数量 bad，答案即 tot - bad。

数据结构设计

• 在线进行修改与查询，可用线段树维护区间信息。每个结点需要存储：
  • 区间长度 len、零的数量 cnt0；
  • 最长前缀/后缀的连续 0 长度、连续 1 长度；
  • 以区间左端或右端为界，且长度为偶/奇的全 1 段数目（用于处理“全 1 且奇长”）；
  • 以区间左/右端为界，仅包含一个 0 的段数目（用于处理“仅一个 0 且偶长”）；
  • 当前区间内的“不可行”子区间数量 bad。
• 合并两个结点时：
  1. 直接把左右区间的 bad 值相加；
  2. 统计跨越分界的“仅一个 1”子区间：它们的结构必为“连续 0 + 单个 1 + 连续 0”，一部分来自左区间的后缀 0、另一部分来自右区间的前缀 0，再考虑单个 1 位于哪一侧；
  3. 统计跨界的“仅一个 0 且偶长”/“全 1 且奇长”两类区间，对应地需要保留前缀/后缀的奇偶信息；
  4. 维护新结点的前缀/后缀信息，方便上层继续合并。
• 单点翻转时在线更新叶子即可，查询时返回整个区间对应的结点信息并利用公式求答案。

复杂度

• 每次合并与统计都在常数时间内完成，修改与查询的时间复杂度为 O(log n)，满足 n,m ≤ 10^5 的限制。

参考实现

#define db(x...)
#define dba(x...)

#include <iostream>
#include <cstdio>
#define ls x << 1
#define rs x << 1 | 1
using namespace std;
const int maxn = 1e5 + 50, maxm = maxn << 2;
int n, q, x, y, a[maxn];
struct node {
    int s0, len, l_, r_, l0, r0, l1, r1, l00, l01, r00, r01;
    long long s;
} t[maxm];
inline int read() {
    int x = 0;
    char c = getchar();

    while (c < '0' || c > '9')
        c = getchar();

    while (c >= '0' && c <= '9')
        x = x * 10 + (c ^ 48), c = getchar();

    return x;
}
inline node merge(node p, node q) {
    db(p.l0 * q.r_ + q.r0 * p.l_ - (p.l0 * q.r1 || p.l1 * q.r0));
    return {
        p.s0 + q.s0,
        p.len + q.len,
        q.s0 == q.len ? p.l_ : (q.s0 == q.len - 1 ? q.l_ + p.l0 : q.l_),
        p.s0 == p.len ? q.r_ : (p.s0 == p.len - 1 ? p.r_ + q.r0 : p.r_),
        q.l0 + (q.s0 == q.len) *p.l0,
        p.r0 + (p.s0 == p.len) *q.r0,
        q.l1 + (!q.s0) *p.l1,
        p.r1 + (!p.s0) *q.r1,
        q.s0 ? (q.s0 > 1 ? q.l00 : q.l00 + (p.l1 + ((q.len - 1) % 2)) / 2) : (q.len % 2 ? p.l01 : p.l00),
        q.s0 ? (q.s0 > 1 ? q.l01 : q.l01 + (p.l1 + (q.len % 2)) / 2) : (q.len % 2 ? p.l00 : p.l01),
        p.s0 ? (p.s0 > 1 ? p.r00 : p.r00 + (q.r1 + ((p.len - 1) % 2)) / 2) : (p.len % 2 ? q.r01 : q.r00),
        p.s0 ? (p.s0 > 1 ? p.r01 : p.r01 + (q.r1 + (p.len % 2)) / 2) : (p.len % 2 ? q.r00 : q.r01),
        p.s + q.s + p.l0 *q.r_ + q.r0 *p.l_ - (p.l0 * q.r1 || p.l1 * q.r0) + 1ll * (p.l1 / 2 + p.l00) *((q.r1 + 1) / 2 + q.r01) - 1ll * p.l00 *q.r01 + 1ll * ((p.l1 + 1) / 2 + p.l01) *(q.r1 / 2 + q.r00) - 1ll * p.l01 *q.r00
    };
}
inline void init(int x = 1, int l = 1, int r = n) {
    if (l == r) {
        a[l] = read();
        t[x] = {!a[l], 1, a[l], a[l], !a[l], !a[l], a[l], a[l], !a[l], 0, !a[l], 0, a[l]};
        return;
    }

    int mid = (l + r) >> 1;
    init(ls, l, mid);
    init(rs, mid + 1, r);
    t[x] = merge(t[ls], t[rs]);
    db(x, l, r, t[x].s, t[x].s0, t[x].len, t[x].l1, t[x].r1, t[x].l00, t[x].l01, t[x].r00, t[x].r01);
}
inline void modify(int p, int x = 1, int l = 1, int r = n) {
    if (l == r) {
        a[l] ^= 1;
        t[x] = {!a[l], 1, a[l], a[l], !a[l], !a[l], a[l], a[l], !a[l], 0, !a[l], 0, a[l]};
        return;
    }

    int mid = (l + r) >> 1;

    if (p <= mid)
        modify(p, ls, l, mid);
    else
        modify(p, rs, mid + 1, r);

    t[x] = merge(t[ls], t[rs]);
    // db(x,l,r,t[x].s,t[x].s0,t[x].len,t[x].l1,t[x].r1,t[x].l00,t[x].l01,t[x].r00,t[x].r01);
}
inline node query(int L, int R, int x = 1, int l = 1, int r = n) {
    if (L <= l && R >= r)
        return t[x];

    int mid = (l + r) >> 1;

    if (L > mid)
        return query(L, R, rs, mid + 1, r);

    if (R <= mid)
        return query(L, R, ls, l, mid);

    node tmp = merge(query(L, R, ls, l, mid), query(L, R, rs, mid + 1, r));
    db(x, l, r, tmp.s, tmp.s0, tmp.len, tmp.l1, tmp.r1, tmp.l00, tmp.l01, tmp.r00, tmp.r01);
    return tmp;
}
int main() {
    n = read();
    init();
    q = read();

    while (q --) {
        if (read() == 1) {
            x = read();
            modify(x);
        } else {
            x = read(), y = read();
            printf("%lld\n", 1ll * (y - x + 1) * (y - x + 2) / 2 - query(x, y).s);
        }
    }

    return 0;
}