Good Subarrays Count Algorithm

Analysis

We are given an integer array $a$ of length $n$, and we want to count the number of good subarrays of $a$. A subarray $b$ of length $m$ is called good if, after sorting $b$, its two medians coincide. Formally,

$$b_{\lfloor (m+1)/2 \rfloor} \;=\; b_{\lceil (m+1)/2 \rceil}.$$

Equivalently:

1. If $m$ is odd, then $\lfloor (m+1)/2 \rfloor = \lceil (m+1)/2 \rceil,$ so any odd-length subarray is automatically good.
2. If $m$ is even, say $m = 2k,$ then we need the $\tfrac{m}{2}$-th and $\bigl(\tfrac{m}{2} + 1\bigr)$-th elements (in sorted order) to be equal. In more intuitive terms, there must be some value $x$ in that subarray that appears at least $k+1$ times (i.e.\ $\ge \tfrac{m}{2}+1$ times).
   • Why? Because for a length-$2k$ subarray to have the two medians the same, the “middle two” elements in sorted order must both be $x$. That forces $\text{freq}(x) \ge k+1$.

Hence the subarray is good if:

• it has odd length, or
• it has even length and contains some “majority” element whose frequency is $\ge \tfrac{\text{length}}{2} + 1$.

Since each test can have up to $n = 10^5$ (and many test cases, but with total $\sum n \le 10^5$), an $O(n^2)$ solution is too slow.

Below is a common, efficient strategy once we notice that:

1. Counting all subarrays of odd length is easy with a direct formula.
2. For the even-length subarrays, we only need to check if there is a majority element.
3. Because the array elements $a_i$ are bounded ($1 \le a_i \le 10$), a subarray cannot have two distinct majority elements simultaneously.
   • Indeed, in an even-length subarray of length $2k$, to have $\text{freq}(x) \ge k+1$ and also $\text{freq}(y) \ge k+1$ (for $x \neq y$) would exceed $2k$ total.

Therefore we can “sum over each candidate $x\in \{1,\dots,10\}$” the number of even-length subarrays in which $x$ is a majority. Because no even subarray can be majority for two different values at once, we will not double-count.

Finally, we add

• all odd-length subarrays (which are automatically good),
• plus all even-length subarrays that have some majority element $x\in\{1,\dots,10\}$.

---

Step 1. Count all odd-length subarrays

The total number of subarrays of an $n$-element array is

$$\frac{n\,(n+1)}{2}.$$

Among these, the number of odd-length subarrays is given by a known closed-form:

$$\text{oddCount} \;=\; \left\lfloor \frac{n+1}{2} \right\rfloor \;\times\; \left\lfloor \frac{n+2}{2} \right\rfloor.$$

You can verify this formula by small cases or by combinatorial arguments.

---

Step 2. Count the even-length subarrays that have a majority element

Let us focus on one candidate value $x \in \{1,\dots,10\}$. Define a new array

$$b[i] \;=\; \begin{cases} 1 & \text{if } a[i] = x,\\ 0 & \text{otherwise}. \end{cases}$$

Let $p[i]$ be the prefix sum of $b[i]$, i.e.\

$$p[0] = 0,\quad p[i] = b[1] + b[2] + \cdots + b[i].$$

Then for a subarray $i..j$ (1-based indices) of length $L = j - i + 1$,
$\text{freq}_x\bigl(a[i..j]\bigr) = p[j] - p[i-1].$

An even-length subarray $i..j$ (so $L$ is even, $L=2k$) has $x$ as a majority element if

$$\text{freq}_x \;\ge\; k + 1 \quad\Longleftrightarrow\quad p[j] - p[i-1] \;\ge\; \frac{L}{2} + 1 \;=\; k+1.$$

Since $L = j - i + 1$, the condition is

$$p[j] - p[i-1] \;\ge\; \frac{(j - i + 1)}{2} + 1.$$

We must also enforce that $(j - i + 1)$ is even.

How to count these subarrays efficiently

A known trick is to rewrite the inequality in a form suitable for Fenwick/BIT or balanced-binary-search (such as std::map in C++ or similar). The usual approach:

1. We only care about subarrays of even length, i.e.\ $j - i + 1\equiv 0\ (\text{mod }2)$.
   • Equivalently, $i$ and $j$ have the same parity (both even indices or both odd indices).
2. Rewrite $$p[j] - p[i-1] \;>\; \frac{j - i + 1}{2} - 1$$ or something quite close. One can then do a prefix transformation (often something like $2\,p[i] - i$) and keep track of partial sums, performing lookups in a Fenwick tree or an ordered map.

A simpler “two-scan” method (often used in problems with $\{-1,+1\}$ arrays) might also work here, but one must handle the “length is even” part carefully.

However, because $1 \le a[i] \le 10$, we only have 10 candidate values. That means we can do the following for each $x\in\{1,\dots,10\}$:

• Build the prefix sum array $p[i]$.
• We want to count the number of pairs $(i,j)$ with $i \le j$, same parity, and $$p[j] - p[i-1] \;\ge\; \frac{(j - i + 1)}{2} + 1.$$
• Use a Fenwick (BIT) or an ordered container to do it in $O(n \log n)$ for each $x$.
• Since there are only 10 different $x$-values, the total is $10 \times O(n \log n)$, which is fine for $n \le 10^5$.

Collect the counts for each $x$. Since no even subarray can have two distinct majorities, we can sum those counts without double-counting.

---

Putting it all together

1. Compute $\text{oddCount}$ = number of odd-length subarrays =

   $$\left\lfloor \frac{n+1}{2} \right\rfloor \;\times\; \left\lfloor \frac{n+2}{2} \right\rfloor.$$

