关于 ds 能力

松绒灼茁桌捉浊卓焯琢 · 2026-10-20 19:48:34 · 题解

好题，我懂得欣赏。

本题解提供了一个与主流做法完全不一样的做法，直接从最底层的状态出发推导，思考非常宏观，代码量比较大但并不繁琐且十分可读。

题意

我们定义斐波那契数列为

序列的前面若干项为 1,2,3,5,8,13,21,\ldots。

对一个正整数 p，定义 X(p) 为将 p 用若干个不同的斐波那契数的和表示的方案数，两个方案不同当且仅当有一个斐波那契数恰好只在其中一个方案中出现。

给定一个长度为 n 的正整数序列 a_1,a_2,\ldots,a_n，对于他的一个非空前缀 a_1,a_2,\ldots,a_k，我们定义 p_k=F_{a_1}+F_{a_2}+\cdots+F_{a_k}。

你的任务是对于所有 k=1, 2, \ldots, n，求出 X(p_k) 对 10^9+7 取模的值。

题解

单独求解 X(p_k)

斐波那契数表示

假设我们要求解 X(a) 的值，我们考虑将 a 表示成若干个斐波那契数的和，具体的，不妨定义非负整数序列 A_i 满足以下条件：

• \forall 1\le i: A_i \in \{0,1\},A_i+A_{i+1}\neq 2
• \sum_{i} A_i F_i=a

根据齐肯多夫定理（Zeckendorf's theorem）可以证明，这样的 A 序列是存在且唯一的。此处不赘述。

那么求解 X(p_k) 本质就是求解有多少个非负整数序列 B_i 满足以下条件：

• \forall 1\le i: B_i \in \{0,1\}
• \sum_{i} B_i F_i=a=\sum_{i} A_i F_i

动态规划

考虑令 dp_{i,j} 表示这样一个事情：

• 我们已经决策了 B 序列前 i-1 位的情况，目前，\displaystyle\sum_{k=1}^{i-1} (B_k - A_k) F_k=F_{j} 的情况下，后续的填写方案数。

这里，强制钦定其差一定为一个斐波那契数的依据如下：

• 如果当前的差是一个负数，根据上面的定理，后续无论怎么调整都无法恰好补上这单独的负值。
• 如果当前的差的表示不是单独的一个斐波那契数（注意 F_{i-2}+F_{i-1}=F_i），那么其进行分解之后必定含有 F_{i-2} 这一个因素，这个因素在后续的填写无论如何消除不了，所以这样钦定是合理且自洽的。

因此，我们也能够分析出 j 的有效取值集合为 \{0,i-1,i\}。

因为我们是从高位向低位（或者说从大到小）去匹配的，如果前面累积多出了一个超过 F_i 的差值（比如 F_{i+1}），那它永远也无法用 \le F_i 的项凑出来（因为 \sum_{k=1}^i F_k < F_{i+2}）。所以前缀差值只能是 0 或者刚好等于当前的 F_i 或 F_{i-1}。

可以得到 dp_{\infty,0}=1，在实际编写时，\infty 应该取 A 序列可能的最大非 0 位。

现在，我们考虑转移：

• 若 A_i=0：
  • 若 j=0：
    • 若当前决策 B_i=0，则 dp_{i,j} \leftarrow dp_{i+1,0}。
    • 若当前决策 B_i=1，由于 F_i=F_i，则 dp_{i,j} \leftarrow dp_{i+1,i}。
  • 若 j=i-1：
    • 若当前决策 B_i=0，对于下一位 i+1 而言，F_{i-1} 是一个无法消除的因素，故转移无效。
    • 若当前决策 B_i=1，由于 F_{i-1}+F_i=F_{i+1} 则 dp_{i,j} \leftarrow dp_{i+1,i+1}。
  • 若 j=i：
    • 若当前决策 B_i=0，由于 F_{i}=F_{i}，所以 dp_{i,j} \leftarrow dp_{i+1,i}。
    • 若当前决策 B_i=1，由于 2F_{i} 是一个无法被消除的元素，因为其最简表示是 F_{i+1}+F_{i-2}，第二项无法被消除，故转移无效。
