rt，这个在我们模拟赛里面。我场上做法是这样的：

转化为对所有 $(i,j)$ 的数量，满足在他的同一连通块中不存在 $(i',j')$ 使得 $j'>j$ 或者 $j'=j$ 且 $i'>i$。分别统计。

感觉情况分的很全了，但是 WA 一半，求 hack /kel

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e6 + 10;

int T, n, a[MAXN], c1[MAXN], c0[MAXN], p1[MAXN], p0[MAXN];

int pa, pb, pc; ll ans;

int main() {
	for (scanf("%d", &T); T--; ) {
		scanf("%d", &n), ans = 0, pa = pb = pc = n + 1;
		for (int i = 1; i <= n; i++) scanf("%d", &a[i]), p0[i] = p1[i] = n + 1;
		for (int i = 1, j = 0; i <= n; i++) {
			c1[i] = c1[i - 1], c0[i] = c0[i - 1];
			(a[i] ? p1 : p0)[++(a[i] ? c1[i] : c0[i])] = i;
		}
		for (int i = n; i; i--) {
			if (a[i]) pa = i;
			if (a[i] && c0[i]) pb = i;
			if (a[i] && c0[i] > 1) pc = i;
		}
		for (int i = 1, j = 0, k = 0; i <= n; i++) {
			ans += i - 1;
			if (a[i]) {
				/*1 1*/
				// nah
				/*0 1*/
			//	puts("0 1");
				if (c0[i] != c0[n]) ans -= c0[i]/*, printf("%d:%lld\n", i, c0[i])*/;
				else if (c1[i] != c1[n]) {
					if (c0[i]) ans -= c0[i] - 1/*, printf("%d:%lld\n", i, c0[i] - 1)*/;
				} else if (p1[1] < i) {
					if (c0[p1[1]] != c0[i]) ans -= c0[i] - c0[p1[1]] - 1/*, printf("%d:%lld\n", i, c0[i] - c0[p1[1]] - 1)*/;
					if (p1[1] > 2 && c0[i] - c0[p1[1]] >= 2) ans -= c0[p1[1]] - 1/*, printf("%d:%lld\n", i, c0[p1[1]] - 1)*/;
				} 
				k = i;
			} else {
				/*1 0*/
			//	puts("1 0");
				if (c0[i] != c0[n]) ans -= c1[i]/*, printf("%d:%d\n", i, c1[i])*/;
				else {
					if (c1[i] != c1[n]) {
						if (p0[2] <= j) ans -= c1[p0[2]] - c1[p0[1]]/*, printf("%d:%d\n", i, c1[p0[2]] - c1[p0[1]])*/;
						if (p0[2] < i) ans -= c1[i] - c1[p0[2]]/*, printf("%d:%d\n", i, c1[i] - c1[p0[2]])*/;
					} else {
						if (p0[1] < j) ans -= c1[j] - c1[p0[1]]/*, printf("%d:%d\n", i, c1[j] - c1[p0[1]])*/;
						if (p0[2] <= j) ans -= c1[i] - c1[j] - 1/*, printf("%d:%d\n", i, c1[i] - c1[j] - 1)*/;
					}
				}
				/*0 0*/
			//	puts("0 0");
				if (c1[i] != c1[n]) ans -= c0[i - 1]/*, printf("%d:%d\n", i, c0[i - 1])*/;
				else if (c0[i] != c0[n]) {
					if (p1[1] < i) ans -= c0[i - 1] - c0[p1[1]]/*, printf("%d:%d\n", i, c0[i - 1] - c0[p1[1]])*/;
				}  else {
					if (pa < pb && pb <= k) ans -= c0[pb] - c0[pa] - 1/*, printf("%d:%d\n", i, c0[pb] - c0[pa] - 1)*/;
					if (pb < pc && pb < j) ans -= c0[min(pc, j)] - c0[pb] - 1/*, printf("%d:%d\n", i, c0[min(pc, j)] - c0[pb] - 1)*/;
					if (pc < i) ans -= c0[i] - c0[pc] - 1/*, printf("%d:%d\n", i, c0[i] - c0[pc] - 1)*/;
				}
				j = i;
			}
		}
		printf("%lld\n", ans);
	}
}