解析

注意到 \(a_i\) 很小，那就不妨讓它更小一點，從最簡單的情況出發。

當 \(1 \le a_i \le 1\) 時，顯然所有子數組都是”好數組“。

當 \(1 \le a_i \le 2\) 時，如果一個子數組中 \(1\) 的個數與 \(2\) 的個數不同，那么它是“好數組”，否則它不是“好數組”。

感覺個數相同的情況會更少，并且似乎會更好求，那就求它！

問題就變成找滿足區間內 \(1\) 和 \(2\) 個數相等的區間個數。

對于區間問題，有一種常見的做法——把它轉化成前綴的問題。設 \(f(x)\) 表示 \(a[1,x]\) 中，\(1\) 的出現次數比 \(2\) 多多少次，那么如果有 \(y < x\) 滿足 \(f(y) = f(x)\)，那么 \(a[y + 1,x]\) 就不是一個 "好數組"，因為把長度為 \(y\) 的前綴去掉就相當于去掉了這一部分的貢獻，剩下這一部分 \(1\) 的個數就和 \(2\) 的個數相等了。

嘗試將這種做法推廣到 \(1 \le a_i \le 10\) 的情況，如果子數組內 \(\le x\) 的元素個數等于 \(> x\) 的元素個數，且子數組內有元素 \(x\)，則該子數組不是一個“好數組”，詳見代碼。

代碼

/*
cnt[i][j] 表示前 i 個元素， 1 ~ j 的個數比 j + 1 ~ 10 的多多少個
不合法的個數就是滿足 cnt[i][j] - cnt[k][j] = 0 (k < i)的個數
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 5;
typedef pair<int,int> pii;
typedef long long ll;
int a[N];
int cnt[N][15],num[N],last[N];//num[i] 表示當前 1 ~ i 的元素個數，last[i] 表示元素 i 最后出現的位置
map<pii,vector<int> > m;//m[i][j] 存儲的是 <= i 的元素個數比 > i 的元素個數多 j 個的前綴位置
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int T;
	cin>>T;
	while(T--){
		m.clear();
		for(int i=1;i<=9;i++){
			m[{i,0}].push_back(0);
			num[i] = 0;
			last[i] = 0;
		}
		int n;
		cin>>n;
		ll res = 1ll * n * (n + 1) / 2;//總子數組個數
		for(int i=1;i<=n;i++){
			cin>>a[i];
			last[a[i]] = i;
			for(int j=a[i];j<=9;j++){
				num[j]++;
			}
			for(int j=1;j<=9;j++){
				cnt[i][j] = num[j] - (i - num[j]);
				if(last[j] && m.count({j,cnt[i][j]})){
					int pos = lower_bound(m[{j,cnt[i][j]}].begin(),m[{j,cnt[i][j]}].end(),last[j]) - m[{j,cnt[i][j]}].begin();
          //需要保證剔除前綴后的區間內確實有 j 這個元素，所以要求 < last[j] 的位置個數
					res -= pos;
				}
			}
			for(int j=1;j<=9;j++){
				m[{j,cnt[i][j]}].push_back(i);
			}
		}
		cout<<res<<'\n';
	}
	return 0;
}