• 若 A_i=1：
  • 若 j=0：
    • 若当前决策 B_i=0，则差值 -F_{i} 出现负数，转移无效。
    • 若当前决策 B_i=1，则 dp_{i,j} \leftarrow dp_{i+1,0}。
  • 若 j=i-1：
    • 若当前决策 B_i=0，则差值 F_{i-1}-F_{i} 出现负数，转移无效。
    • 若当前决策 B_i=1，由于 F_{i} + F_{i-1} - F_{i}=F_{i-1}，相对于 i+1 是一个无法被消除的元素，转移无效。
  • 若 j=i：
    • 若当前决策 B_i=0，则差值 F_i-F_i=0，有转移 dp_{i,j} \leftarrow dp_{i+1,0}
    • 若当前决策 B_i=1，则差值 F_i+F_i-F_i=F_i，有转移 dp_{i,j} \leftarrow dp_{i+1,i}

这样单次求解的时间复杂度为 O(V)。

矩阵乘法

令 dp'_{i,0}=dp_{i,0},dp'_{i,1}=dp_{i,i-1},dp'_{i,2}=dp_{i,i}，随后，将此转移写成矩阵形式：

而最后一个向量的样子是 $\begin{bmatrix} 1 \ 0 \ 0 \end{bmatrix}

• \forall 1\le i \le m: l_i\le r_i,l_i\equiv r_i\pmod 2
• \sum_{x}\left[\exists 1\le j \le m:x\in\left[l_j,r_j\right],x\equiv l_j \pmod 2\right]F_x = \sum_{x} A_x F_x

接下来，我们考虑不同更新情况下，这个连续段的变化。

情况一：A_i=A_{i+1}=A_{i-1}=0

这意味着 i 不在任何一个区间，直接更新即可。

情况二点一：A_{i-1}=1,A_i=0

注意到 F_{i-1}+F_{i}=F_{i+1}，所以清除 i-1 的状态然后在 i+1 更改即可。

情况二点二：A_{i-1}=0,A_i=0,A_{i+1}=1

此时可能会是这个样子：

设置 A_i=1：

进行更新之后：

其中 r 表示 i 所属连续段所对应的右端点。

因此，该操作会让 i 到 r 的元素全部清零，r+1 的元素设置为 1。

注意 r+3 可能会是 1，这可能会引发下一轮的连续段合并。

严格地说，对于任意 t\in\{0,1\},1\le l\le r 都有：

具体证明可以数学归纳法：

• 当 l=r 时，等式 F_{2l+t-1}+F_{2l+t}=F_{2r+t+1} 显然成立。
• 当有 F_{2l+t-1}+\displaystyle\sum_{i=l}^{r} F_{2i+t}=F_{2r+t+1} 时，由于有 F_{2l+t-1}=F_{2l+t-2}+F_{2l+t-3}，故有：

对应到连续段上的操作，就是先删除掉 (i+1,r) 全部的连续段，然后再在 r+1 放置一个 1，然后再考虑 r+1 是否可以拓展。

情况三：A_i=1

设置 A_i=2： | i-4 | i-3 | i-2 | i-1 | i | i+1 | i+2 | i+3 | i+4 | i+5 | | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: |:-: |:-:| | 1 | 0 | 1 | 0 | 2 | 0 | 1 | 0 | 1 | 0 |

将 2F_i 表示为 F_{i-2}+F_{i+1}：

将 2F_{i-2} 表示为 F_{i-4}+F_{i-1}：

因此有：

其中 l 表示 i 所属连续段所对应的左端点。

后面的元素就像第二种情况一样。

形式化的，对于所有 t\in\{0,1\}, 1\le l\le x \le r，都有：

