• 单点修改 + 单点查询
  • 楼兰图腾

单点修改 + 单点查询

楼兰图腾

题目描述


参考题解

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 2e5+5;

typedef long long LL;

int n;
int a[N];
int treeMessage[N]; //the cnt of i

int ll[N], lg[N], rl[N], rg[N];

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

void add(int x, int v)
{
    for(; x <= n; x += lowbit(x))
    {
        treeMessage[x] += v;
    }
}

// the sum of treeMessage[i], i: 1~x
int query(int x)
{
    int ans = 0;
    while(x > 0)
    {
        ans += treeMessage[x];
        x = x - lowbit(x);
    }
    return ans;
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++ i)
    {
        scanf("%d", a+i);
    }
    for(int i = 1; i <= n; i ++)
    {
        ll[i] = query(a[i]-1);
        lg[i] = i-1 - query(a[i]); //之前有i-1个数，不包括a[i]
        add(a[i], 1);
    }
    memset(treeMessage, 0, sizeof treeMessage);
    for(int i = n; i > 0; -- i)
    {
        rl[i] = query(a[i]-1);
        rg[i] = n-i - query(a[i]);
        add(a[i], 1);
    }
    LL ans1 = 0, ans2 = 0;
    for(int i = 1; i <= n; ++ i)
    {
        ans1 += lg[i] * (LL)rg[i];
        ans2 += ll[i] * (LL)rl[i];
    }
    cout << ans1 << " " << ans2 << endl;
    return 0;
}