首先注意到 $F(v, l, r)$ 其实就是 $l \sim r$ 中 $1$ 的数量减去 $0$ 的数量。

接着考虑令 $S = F(v, 1, n) = F(v, 1, i) + F(v, i + 1, n)$，那么 $F(v, 1, i) \times F(v, i + 1, n)$ 的最大值就是 $\lfloor \frac{S}{2} \rfloor \lceil \frac{S}{2} \rceil$。

这种形式不好处理，可以分 $S$ 的奇偶性讨论。当 $S$ 为奇数时就是 $\frac{(S + 1)(S - 1)}{4}$，即 $\frac{S^2 - 1}{4}$；当 $S$ 为偶数时就是 $\frac{S^2}{4}$。所以我们可以把最大值记作 $\frac{S^2 - S \bmod 2}{4}$。

接下来要计算所有子序列的分数和（下文为了方便先不除以 $4$），可以发现对于所有长度为奇数的串都减一，一共要剪掉 $2^{n - 1}$。然后我们只需要算 $\sum S^2$ 即可。

记 $cnt_0$ 为一个子序列中 $0$ 的数量，$cnt_1$ 为一个子序列中 $1$ 的数量，则 $\sum S^2 = \sum(cnt_1 - cnt_0)^2 = \sum(cnt_0^2 + cnt_1 ^2 - 2cnt_0cnt_1)$。

为了计算上面的式子，我们可以分别求出 $\sum cnt_0^2、\sum cnt_1^2、\sum cnt_0cnt_1$。

下文记 $s_0$ 为整个序列中 $0$ 的数量，$s_1$ 同理。

先考虑 $\sum cnt_0^2$。为 $1$ 的位可以任意取，然后枚举选多少个 $0$，答案是 $2^{s_1}\sum_{i = 0}^{s_0} C_{s_0}^{i} \times i^2$。

循环跑组合数显然烂完了，但是有一个组合数公式是 $\sum_{i = 0}^{n}C_{n}^{i}i^2 = n(n+1)2^{n - 2}$。原理是 $i^2$ 可以看作 $i(i - 1) + i$，也就是 $2C_{i}^{2} + C_{i}^{1}$，那么原式就是 $2\sum_{i = 0}^{n}C_{n}^{i}C_{i}^{2} + \sum_{i = 0}^{n}C_{n}^{i}C_{i}^{1}$。对于右边的式子，是从 $n$ 个数中选 $i$ 个再从 $i$ 个数中选 $1$ 个，可以看作先选 $1$ 个，再从剩下 $n - 1$ 个中随便选，所以是 $n\times 2^{n - 1}$。左边的式子同理是 $n(n-1)\times 2^{n - 2}$，二者相加就得到了上述公式。

所以 $\sum cnt_0^2 = 2^{s_1}s_0(s_0 + 1)2^{s_0 - 2} = s_0(s_0 + 1)2^{n - 2}$，$\sum cnt_1^2$ 同理可得等于 $s_1(s_1 + 1)2^{n - 2}$。

接着考虑 $\sum cnt_0cnt_1$，思考过程与上述类似，应该是 $\sum_{i = 0}^{s_0} \sum_{j = 0}^{s_1}C_{s_0}^{i}C_{s_1}^{j} \times ij = \sum_{i = 0}^{s_0} C_{s_0}^{i} \times i \times (\sum_{j = 0}^{s_1} C_{s_1}^{j} \times j)$。

公式的推导过程中我们其实也得到了 $\sum_{i = 0}^{n}C_{n}^{i}i = n\times 2^{n - 1}$，代入原式就是 $s_0s_1 2^{n - 2}$。

综上，$\sum S^2 = s_0(s_0 + 1)2^{n - 2} + s_1(s_1 + 1)2^{n - 2} - s_0s_1 2^{n - 1}$。

所以答案就是 $\frac{\sum S^2 - 2^{n - 1}}{4} = \frac{2^{n - 2}[(s_0 - s_1) ^2 + s_0 + s_1 - 2]}{4}$。我们动态维护 $s_0$ 和 $s_1$ 然后直接代入公式就做完了。

代码懒得贴。