ZP4PZM - Online C++0x Compiler & Debugging Tool

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

const int MAXN = 500000;
int n;
int a[MAXN+5];
unordered_map<int,int> freq;
vector<int> pos[MAXN+5];

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

    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        freq[a[i]]++;
        pos[a[i]].push_back(i);
    }

    long long total = 1LL * n * (n+1) / 2;
    int B = sqrt(n);

    // xử lý light
    long long bad = 0;
    for(auto &p: freq){
        int x = p.first, f = p.second;
        if(f > B) continue;
        auto &vec = pos[x];
        vec.insert(vec.begin(),0);
        vec.push_back(n+1);
        for(int i=1;i+f<= (int)vec.size()-1; i++){
            int L = vec[i-1]+1;
            int R = vec[i+f]-1;
            int midL = vec[i];
            int midR = vec[i+f-1];
            long long left = midL - L + 1;
            long long right = R - midR + 1;
            bad += left * right;
        }
    }

    // xử lý heavy
    vector<int> heavy;
    for(auto &p: freq){
        if(p.second > B) heavy.push_back(p.first);
    }

    for(int x: heavy){
        vector<int> S(n+1,0);
        for(int i=1;i<=n;i++){
            if(a[i]==x) S[i] = S[i-1]+1;
            else S[i] = S[i-1]-1;
        }

        unordered_map<int,int> cnt;
        cnt.reserve(2*n);
        cnt.max_load_factor(0.7);
        cnt[0]=1;

        long long cur=0;
        for(int i=1;i<=n;i++){
            if(S[i]==S[i-1]+1){
                cur += cnt[S[i]];
            }else{
                cur -= cnt[S[i]];
            }
            bad += cur;
            cnt[S[i]]++;
        }
    }

    cout << total - bad << "\n";
    return 0;
}