该证明略。

对应到连续段上的操作，就是先删除掉 (i+2,r) 连续段，在 r+1 位放置一个 1，然后将 (l,i-2) 连续段右移一位（即原本在 x 的 1 变成了在 x+1 的 1），再在 l-2 位放一个 1。

同样注意在 l-2 位放 1 可能导致的级联更新，也注意在 r+1 位放 1 可能的级联更新。

而这里有一些边界情况：

• 若 l=1：注意到 2F_1=0+F_2，所以就是自动把在 l-2 放 1 的操作忽略即可。
• 若 l=2：注意到 2F_2=F_1+F_3，所以就是把 l-2 放 1 的操作改成在 l-1 放 1 的操作。

时间复杂度证明

注意到每一次操作可能的影响如下：

• 操作 1：增加至多一个连续段。
• 操作 2：删除若干个连续段。
• 操作 3：增加至多一个连续段，删除若干个连续段。

简单势能分析可得修改量复杂度是 O(n) 的。

数据结构细节

现在就是进入正题了，回顾上面的操作，我们要做的操作本质就是：

• 查询 1：单点查询 A_i；
• 查询 2：查询 i 所在连续段左/右端点（这需要保证 A_i=1）；
• 修改 1：将某一个区间 [l,r] 覆盖为 01010101\dots；
• 修改 2：将某一个区间 [l,r] 覆盖为 10101010\dots；
• 修改 3：将某一个区间 [l,r] 覆盖为 00000000\dots。

注意，连续段右移这个操作的本质无非就是把原本的连续段全部覆盖为 0，然后再用修改操作 1,2 更改，所以上面的逻辑可以刻画上一节的所有操作。

因此我们仍然考虑使用可持久化线段树维护整个数组。

我们发现查询 i 所在连续段左/右端点这个操作非常不好做，因此我们转换一下思路，去查询另一个东西（以查询右端点为例）：

• 查询首个满足以下条件的 j 的最小值：
  • A_j=0
  • j> i, j\equiv i \pmod 2

可以发现，查询出来这个 j 后，j-2 就会是连续段的右端点。

有了这个奇偶分离的条件，我们就可以考虑对于每一个线段树节点维护在该区间内，奇数位上 0 的个数和偶数位上 1 的个数，注意这里的奇数偶数是绝对的，这样后续的线段树二分操作才可能好写。

有了这个思路转化相信数据结构手子就能轻松做出来了，但我不是手子，所以我要继续讨论实现细节。

基础信息定义

为了尽可能少去分类讨论奇数偶数，我们考虑直接把线段树的操作范围限定为 [1,2^{30}]，这样线段树在建满后就是一个满二叉树，核心性质就是同深度的点同构，而且非叶子节点的 l,r 奇偶性是确定的（l 奇 r 偶），这样我们就只需要在叶子讨论奇偶即可。

struct Info {
    int ls, rs, sum[2], tag;
    Mat res;
};

• ls, rs 表示左右儿子编号。
• sum[0] 表示偶数下标 1 的个数，sum[1] 表示奇数下标 1 的个数，注意这里的奇数偶数是绝对的，不是相对于当前区间左端点的奇偶，在叶子节点讨论需要格外注意。
• tag 有以下几种：
  • 需要注意的是，tag 也是绝对的。下文中出现的 101010 等说法是指奇数位被该字符串第一个数覆盖，偶数同理。
• res 就是当前的答案。

打标记

