D. Unique Median【Codeforces Round 997 (Div. 2)】

D. Unique Median

思路：

长度为奇数的一定是好数组，很容易相当找长度为偶数中的好数组数量，但是过于复杂。正向解决困难的情况下可以尝试反向思考，即找长度为偶数的非好数组数量，总答案就等于 n*(n+1)/2 - 非好数组数量。
每次枚举一个 $i$ 作为较大的那个中位数，那么这个数组不好的条件为 大于等于i的数的数量等于小于i的数的数量。如果将数组a中大于等于i的数记为1，小于i的数记为-1，得到一个新的数组b，那么不好的条件即为数组中 $\sum b[i]=0$
记b的前缀和为pre，那么区间$l-r$不好的条件为 $pre[r]=pre[l-1]$
详见代码

代码:

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define pb push_back
#define pii pair<int, int>
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
typedef long long ll;
using namespace std;

const int N = 500100;
int a[N], b[N], pre[N];

void solve(){
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    int sum = n * (n + 1) / 2;
    for (int i = 1; i <= 10; ++i){ // 遍历i，枚举中位数中较大的那个
        map<int, int> mp; // 记录前缀和出现次数
        for (int j = 1; j <= n; ++j)
            if (a[j] >= i)
                b[j] = 1;
            else
                b[j] = -1;
        for (int j = 1; j <= n; ++j)
            pre[j] = pre[j - 1] + b[j];
        int pos = 0;// 单向指针，一直向右走到j-1 
        for (int j = 1; j <= n; ++j)
        {
            if (a[j] == i)  //如果a[j]等于当前枚举的i时，这样能确保不重复统计
                while (pos < j)  //pos移动到j-1来，并统计pre出现次数，存在mp中
                    ++mp[pre[pos++]];
            sum -= mp[pre[j]];  //pre[j]在1到j-1的出现次数即mp[pre[j]] 为前面这一段的非好子数组数，从总ans中减去
        }
    }
    cout << sum << '\n';
}

signed main(){
    cin.tie(0)->ios::sync_with_stdio(0);
    int T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}