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

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

struct Fenwick {
    int n; vector<int> bit;
    Fenwick(int n=0){init(n);}
    void init(int n_){ n=n_; bit.assign(n+1,0); }
    void add(int i,int v){ for(;i<=n;i+=i&-i) bit[i]+=v; }
    int sumPrefix(int i){ int s=0; for(;i>0;i-=i&-i) s+=bit[i]; return s; }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin>>N;
    vector<int>A(N+1); int maxA=0;
    for(int i=1;i<=N;i++){cin>>A[i]; maxA=max(maxA,A[i]);}
    vector<vector<int>>pos(maxA+1);
    for(int i=1;i<=N;i++) pos[A[i]].push_back(i);
    const int B=700;
    ll total=(ll)N*(N+1)/2;
    ll bad=0;
    for(int val=1;val<=maxA;val++){
        int k=pos[val].size();
        if(k<=B) continue;
        vector<int>S(N+1);
        for(int i=1;i<=N;i++) S[i]=S[i-1]+(A[i]==val?1:-1);
        vector<int>comp=S; sort(comp.begin(),comp.end());
        comp.erase(unique(comp.begin(),comp.end()),comp.end());
        Fenwick fw(comp.size()+2);
        for(int i=0;i<=N;i++){
            int id=lower_bound(comp.begin(),comp.end(),S[i])-comp.begin()+1;
            bad+=fw.sumPrefix(id-1);
            fw.add(id,1);
        }
    }
    for(int val=1;val<=maxA;val++){
        int k=pos[val].size();
        if(k==0||k>B) continue;
        vector<int>p; p.push_back(0);
        for(int x:pos[val]) p.push_back(x);
        p.push_back(N+1);
        for(int t=1;t<=k;t++){
            for(int i=1;i+t-1<=k;i++){
                int left_prev=p[i-1], left_first=p[i];
                int right_last=p[i+t-1], right_next=p[i+t];
                int Lstart=left_prev+1, Lend=left_first;
                if(Lstart>Lend) continue;
                int Rmin=right_last, Rmax_cap=right_next-1;
                if(Rmin>Rmax_cap) continue;
                ll Cconst=2LL*t-1-Rmin;
                int D=Rmax_cap-(2*t-2);
                int L1=max(Lstart,Rmin-(2*t-2)), L2=min(Lend,D);
                ll sum=0;
                if(L1<=L2){
                    ll cnt=L2-L1+1;
                    ll sumL=(ll)(L1+L2)*cnt/2;
                    sum+=sumL+cnt*Cconst;
                }
                int L3=max(Lstart,D+1), L4=Lend;
                if(L3<=L4){
                    ll cnt=L4-L3+1;
                    ll valR=Rmax_cap-Rmin+1;
                    if(valR>0) sum+=cnt*valR;
                }
                if(sum>0) bad+=sum;
            }
        }
    }
    cout<<total-bad<<"\n";
}