inline void settag(int &i, int l, int r, int tag) {
  if (!i) i = ++tot;
  t[i].tag = tag;
  int len = r - l + 1;
  if (tag == 1) { // 0000 
    t[i].sum[0] = t[i].sum[1] = 0;
    t[i].res = get_z(len); // 这里 get_z 是指获取 000000…… 对应的矩阵
  } else if (tag == 2) { // 绝对的 101010
    if (l == r) {
      if (l & 1) { t[i].sum[1] = 1; t[i].sum[0] = 0; t[i].res = onet; } // l 奇数，每 1 覆盖
      else { t[i].sum[1] = 0; t[i].sum[0] = 0; t[i].res = zerot; } // 没有
    } else { // 若 l!=r 则 l 是奇数
      t[i].sum[1] = len / 2; t[i].sum[0] = 0; // 奇数位被 1 覆盖，偶数清零
      t[i].res = get_p1(len / 2); // 这里 get_p1 是指获取 10101010…… 对应的矩阵
    }
  } else if (tag == 3) { // 绝对的 010101
    if (l == r) {
      if (!(l & 1)) { t[i].sum[0] = 1; t[i].sum[1] = 0; t[i].res = onet; } // l 偶数，被 1 覆盖
      else { t[i].sum[0] = 0; t[i].sum[1] = 0; t[i].res = zerot; } // 没有
    } else {
      t[i].sum[0] = len / 2; t[i].sum[1] = 0; // 偶数位被 1 覆盖，奇数清零
      t[i].res = get_p0(len / 2); // 这里 get_p1 是指获取 01010101…… 对应的矩阵
    }
  }
}

在理解了上面的概念应该不难理解。

向下/向上更新

inline void push_up(int i, int l, int r) {
  int mid = (l + r) / 2;
  t[i].res = I;
  if (t[i].ls) t[i].res = t[t[i].ls].res;
  else t[i].res = get_z(mid - l + 1);
  if (t[i].rs) t[i].res = t[i].res * t[t[i].rs].res;
  else t[i].res = t[i].res * get_z(r - mid);
  t[i].sum[0] = (t[i].ls ? t[t[i].ls].sum[0] : 0) + (t[i].rs ? t[t[i].rs].sum[0] : 0);
  t[i].sum[1] = (t[i].ls ? t[t[i].ls].sum[1] : 0) + (t[i].rs ? t[t[i].rs].sum[1] : 0);
}

inline void push_down(int i, int l, int r) {
  if (t[i].tag) {
    int mid = (l + r) / 2;
    settag(t[i].ls, l, mid, t[i].tag);
    settag(t[i].rs, mid + 1, r, t[i].tag);
    t[i].tag = 0;
  }
}

注意在 push_down 中，由于我们的标记就是绝对的，所以不需要任何叶子奇偶讨论，这个操作在 settag 部分就已经帮我们完成了。

区间修改/单点查询

略。

找到区间的左右端点/找到第一个奇偶性不同的 0 位

最吃手法的一个。

假设我们要做查询右端点（即首个 j>p,j\equiv p\pmod2 且 A_j=0 的位置），并且目前我们要在 i 节点内（对应区间 l,r）找，那么我们的流程就大致如下：

• 边界检查：
  • 若 i 是空的：说明里面全都是 0，找到区间 [l,r] 第一个奇偶性与 p 相同的即可。
  • 若 l=r：则判断当前位是否是 0 且奇偶性是否和 p 一样，如果是则返回 l，否则返回未找到。
  • 若 [l,r] 的对应奇偶位全是 1：说明不可能找到。注意这个剪枝是必要的，否则复杂度会退化。
• 二分过程：
  • 由于我们只找右边的第一个 0，所以先令 t 表示在左子树寻找的结果。
    • 若返回未找到，则说明左边是全满或空的状态，得去右边找。
    • 若返回找到了，那么就返回 t。

这个二分过程就说明了为什么要这个剪枝，如果不加那就是整个子树遍历一遍了。

注意时间复杂度是 O(\log V) 的，因为二分过程的 Case1 我们只会遇到一次，遇到之后再遇到全满就会被上面那个剪枝消除了。

