cjb-poi2011treerotations

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#define rep(i,n) for(int i=1;i<=n;i++)
#define mp make_pair
#define pb push_back
using namespace std;
#define PI 3.1415926535897932384626433
#define N 1000010
#define LF double
#define stack stck
struct node
{
    int l,r,cnt,key;
}a[1000100];
int root[3000100];
int n,tot=1;
long long cnt,ans=0;
void update(int x){ a[x].cnt=a[a[x].l].cnt+a[a[x].r].cnt+1; }
int merge(int x,int y)
{
    if (x==0||y==0)return x+y;
    if (a[x].key>a[y].key)
    {
        a[x].r=merge(a[x].r,y);
        update(x);
        return x;
    }
    else
    {
        a[y].l=merge(x,a[y].l);
        update(y);
        return y;
    }
}
void split(int t,int k,int &x,int &y)
{
    if (t==0){x=0; y=0; return;}
    if (t<=k)
    {
        x=t;
        split(a[t].r,k,a[t].r,y);
    }
    else 
    {
        y=t;
        split(a[t].l,k,x,a[t].l);
    }
    if (x!=0)update(x);
    if (y!=0)update(y);
}
void insert(int x,int rt)
{
    int r1,r2;
    split(root[rt],x,r1,r2);
    a[x].l=a[x].r=0;
    a[x].cnt=1;
    cnt=cnt+a[r2].cnt;
    root[rt]=merge(merge(r1,x),r2);
}
void dfs(int x,int rt)
{
    int l=a[x].l;
    int r=a[x].r;
    if (l)dfs(l,rt);
    insert(x,rt);
    if (r)dfs(r,rt);
}
void solve(int t)
{
    int x; scanf("%d",&x);
    if (x!=0)
    {
        root[t]=x;
        a[x].l=a[x].r=0;
        a[x].cnt=1;
        return;
    }
    int l=++tot;
    solve(l);
    int r=++tot;
    solve(r);
    if (a[root[l]].cnt<a[root[r]].cnt)swap(l,r);
    long long sum=1ll*a[root[l]].cnt*a[root[r]].cnt;
    cnt=0;
    dfs(root[r],l);
    ans+=min(cnt,sum-cnt);
    root[t]=root[l];
}
int main()
{
    srand(time(0));
    cin>>n;
    rep(i,n)a[i].key=random();
    solve(1);
    cout<<ans<<endl;
    return 0;
}
}}}

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#define rep(i,n) for(int i=1;i<=n;i++)
#define mp make_pair
#define pb push_back
using namespace std;
#define PI 3.1415926535897932384626433
#define N 1000010
#define LF double
#define stack stck
struct node
{
    int l,r,cnt,key;
}a[1000100];
int root[3000100];
int n,tot=1;
long long cnt,ans=0;
void update(int x){ a[x].cnt=a[a[x].l].cnt+a[a[x].r].cnt+1; }
int merge(int x,int y)
{
    if (x==0||y==0)return x+y;
    if (a[x].key>a[y].key)
    {
        a[x].r=merge(a[x].r,y);
        update(x);
        return x;
    }
    else
    {
        a[y].l=merge(x,a[y].l);
        update(y);
        return y;
    }
}
void split(int t,int k,int &x,int &y)
{
    if (t==0){x=0; y=0; return;}
    if (t<=k)
    {
        x=t;
        split(a[t].r,k,a[t].r,y);
    }
    else 
    {
        y=t;
        split(a[t].l,k,x,a[t].l);
    }
    if (x!=0)update(x);
    if (y!=0)update(y);
}
void insert(int x,int rt)
{
    int r1,r2;
    split(root[rt],x,r1,r2);
    a[x].l=a[x].r=0;
    a[x].cnt=1;
    cnt=cnt+a[r2].cnt;
    root[rt]=merge(merge(r1,x),r2);
}
void dfs(int x,int rt)
{
    int l=a[x].l;
    int r=a[x].r;
    if (l)dfs(l,rt);
    insert(x,rt);
    if (r)dfs(r,rt);
}
void solve(int t)
{
    int x; scanf("%d",&x);
    if (x!=0)
    {
        root[t]=x;
        a[x].l=a[x].r=0;
        a[x].cnt=1;
        return;
    }
    int l=++tot;
    solve(l);
    int r=++tot;
    solve(r);
    if (a[root[l]].cnt<a[root[r]].cnt)swap(l,r);
    long long sum=1ll*a[root[l]].cnt*a[root[r]].cnt;
    cnt=0;
    dfs(root[r],l);
    ans+=min(cnt,sum-cnt);
    root[t]=root[l];
}
int main()
{
    srand(time(0));
    cin>>n;
    rep(i,n)a[i].key=random();
    solve(1);
    cout<<ans<<endl;
    return 0;
}