526互联

AcWing 241. 楼兰图腾 / 树状数组 + 在线隔离数据 + 变为 1 统计和

发布时间 2023-04-26 16:32:04作者: 妃即

AcWing 241. 楼兰图腾 

#include <iostream>
#include <cstring>

using namespace std;

const int N = 2e5 + 10;
typedef long long LL;

int n, a[N], tr[N];
LL highle[N], lowle[N];

int lowbit(int x)
{
    return x & -x;    
}

void add(int u, int c)
{
    for (int i = u; i <= n; i += lowbit(i)) tr[i] += c;
}

int sum(int u)
{
    int ans = 0;
    for (int i = u; i > 0; i -= lowbit(i)) ans += tr[i];
    return ans;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) 
    {
        cin >> a[i];
        
        highle[i] = sum(n) - sum(a[i]);
        lowle[i] = sum(a[i] - 1);
        
        add(a[i], 1);
    }
    
    memset(tr, 0, sizeof tr);
    
    LL cntA = 0, cntV = 0;
    for (int i = n; i >= 1; i -- )
    {
        cntA += lowle[i] * sum(a[i] - 1);
        cntV += highle[i] * (sum(n) - sum(a[i]));
        
        add(a[i], 1);
    }
    
    cout << cntV << ' ' << cntA;
    
    return 0;
}