int next_zero(int i, int l, int r, int pos) {
  if (r <= pos) return -1;
  int par = pos & 1;
  if (!i) {
    int L = max(l, pos + 1);
    int ans = (L & 1) == par ? L : L + 1;
    return ans <= r ? ans : -1;
  }
  if (l == r) {
    return ((l & 1) == par && !t[i].sum[par]) ? l : -1;
  }
  if (t[i].sum[par] == (r - l + 1) / 2) return -1;
  push_down(i, l, r);
  int mid = (l + r) / 2;
  int res = next_zero(t[i].ls, l, mid, pos);
  return res != -1 ? res : next_zero(t[i].rs, mid + 1, r, pos);
}

找上一个同理。

int prev_zero(int i, int l, int r, int pos) {
  if (l >= pos) return -1;
  int par = pos & 1;
  if (!i) {
    int R = min(r, pos - 1);
    int ans = (R & 1) == par ? R : R - 1;
    return ans >= l ? ans : -1;
  }
  if (l == r) {
    return ((l & 1) == par && !t[i].sum[par]) ? l : -1;
  }
  if (t[i].sum[par] == (r - l + 1) / 2) return -1;
  push_down(i, l, r);
  int mid = (l + r) / 2;
  int res = prev_zero(t[i].rs, mid + 1, r, pos);
  return res != -1 ? res : prev_zero(t[i].ls, l, mid, pos);
}

复杂度

• 时间复杂度：线段树的任何操作就是 O(\log V) 的，一共操作 O(n) 次，所以是 O(n \log V) 的。
• 空间复杂度：每次操作至多新建 O(\log V) 个节点，所以空间复杂度 O(n \log V)。

可能有人好奇矩阵快速幂的复杂度，不过注意我们的区间长度一定是 2 的幂次，所以可以认为矩阵快速幂复杂度就是 O(1) 的。

代码

把以上所有代码超级拼装就是最终的代码了，最终代码对 A 序列更新的模拟有一定注解。

:::info[6.97K]

#include <bits/stdc++.h>
using namespace std;
#define int long long
bool st;
const int V = 1<<30;
const unsigned p = 1e9 +7;
int n, a[102005], xg, upt = 0, rt;

struct Mat {
    unsigned mat[3][3];
    inline Mat operator * (const Mat &m) const {
        Mat res = {};
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (!mat[i][j]) continue;
                for (int k = 0; k < 3; ++k) {
                    res.mat[i][k] += 1ull * mat[i][j] * m.mat[j][k] % p;
                }
            }
        }
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                res.mat[i][j] %= p;
            }
        }
        return res;
    }
};
const Mat onet = {{
    {1, 0, 0},
    {0, 0, 0},
    {1, 1, 0}
}};
const Mat zerot = {{
    {1, 1, 0},
    {0, 0, 1},
    {0, 1, 0}
}};
const Mat I = {{
    {1, 0, 0},
    {0, 1, 0},
    {0, 0, 1}
}};
const Mat OO = {{
    {0, 0, 0},
    {0, 0, 0},
    {0, 0, 0}
}};
Mat bst[32], b1p[32], b0p[32];
// b0p 是 0101010101 的转移
// b1p 是 1010101010 的转移

Mat get_z(int len) {
    if (len == 0) return I;
    assert((len & (len - 1)) == 0);
    return bst[__lg(len)];
}
Mat get_p0(int len) {
    if (len == 0) return I;
    assert((len & (len - 1)) == 0);
    return b0p[__lg(len)];
}
Mat get_p1(int len) {
    if (len == 0) return I;
    assert((len & (len - 1)) == 0);
    return b1p[__lg(len)];
}
namespace SGT {
    struct Info {
        int ls, rs;
        unsigned sum[2], tag;
        Mat res;
    } t[100005 * 34];
    int tot = 0;

