欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

树状数组

程序员文章站 2022-10-03 18:24:20
Ultra-QuickSort先离散化处理在利用树状数组求一个数前面比他小的。#include#include#include#include#include#include#include#include#include#in...

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