【CF 459D】 Pashmak and Parmida's problem

【CF 459D】 Pashmak and Parmida’s problem

预处理+线段树求逆序对 新学了树状数组 很适合这题 来一发

代码如下:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <map>
#include <cstring>
#define ll long long

using namespace std;

map <int,int> mp;

int l[1111111],r[1111111];
int num[1111111];
int tr[1111111];
int sum[1111111];

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

int Getsum(int x)
{
    int s = 0;
    while(x)
    {
        s += sum[x];
        x -= Bite(x);
    }
    return s;
}

void Add(int x,int n)
{
    while(x <= n)
    {
        sum[x]++;
        x += Bite(x);
    }
}

int main()
{
    int n,i,j,mm;
    ll ans = 0;
    scanf("%d",&n);

    mm = 0;
    for(i = 0; i < n; ++i)
    {
        scanf("%d",&num[i]);
        mp[num[i]]++;
        l[i] = mp[num[i]];
        mm = max(mm,l[i]);
    }
    mp.clear();
    for(i = n-1; i >= 0; --i)
    {
        mp[num[i]]++;
        r[i] = mp[num[i]];
    }
    memset(sum,0,sizeof(sum));
    for(i = n-1; i > 0; --i )
    {
        Add(r[i],mm);
        ans += Getsum(l[i-1]-1);
    }
    printf("%I64d\n",ans);
    return 0;
}