    inline void settag(int &i, int l, int r, int tag) {
        if (!i) i = ++tot;
        t[i].tag = tag;
        int len = r - l + 1;
        if (tag == 1) { // 0000 
            t[i].sum[0] = t[i].sum[1] = 0;
            t[i].res = get_z(len);
        } else if (tag == 2) { // 绝对的 101010，若 l!=r 则 l 是奇数
            if (l == r) {
                if (l & 1) { t[i].sum[1] = 1; t[i].sum[0] = 0; t[i].res = onet; }
                else { t[i].sum[1] = 0; t[i].sum[0] = 0; t[i].res = zerot; }
            } else {
                t[i].sum[1] = len / 2; t[i].sum[0] = 0;
                t[i].res = get_p1(len / 2); 
            }
        } else if (tag == 3) { 
            if (l == r) {
                if (!(l & 1)) { t[i].sum[0] = 1; t[i].sum[1] = 0; t[i].res = onet; }
                else { t[i].sum[0] = 0; t[i].sum[1] = 0; t[i].res = zerot; }
            } else {
                t[i].sum[0] = len / 2; t[i].sum[1] = 0;
                t[i].res = get_p0(len / 2);
            }
        }
    }

    inline void push_up(int i, int l, int r) {
        int mid = (l + r) / 2;
        t[i].res = I;
        if (t[i].ls) t[i].res = t[t[i].ls].res;
        else t[i].res = get_z(mid - l + 1);
        if (t[i].rs) t[i].res = t[i].res * t[t[i].rs].res;
        else t[i].res = t[i].res * get_z(r - mid);
        t[i].sum[0] = (t[i].ls ? t[t[i].ls].sum[0] : 0) + (t[i].rs ? t[t[i].rs].sum[0] : 0);
        t[i].sum[1] = (t[i].ls ? t[t[i].ls].sum[1] : 0) + (t[i].rs ? t[t[i].rs].sum[1] : 0);
    }

