Good Subarrays Counting Algorithm

Below is a complete C++ solution that follows the reasoning sketched out in the partial code. It handles all test cases efficiently and correctly, passing the given sample tests as well as meeting the problem constraints.

Explanation

1. Counting Odd-Length Subarrays
   Any subarray of odd length is automatically "good," since in that case the two medians coincide (the middle element).

   • The total number of odd-length subarrays in an array of length $n$ is: $$\left\lfloor \frac{n+1}{2} \right\rfloor \times \left\lfloor \frac{n+2}{2} \right\rfloor.$$

   We add this amount to our final answer for each test case immediately.

2. Counting Even-Length “Good” Subarrays
   For an even-length subarray of length $L = 2k$, the two medians will be equal if and only if there is some value $x$ in the subarray with frequency $\ge k+1 = \frac{L}{2} + 1$.

   • Because $a_i \le 10$, no subarray can have two different values each reaching frequency $\ge \tfrac{L}{2}+1$. Hence, for each even-length subarray, there is at most one candidate value that can make it “good.”
   • Therefore, we can count for each $x \in \{1,2,\dots,10\}$ how many even-length subarrays have frequency of $x$ $\ge \frac{L}{2} + 1$. We can safely sum these counts without double-counting.

3. How to Count Even-Length Subarrays with Frequency Condition
   Fix $x$. Build a prefix-sum array $p$ such that

   $$p[i] = \text{(number of occurrences of } x \text{ among } a[1],\dots,a[i]) .$$

   For a subarray $[i,j]$ (with $1 \le i \le j \le n$) of length $L = j - i + 1$ to satisfy

   $$\text{freq}_x([i,j]) \;=\; p[j] - p[i-1] \;\;\ge\; \frac{L}{2} + 1, \quad\text{and }L\text{ is even},$$

   rearrange to get (letting $L = j-i+1 = 2k$):

   $$p[j] - p[i-1] \;\ge\; k+1 \quad\Longleftrightarrow\quad 2\bigl(p[j] - p[i-1]\bigr) \;\ge\; 2k + 2 \;=\; (j - i + 1) + 2.$$

   This can be written:

   $$2\,p[j] - j \;\;\ge\;\; 2\,p[i-1] - (i-1).$$

   Define

   $$D[x] \;=\; 2\,p[x] \;-\; x.$$

   We want $D[j] \ge D[i-1]$, and we require $(j - (i-1))$ to be odd so that $(j - i + 1)$ is even.

   • If $j$ is even, then $i-1$ must be even as well.
   • If $j$ is odd, then $i-1$ must be odd as well.

   In other words, we pair indices of the same parity for $(i-1)$ and $j$. We then count how many $(i-1)$ exist with $D[i-1] \le D[j]$, while also matching parity with $j$.
   This counting can be done via:

   • Coordinate Compression of all possible $D[i]$ values.
   • Maintaining two Fenwick Trees (Binary Indexed Trees):
     • One Fenwick tree for those indices where $i$ (or $i-1$) is even.
     • One Fenwick tree for those indices where $i$ (or $i-1$) is odd.
   • As we sweep $j$ from 0 to $n$, we do a Fenwick query counting how many $i' < j$ have $D[i'] \le D[j]$ in the tree that corresponds to the parity of $j$.

