Codeforces Round 997 (Div. 2) D

D. Unique Median

由题意可以看出奇数长度的数组一定合法，但是偶数长度的数组不一定合法，我们反过来来找非法数组的充要条件，我们观察非法数组 $[1,3,2,1]$ ，发现首先其长度为偶数，并且存在一该数组内包含的数 $k$（该例子中 $k = 1$） , 小于等于 $k$ 的数的数量正好为数组的大小的一半。

我们可以枚举 $k$ （因为 $k$ 必须在数组中存在， 所以可以之遍历出现过的可能 $k$ 值），其范围在 $[1,10]$ ，枚举 $k$ ， 然后构造出数组 $C$ ，表示每一个位置前的小于等于 $k$ 的数数量， 这样对一个偶数长区间， 倘若 $2 * (C_r - C_{l-1}) = r - l + 1$ ，并且区间内包含有 $k$ 我们就可以说这一个区间不合法。

对于上述式子我们继续变形，把具有相同个变量的放到一边，得到 $f = 2 * C_r - r = 2 * C_{l-1} - l + 1$ ，我们由此可以先枚举右端点（或者左端点），用 map集合 记录 $f$ 的值出现次数（由于我们要保证长度为偶数， 所以奇数偶数端点要分开存储）。

接着枚举左端点，又因为我们要保证区间内一定有 $k$ 存在， 我们需要预先处理一个数组 $nex$ ， 其含义为 第 $i$ 个位置之后的第一个 $k$ 出现的位置（包含 $i$），这样我们枚举每一个左端点是首先先把在 $[i , nex[i]-1]$ 这个区间的右端点对应的值 -- ，因为这样的右端点和当前左端点构成的区间一定不包含 $k$ ，不合法。

由此我们最后用总可能值最后减去每一个位置相对应相反奇偶性的记录值即可。

int a[N] ;
int cnt[N] ;//i个位置之前小于等于k的数的数量
int nex[N] ;//i个位置之后第一个k的位置
int b[N] ;
void solve(){
    cin >> n ;
    set<int> se ;
    for(int i = 1;  i <= n ; ++ i){
        cin >> a[i] ;
        se.insert(a[i]) ;
    }
    //相同的数组不能重复
    ans = (1LL * (1 + n) * n) / 2   ;
    //考虑不合法的充要条件 存在k使得偶数长区间， 小于等于k的数的数量等于 区间长度一半
    unordered_map<int,int> mp[2] ;
    for(auto e : se){//
        int k = e ;
        for(int i = 1  ; i <= n ; ++ i ){
            cnt[i] = cnt[i-1] + (a[i] <= k) ;
        }
        mp[0].clear() ;
        mp[1].clear() ;
        nex[n + 1] = n + 1 ;
        for(int i = n ; i >= 1 ; -- i){
            if(a[i] == k) nex[i] = i ;
            else nex[i] = nex[i + 1] ;
        }
        //非法条件， 偶数区间包含有k并且r - l + 1 = (cnt[r] - cnt[l-1]) * 2,
        //根据端点奇偶性分为两桶，左右端点 一奇一偶，保证区间长度为偶数 
        for(int i = 1; i <= n ; ++ i){//确定右端点，  2 * cnt[r] - r = 2 * cnt[l-1] - l + 1
            mp[i&1][cnt[i] * 2 - i] ++ ;
        }
        int pt = 1;
        for(int i = 1; i <= n ; ++ i){//保证区间内有 k 存在
            while(pt < nex[i]){// l <= nex[i], r > nex[i] ,保证r在nex[i] 左侧的情况不会进入计算，
                mp[pt&1][cnt[pt] * 2 - pt] -- , pt ++ ;
            }
            ans -= mp[(i^1)&1][cnt[i-1] * 2 - i + 1]  ;//
        }
    }
    cout << ans << endl ;
}