    inline void push_down(int i, int l, int r) {
        if (t[i].tag) {
            int mid = (l + r) / 2;
            settag(t[i].ls, l, mid, t[i].tag);
            settag(t[i].rs, mid + 1, r, t[i].tag);
            t[i].tag = 0;
        }
    }
    inline void update(int &i, int l, int r, int ql, int qr, int tag) {
        if (l > qr || r < ql) return;
        if (!i) i = ++tot;
        if (l >= ql && r <= qr) return settag(i, l, r, tag);
        push_down(i, l, r);
        int mid = (l + r) / 2;
        update(t[i].ls, l, mid, ql, qr, tag);
        update(t[i].rs, mid + 1, r, ql, qr, tag);
        push_up(i, l, r);
    }
    int query_bit(int i, int l, int r, int qp) {
        if (l > qp || r < qp || !i || !(t[i].sum[0] + t[i].sum[1])) return 0;
        if (l == r) return t[i].sum[0] + t[i].sum[1];
        push_down(i, l, r);
        int mid = (l + r) / 2;
        return query_bit(t[i].ls, l, mid, qp) + query_bit(t[i].rs, mid + 1, r, qp);
    }
    inline int full(int l, int r, int p) {
        return (l == r) ? ((l & 1) == p) : (r - l + 1) / 2;
    }
    int prev_zero(int i, int l, int r, int pos) {
        if (l >= pos) return -1;
        int par = pos & 1;
        if (!i) {
            int R = min(r, pos - 1);
            int ans = (R & 1) == par ? R : R - 1;
            return ans >= l ? ans : -1;
        }
        if (l == r) {
            return ((l & 1) == par && !t[i].sum[par]) ? l : -1;
        }
        if (r < pos && t[i].sum[par] == (r - l + 1) / 2) return -1;
        push_down(i, l, r);
        int mid = (l + r) / 2;
        int res = prev_zero(t[i].rs, mid + 1, r, pos);
        return res != -1 ? res : prev_zero(t[i].ls, l, mid, pos);
    }
    int next_zero(int i, int l, int r, int pos) {
        if (r <= pos) return -1;
        int par = pos & 1;
        if (!i) {
            int L = max(l, pos + 1);
            int ans = (L & 1) == par ? L : L + 1;
            return ans <= r ? ans : -1;
        }
        if (l == r) {
            return ((l & 1) == par && !t[i].sum[par]) ? l : -1;
        }
        if (l > pos && t[i].sum[par] == (r - l + 1) / 2) return -1;
        push_down(i, l, r);
        int mid = (l + r) / 2;
        int res = next_zero(t[i].ls, l, mid, pos);
        return res != -1 ? res : next_zero(t[i].rs, mid + 1, r, pos);
    }
}
void update_pos(int pos) {
    if (pos <= 0) return;
    int p = pos & 1;
    if (SGT::query_bit(rt, 1, V, pos) == 1) { // 当前位置是一个 1
        int bad_l = SGT::prev_zero(rt, 1, V, pos);
        int z = (bad_l == -1) ? (p ? 1 : 2) : (bad_l + 2); // 找左端点
        int bad_r = SGT::next_zero(rt, 1, V, pos);
        int y = (bad_r == -1) ? (V - ((V & 1) != p)) : (bad_r - 2); // 找右端点
        SGT::update(rt, 1, V, z, y, 1); // 先把整个连续段清空
        if (z + 1 <= pos - 1) { // 对于左边那个连续段，101010 覆盖，就相当于右移了
            SGT::update(rt, 1, V, z + 1, pos - 1, ((z + 1) & 1) ? 2 : 3);
        }
        // 左边多出来的一个 1 还要更新
        if (z == 1) { 
        } else if (z == 2) {
            SGT::update(rt, 1, V, 1, 1, 1 % 2 ? 2 : 3);
        } else if (z > 2) {
            int e = z - 2;
            if (SGT::query_bit(rt, 1, V, e - 1) == 1) { // z-2 的更新可能会导致和 z-3 合并
                SGT::update(rt, 1, V, e - 1, e - 1, 1);
                SGT::update(rt, 1, V, e + 1, e + 1, (e + 1) % 2 ? 2 : 3);
            } else {
                SGT::update(rt, 1, V, e, e, e % 2 ? 2 : 3);
            }
        }
        update_pos(y + 1); // y+1 位要加一
    } else { // 当前位置是一个 0
        if (SGT::query_bit(rt, 1, V, pos - 1) == 1) { // 和 pos - 1 的 1 合并
            SGT::update(rt, 1, V, pos - 1, pos - 1, 1);
            update_pos(pos + 1); // F_{pos-1} + F_{pos} = F_{pos+1}
        } else if (SGT::query_bit(rt, 1, V, pos + 1) == 1) { // 和 pos + 1 的一坨连续段更新
            int nxt_p = (pos + 1) & 1;
            int bad_r = SGT::next_zero(rt, 1, V, pos + 1);
            int y = (bad_r == -1 ? (V - ((V & 1) != nxt_p)) : (bad_r - 2));
            SGT::update(rt, 1, V, pos + 1, y, 1); // 连续段变成 0
            update_pos(y + 1); // y+1 更新一位
        } else {
            SGT::update(rt, 1, V, pos, pos, pos % 2 ? 2 : 3); // 正常更新
        }
    }
}
bool ed;
signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    bst[0] = zerot;
    b0p[0] = zerot * onet;
    b1p[0] = onet * zerot;
    for (int i = 1; i <= 31; ++i) {
        bst[i] = bst[i - 1] * bst[i - 1];
        b0p[i] = b0p[i - 1] * b0p[i - 1];
        b1p[i] = b1p[i - 1] * b1p[i - 1];
    }
    for (int i = 1; i <= 31; ++i) {
    }
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        update_pos(a[i]);
        cout << SGT::t[rt].res.mat[0][0] << "\n";
    }
}

:::

AI 使用说明：感谢 Gemini 3 为我提供精神支持和技术支持并提供了部分代码实现。