D. Intersecting Segments

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

const int N = 1e5 + 5e1;
typedef vector<int> vi;
#define rg (p << 1) | 1
#define lf (p << 1)

int n ,Q ,a[N] ,Idx[N] ,Ans[N];

class SegTree {
    public:
        vector<int> Seg;
    private:

        int Compain(int a ,int b){
            return a + b;
        }

        void UPD(int i ,int v ,int p ,int L ,int R){
            if( i > R || i < L ) return;
            if( L == R ){
                Seg[p] = v; return;}

            int Mid = (L + R) >> 1;
            UPD(i ,v ,lf ,L ,Mid);
            UPD(i ,v ,rg ,Mid + 1 ,R);
            Seg[p] = Compain(Seg[lf] ,Seg[rg]);
        }

        int QRY(int i ,int j ,int p ,int L ,int R){
            if( i >  R || j <  L ) return 0;
            if( i <= L && R <= j ) return Seg[p];

            int Mid = (L + R) >> 1;
            int LF = QRY(i ,j ,lf ,L ,Mid);
            int RG = QRY(i ,j ,rg ,Mid + 1 ,R);
            return Compain(LF ,RG);
        }
    public:
        SegTree(int n){
            Seg.assign(4 * n ,0);
        }
        void ReSet(){
            for(auto&i:Seg)i=0;
        }
        void UPD(int i ,int v){
            UPD(i ,v ,1 ,1 ,2*n);
        }
        int QRY(int L ,int R){
            return QRY(L ,R ,1 ,1 ,2*n);
        }
};

int main() {
    scanf("%d" ,&n);
    SegTree ST(2*(n + 1));

    for(int i=1 ; i <= 2 * n ; i++)
        scanf("%d" ,&a[i]);

    for(int i=1 ; i <= 2 * n ; i++){
        if( Idx[ a[i] ] > 0 ){
            ST.UPD(Idx[ a[i] ] ,0);
            Q = ST.QRY(Idx[ a[i] ] ,i);
            Ans[ a[i] ] = Q;
            Idx[ a[i] ] = 0;
        } else {
            Idx[ a[i] ] = i;
            ST.UPD(Idx[ a[i] ] ,1);
        }
    }

    ST.ReSet();
    reverse(a + 1 , a + 1 + 2 * n);
    for(int i=1 ; i <= 2 * n ; i++){
        if( Idx[ a[i] ] > 0 ){
            ST.UPD(Idx[ a[i] ] ,0);
            Q = ST.QRY(Idx[ a[i] ] ,i);
            Ans[ a[i] ] += Q;
            Idx[ a[i] ] = 0;
        } else {
            Idx[ a[i] ] = i;
            ST.UPD(Idx[ a[i] ] ,1);
        }
    }

    for(int i=1 ; i <= n ; i++)
        printf("%d " ,Ans[i]);
    return 0;
}