P1908题解

yoyo2005 · 2019-04-01 20:55:19 · 题解

听说大佬们都在用归并排序和树状数组和暴力，那蒟蒻不才，就来一发平衡树吧。

主要思路：

从后向前，每次将一个数加入平衡树，每次加入后求出已经在平衡树中的数中比它小的数的个数。

每次求出个数后相加，就是答案。

上代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double alpha=0.75;
const int inf=0x3f3f3f3f;
struct node
{
    int son[2];
    int fa,size,num;
};
node a[500005];
int n,m,root;
int s[500005];
int num;
void init()
{
    n=2;
    root=1;
    a[1].num=-inf;
    a[1].size=2;
    a[1].son[1]=2;
    a[2].num=inf;
    a[2].size=1;
    a[2].fa=1;
    return;
}
bool check(int t)
{
    return (double)a[t].size*alpha>=(double)a[a[t].son[0]].size
        && (double)a[t].size*alpha>=(double)a[a[t].son[1]].size;
}
int buildtree(int l,int r)
{
    if(l>r)
    {
        return 0;
    }
    int mid,t;
    mid=(l+r)>>1;
    t=s[mid];
    a[a[t].son[0]=buildtree(l,mid-1)].fa=t;
    a[a[t].son[1]=buildtree(mid+1,r)].fa=t;
    a[t].size=a[a[t].son[0]].size+a[a[t].son[1]].size+1;
    return t;
}
void recycle(int t)
{
    if(a[t].son[0])
    {
        recycle(a[t].son[0]);
    }
    s[++num]=t;
    if(a[t].son[1])
    {
        recycle(a[t].son[1]);
    }
    return;
}
void rebuild(int t)
{
    num=0;
    recycle(t);
    int fa,son,cur;
    fa=a[t].fa;
    son=(a[a[t].fa].son[1]==t);
    cur=buildtree(1,num);
    a[a[fa].son[son]=cur].fa=fa;
    if(t==root)
    {
        root=cur;
    }
    return;
}
int getnum(int x)
{
    int t;
    t=root;
    while(1)
    {
        if(a[t].num==x)
        {
            return t;
        }
        else
        {
            t=a[t].son[a[t].num<x];
        }
    }
}
void insert(int x)
{
    int t,cur;
    t=root;
    cur=++n;
    a[cur].size=1;
    a[cur].num=x;
    while(1)
    {
        a[t].size++;
        bool son=(x>=a[t].num);
        if(a[t].son[son])
        {
            t=a[t].son[son];
        }
        else
        {
            a[a[t].son[son]=cur].fa=t;
            break;
        }
    }
    int pd;
    pd=0;
    int i;
    for(i=cur;i;i=a[i].fa)
    {
        if(!check(i))
        {
            pd=i;
        }
    }
    if(pd)
    {
        rebuild(pd);
    }
    return;
}
int getrank(int x)
{
    int t,ans;
    t=root;
    ans=0;
    while(t)
    {
        if(a[t].num<x)
        {
            ans+=a[a[t].son[0]].size+1;
            t=a[t].son[1];
        }
        else
        {
            t=a[t].son[0];
        }
    }
    return ans;
}
ll tot;
int in[500005];
int main()
{
    scanf("%d",&m);
    init();
    int i;
    for(i=1;i<=m;i++)
    {
        scanf("%d",&in[i]);
    }
    for(i=m;i>=1;i--)
    {
        insert(in[i]);
        tot+=getrank(in[i])-1;
    }
    printf("%lld\n",tot);
    return 0;
}

蒟蒻写的是替罪羊树。