2. For each candidate $x \in \{1,\dots,10\}$:

   1. Build $b[i]$ and prefix sums $p[i]$.
   2. Count (using Fenwick or ordered structure) the number of pairs $(i,j)$ with
      • $1 \le i \le j \le n$,
      • $j - i + 1$ is even (so $i$ and $j$ have the same parity),
      • $p[j] - p[i-1] \ge \tfrac{(j - i + 1)}{2} + 1$.
   3. Let that count be $\text{cnt}_x$.

3. Sum up $\text{cnt}_{x}$ over all $x$. Denote this total by $\text{evenMajorityCount}$.

4. The final answer (number of good subarrays) is

   $$\text{oddCount} \;+\; \text{evenMajorityCount}.$$

You repeat the above per test case.

---

C++ Implementation Sketch (Fenwick / BIT)

Below is a (somewhat abbreviated) sketch. The key is to implement the counting step for each $x$. There are various ways to handle “only even-length subarrays”; one common trick is:

• Notice that “$j - i + 1$ is even” $\iff$ “$i$ and $j$ have the same parity.”
• So, you can maintain two Fenwick trees: one for indices $i$ that are odd, and one for indices $i$ that are even. Or, you can separate them in your prefix array approach.

One straightforward pattern (among several) is:

1. Define $$d[i] \;=\; 2 \cdot p[i] - i,$$ and similarly $d[0] = 0$.
2. You want subarray $(i,j)$ with “same parity” and $$p[j] - p[i-1] \;\ge\; \frac{(j - i + 1)}{2} + 1 \;\;\Longleftrightarrow\;\; 2(p[j] - p[i-1]) \;\ge\; (j - i + 1) + 2 \;\;\Longleftrightarrow\;\; \bigl(2p[j] - j\bigr) - \bigl(2p[i-1] - (i-1)\bigr) \;\ge\; 2.$$ That is $$d[j] - d[i-1] \;\ge\; 2 + \bigl((i-1) - j\bigr).$$ …and then you handle the “same parity” by ensuring either both $i$ and $j$ are even or both odd.

Because there are multiple ways to code the details, below is a more “direct” counting approach, using a Fenwick tree keyed by the values of $\,d[i]$. (If you find the offset arithmetic too fiddly, you can store $\,d[i]$ in an std::map<long long,int> as you iterate from left to right, and do an order-statistic or cumulative-frequency approach.)

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

// Fenwick (BIT) for frequencies of indices/values.
struct Fenwick {
    int N;
    vector<int> fenw;
    Fenwick(int n) : N(n), fenw(n+1,0) {}
    void update(int i,int v){ 
        for(; i<=N; i+=(i & -i)) fenw[i]+=v; 
    }
    int query(int i){
        int s=0; for(; i>0; i-=(i & -i)) s+=fenw[i];
        return s;
    }
    // query range [1..i]
};

// You will also need coordinate compression of d[i] values
// if they can be large, so you can store them in Fenwicks.

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
        long long totalSub = 1LL*n*(n+1)/2; 
        // # of odd subarrays = floor((n+1)/2)*floor((n+2)/2)
        long long oddCount = 1LL*((n+1)/2)*((n+2)/2);

        long long ans = oddCount;  // all odd-length are already good

        // 2) For each x in [1..10], count even-length subarrays that have freq(x)>= (L/2 +1)
        long long evenMajorityCount = 0;
        for(int x=1; x<=10; x++){

            // Build b[i], prefix p[i]
            vector<int> b(n+1), p(n+1,0);
            for(int i=1; i<=n; i++){
                b[i] = (a[i]==x ? 1 : 0);
                p[i] = p[i-1] + b[i];
            }

            // We want to count number of pairs (i,j), i<=j, same parity, s.t.
            // p[j] - p[i-1] >= ( (j - i + 1)/2 ) + 1.
            // We'll implement a Fenwicks-based or map-based counting.

            // [Pseudocode or actual detailed code to do the counting...]
            // You can store d[i] = 2*p[i] - i in two separate maps: one for i even, one for i odd,
            // or use a single structure but watch the parity constraints carefully.

            long long countForX = 0;
            // ... implement the counting logic ...
            
            evenMajorityCount += countForX;
        }

        ans += evenMajorityCount;

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

    return 0;
}

The precise details of the Fenwick or binary-search logic can vary. One simpler approach, since $n\le10^5$ and we only do it 10 times, is to store partial sums in an std::vector<long long>, do coordinate-compression for the $d[i]$-values, and then use two Fenwicks (one for odd indices, one for even). As you iterate $j$ from 0 to $n$, you look up how many $i$-indices in the Fenwicks satisfy

$$d[i] \;\le\; d[j] - 2 \quad\text{(because you want }d[j] - d[i]\ge2\text{),}$$

with the additional constraint that $i$ and $j$ have same parity. Then update Fenwicks with $d[j]$.

However you implement it, the core ideas remain:

1. Count odd-length subarrays right away.
2. For each possible majority candidate $x$ (only 10 of them!), count how many even-length subarrays make $x$ appear $\ge \frac{L}{2}+1$ times.
3. Sum those counts, add to the odd-length subarray count.

That solves the problem in about $O(10 \times n \log n)$ time overall, which is acceptable for $\sum n \le 10^5$.

---

Key Takeaways

• Odd-length subarrays are automatically good (both medians collapse into one index).
• Even-length subarrays must have a value whose frequency is strictly more than half of the length (i.e.\ $\ge \frac{L}{2}+1$).
• Because $a_i\le 10$, no two distinct values can both be “strict majority” in the same subarray. So we can count each candidate separately and sum up.
• Prefix-sum transformations plus Fenwicks (or balanced-BST / binary-search) are a common technique to handle “count subarrays whose prefix differences exceed some threshold.”

This yields a clean $O(10 \times n \log n)$ solution in C++.