树状数组

Ultra-QuickSort
先离散化处理在利用树状数组求一个数前面比他小的。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstdlib>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int MAX_N=500000+5;
const int MAX_M=100000+5;
const int INF=0x7fffffff;
const int inf=1000000000;
const double EPS=1e-6;
const ull base=123;
const ll mod=998244353;
const double pi=4*atan(1.0);
struct node
{
    int pos;
    int x;
    int cnt;
} a[MAX_N];
int n;
int bit[MAX_N];
bool cmp(node a,node b)
{
    return a.x<b.x;
}
bool cmp2(node a,node b)
{
    return a.pos<b.pos;
}
int sum(int x)
{
    int s=0;
    while(x>0)
    {
        s+=bit[x];
        x-=x&-x;
    }
    return s;
}
void add(int x,int val)
{
    while(x<=n)
    {
        bit[x]+=val;
        x+=x&-x;
    }
}
int main()
{
    while(cin>>n&&n)
    {
        me(bit,0);
        int i;
        for(i=1; i<=n; i++)
        {
            a[i].pos=i;
            scanf("%d",&a[i].x);
        }
        sort(a+1,a+1+n,cmp);
        int cnt=1;
        a[1].cnt=1;
        for(i=2; i<=n; i++)
        {
            a[i].cnt=i;
        }
        sort(a+1,a+1+n,cmp2);
        ll ans=0;
        for(i=1; i<=n; i++)
        {
            add(a[i].cnt,1);
            ans+=(ll)(i-sum(a[i].cnt));
        }
        cout<<ans<<endl;
    }
}

本文地址：https://blog.csdn.net/ljy121121/article/details/107387764