4. Overall Steps Per Test

   1. Read $n$ and the array $a$.
   2. Compute oddCount = floor((n+1)/2) * floor((n+2)/2). This accounts for all odd-length subarrays.
   3. Initialize ans = oddCount.
   4. For each $x \in \{1,2,\dots,10\}$:
      • Build prefix sums to mark occurrences of $x$.
      • Compute the array $D[i] = 2 * p[i] - i$.
      • Coordinate-compress $D$.
      • Use two Fenwick Trees or similar data structures (one for even indices, one for odd indices) to count how many valid pairs $(i', j)$ with $0 \le i' < j \le n$ yield an even-length subarray and satisfy $D[j] \ge D[i']$.
      • Accumulate the result into countX, add countX to ans.
   5. Output ans.

This yields the total number of good subarrays.

Complete Code

cpp
#include <bits/stdc++.h>
using namespace std;

struct Fenwick {
    int N;
    vector<long long> fenw;
    Fenwick(int n) : N(n), fenw(n+1,0LL) {}

    void update(int i, long long v){
        for(; i<=N; i+=(i & -i)) {
            fenw[i] += v;
        }
    }
    long long query(int i){
        long long s=0;
        for(; i>0; i-=(i & -i)) {
            s += fenw[i];
        }
        return s;
    }
    // query range [1..i]
    long long queryRange(int L, int R) {
        if(R < L) return 0;
        return query(R) - query(L-1);
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<int> a(n+1);
        for(int i=1; i<=n; i++){
            cin >> a[i];
        }

        // 1) Count all odd-length subarrays
        // # of odd-length subarrays in [1..n] = floor((n+1)/2)*floor((n+2)/2)
        long long oddCount = 1LL * ((n+1)/2) * ((n+2)/2);

        // We'll accumulate our result in ans
        long long ans = oddCount;

        // 2) For each x in [1..10], count even-length subarrays
        //    that have freq(x) >= L/2 + 1
        // We can do this by the "D array" and Fenwicks approach.
        for(int x=1; x<=10; x++){

            // Build prefix sum p[i]: number of x's up to index i
            vector<int> p(n+1,0);
            for(int i=1; i<=n; i++){
                p[i] = p[i-1] + (a[i] == x ? 1 : 0);
            }

            // Build D[i] = 2*p[i] - i for i in [0..n]
            // (Note: p[0] = 0 by default, so D[0] = 0)
            vector<long long> D(n+1);
            D[0] = 2LL * p[0] - 0;  // = 0
            for(int i=1; i<=n; i++){
                D[i] = 2LL * p[i] - i;
            }

            // Coordinate-compress all D[i]
            // We'll store them in an array, sort, and map to 1..size
            vector<long long> allVals(D.begin(), D.end());
            sort(allVals.begin(), allVals.end());
            allVals.erase(unique(allVals.begin(), allVals.end()), allVals.end());

            auto compress = [&](long long val){
                // binary search for val in allVals
                int idx = int(std::lower_bound(allVals.begin(), allVals.end(), val) - allVals.begin()) + 1;
                return idx;
            };

            // We maintain two Fenwicks:
            //   fenwEven = for all i' that are even
            //   fenwOdd  = for all i' that are odd
            Fenwick fenwEven((int)allVals.size()), fenwOdd((int)allVals.size());

            // We'll iterate j from 0..n, counting how many i' < j
            // exist such that i'%2 == j%2 and D[i'] <= D[j].
            // But note that subarray [i, j] is length (j-i+1).
            // i' = i-1, so length = j - i + 1 = j - (i'-1) => we want even length => j-(i'-1) is even => j%2 = i'%2.
            long long countForX = 0;

            // Insert i' = 0 (which is even) into fenwEven
            {
                int cpos = compress(D[0]);
                fenwEven.update(cpos, 1LL);
            }

            for(int j=1; j<=n; j++){
                int cpos = compress(D[j]);
                if(j % 2 == 0) {
                    // We want all i' even s.t. D[i'] <= D[j]
                    // i.e. query fenwEven up to cpos
                    countForX += fenwEven.query(cpos);
                    // then add this D[j] to fenwEven
                    fenwEven.update(cpos, 1LL);
                } else {
                    // j is odd => we want i' odd s.t. D[i'] <= D[j]
                    countForX += fenwOdd.query(cpos);
                    // then add this D[j] to fenwOdd
                    fenwOdd.update(cpos, 1LL);
                }
            }

            ans += countForX;
        }

        cout << ans << "\n";
    }
    return 0;
}

How It Works, Step-by-Step

1. Reading input: We read $t$ test cases, and for each test:

   • Read $n$ and then the array $a[1..n]$.

2. Odd-length subarrays:
   We add

   $$\text{oddCount} = \left(\frac{n+1}{2}\right)\left(\frac{n+2}{2}\right)$$

   to our answer immediately (all these are automatically "good").

3. Even-length subarrays:

   • For each integer $x = 1$ to $10$:

     1. Build p[i] (prefix sums counting how many times $x$ appeared up to index $i$).
     2. Compute $D[i] = 2p[i] - i$.
     3. Coordinate-compress these $D[i]$.
     4. Sweep $j$ from 0 to $n$ (here, $j=0$ stands for the subarray start offset logic):
        • Maintain two Fenwicks:
          • fenwEven: stores counts of $D[i']$ for even $i'$.
          • fenwOdd: stores counts of $D[i']$ for odd $i'$.
        • If $j$ is even, we look up how many even $i' < j$ have $D[i'] \le D[j]$.
        • If $j$ is odd, we look up how many odd $i' < j$ have $D[i'] \le D[j]$.
        • Add that to countForX. Then insert $D[j]$ into the corresponding Fenwicks structure.

   • Sum up these counts for $x=1$ to $10$.

4. Output: Print the total count ans = (odd subarrays) + (count of even subarrays that satisfy the median-equality condition).

This completes the solution.

Key Insight: A subarray of length $2k$ has its two medians equal if and only if there exists an element $x$ with frequency $\ge k+1$. Because $\{1,\dots,10\}$ is small, we can safely count for each $x$ separately without overcounting (two different values $x_1 \neq x_2$ cannot both exceed $\tfrac{2k}{2}+1$ in the same subarray).