ch_4201 楼兰图腾

同树状数组求逆序对思路

只不过要求4次（种）

#include<iostream>
#include<cstdio>

#define ri register int
#define u long long

namespace opt {

    inline u in() {
        u x(0),f(1);
        char s(getchar());
        while(s<'0'||s>'9') {
            if(s=='-') f=-1;
            s=getchar();
        }
        while(s>='0'&&s<='9') {
            x=(x<<1)+(x<<3)+s-'0';
            s=getchar();
        }
        return x*f;
    }

}

using opt::in;

#define NN 200005

#include<cstring>

namespace mainstay {

    u N,K;

    u c[NN],a[NN],l[2][NN],r[2][NN];

    inline u ask(const u &x) {
        u _re(0);
        for(ri i(x); i; i-=i&-i) _re+=c[i];
        return _re;
    }

    inline void add(const u &x,const u &y) {
        for(ri i(x); i<=N; i+=i&-i) c[i]+=y;
    }

    inline void solve() {
        N=in();
        for(ri i(1); i<=N; ++i) a[i]=in();
        
        std::memset(c,0,sizeof(c));
        for(ri i(1);i<=N;++i){
            l[0][i]=ask(N)-ask(a[i]);
            add(a[i],1);
        }
        std::memset(c,0,sizeof(c));
        for(ri i(N);i>=1;--i){
            r[0][i]=ask(N)-ask(a[i]);
            add(a[i],1);
        }
        
        std::memset(c,0,sizeof(c));
        for(ri i(1);i<=N;++i){
            l[1][i]=ask(a[i]-1);
            add(a[i],1);
        }
        std::memset(c,0,sizeof(c));
        for(ri i(N);i>=1;--i){
            r[1][i]=ask(a[i]-1);
            add(a[i],1);
        }
        
        long long ans[2]={0,0};
        for(ri i(1);i<=N;++i){
            ans[0]+=l[0][i]*r[0][i];
            ans[1]+=l[1][i]*r[1][i];
        }
        printf("%lld %lld",ans[0],ans[1]);
    }

}

int main() {

    //freopen("x.txt","r",stdin);
    std::ios::sync_with_stdio(false);
    mainstay::solve();

}