[51nod1297]管理二叉樹

一個初始為空的二叉搜索樹T，以及1到N的一個排列P: {a1, a2, ..., aN}。我們向這個二叉搜索樹T添加這些數，從a1開始, 接下來是 a2, ...， 以aN結束。在每一個添加操作后，輸出T上每對節點之間的距離之和。

例如：4 7 3 1 8 2 6 5。最終的二叉樹為：

4

/ ? \

3 ? ? ?7 ??

/ ? ? ?/ ? \

1 ? ? ?6 ? ? 8

\ ? ?/

2 ?5

節點兩兩之間的距離和 =?6+5+5+4+3+2+1+5+4+4+3+2+1+4+3+3+2+1+3+2+2+1+2+1+1+2+1+3 = 76

　Input
　　第1行：1個數N。(1 <= N <= 100000)
　　第2 - N + 1行：每行1個數，對應排列的元素。(1 <= ai <= N)
　Output
　　輸出共N行，每行1個數，對應添加當前元素后，每對節點之間的距離之和。

?

?

　　先把樹求出來。。具體的話就是每次添加元素之后，找到這個數的前驅后繼，哪個有空位這個元素就在哪。隨便寫個什么數據結構。

　　求節點的距離和的話。。我寫了點分治，每次查找完往里面加點...查找啊去重啊什么的都是一樣的套路...

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#include<cstdlib>
#include<bitset>
//#include<ctime>
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define d double
//#define ld long double
using namespace std;
const int maxn=100233,mxnode=maxn;
struct zs{int too,pre;}e[maxn<<1];int tot,last[maxn];
int lc[mxnode],rc[mxnode],v[mxnode],rnd[mxnode],tt;int V,PRE,AFT,rt;bool u[maxn][2];
int sz[maxn],mx[maxn],RT,POI,dis[maxn],st[maxn],top,mxdep[maxn];bool del[maxn];
int bel[maxn][20],belson[maxn<<1][20],dist[maxn][20],_sz[maxn],_sonsz[maxn<<1];int ID;
ll _sum[maxn],_sonsum[maxn<<1];
int a[maxn];
int i,j,k,n,m;

int ra,fh;char rx;
inline int read(){
    rx=getchar(),ra=0,fh=1;
    while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();
    if(rx=='-')fh=-1,rx=getchar();
    while(rx>='0'&&rx<='9')ra=ra*10+rx-48,rx=getchar();return ra*fh;
}
inline void maxs(int &a,int b){if(b>a)a=b;}
inline void lturn(int &x){int R=rc[x];rc[x]=lc[R],lc[R]=x,x=R;}
inline void rturn(int &x){int L=lc[x];lc[x]=rc[L],rc[L]=x,x=L;}
inline void insert(int &x){
    if(!x){x=++tt,v[x]=V,rnd[x]=rand();return;}
    if(V<v[x]){
        insert(lc[x]);
        if(rnd[lc[x]]<rnd[x])rturn(x);
    }else{
        insert(rc[x]);
        if(rnd[rc[x]]<rnd[x])lturn(x);
    }
}
void getpre(int x){
    if(!x)return;
    if(v[x]<V)PRE=v[x],getpre(rc[x]);else getpre(lc[x]);
}
void getaft(int x){
    if(!x)return;
    if(v[x]>V)AFT=v[x],getaft(lc[x]);else getaft(rc[x]);
}
inline void ins(int a,int b){
    e[++tot].too=b,e[tot].pre=last[a],last[a]=tot;
    e[++tot].too=a,e[tot].pre=last[b],last[b]=tot;
}


void getrt(int x,int fa){
    sz[x]=1,mx[x]=0;
    for(int i=last[x];i;i=e[i].pre)if(e[i].too!=fa&&!del[e[i].too])
        getrt(e[i].too,x),maxs(mx[x],sz[e[i].too]),sz[x]+=sz[e[i].too];
    maxs(mx[x],POI-sz[x]);
    if(mx[x]<mx[RT])RT=x;
}
void getpoi(int x,int fa){
    dis[x]=dis[fa]+1,st[++top]=x,sz[x]=1;
    for(int i=last[x];i;i=e[i].pre)if(e[i].too!=fa&&!del[e[i].too])
        getpoi(e[i].too,x),sz[x]+=sz[e[i].too];
}
void work(int x,int dep){
    int i,p;
    RT=0,getrt(x,0),x=RT,mxdep[x]=dep,bel[x][dep]=x,dist[x][dep]=dis[x]=0;
    for(i=last[x];i;i=e[i].pre)if(!del[e[i].too]){
        getpoi(e[i].too,x);ID++;
        while(top)p=st[top--],bel[p][dep]=x,belson[p][dep]=ID,dist[p][dep]=dis[p];
    }
    del[x]=1,sz[x]=-233;
    for(i=last[x];i;i=e[i].pre)if(!del[e[i].too])
        POI=sz[e[i].too],work(e[i].too,dep+1);
}

int main(){
    n=read();
    for(i=1;i<=n;i++){
        a[i]=read();
        if(i>1){
            PRE=AFT=0,V=a[i],getpre(rt),getaft(rt),
            insert(rt);
            if(!PRE||!AFT)ins(PRE|AFT,a[i]),u[PRE|AFT][PRE>0]=1;
            else if(!u[PRE][1])u[PRE][1]=1,ins(PRE,a[i]);
            else u[AFT][0]=1,ins(AFT,a[i]);
        }else V=a[i],insert(rt);
    }
//    for(i=1;i<=n;i++)for(j=last[i];j;j=e[j].pre)printf("%d-->%d\n",i,e[j].too);
    
    mx[0]=1<<30,POI=n,work(a[1],1);ll ans=0;int fa,son,dis;
    for(i=1;i<=n;i++){
        k=a[i];
        
        ans+=_sum[k],_sz[k]++;
        for(j=mxdep[k]-1;j;j--)
            fa=bel[k][j],son=belson[k][j],dis=dist[k][j],
            ans+=1ll*dis*(_sz[fa]-_sonsz[son])+_sum[fa]-_sonsum[son],
            _sz[fa]++,_sonsz[son]++,_sum[fa]+=dis,_sonsum[son]+=dis;
        
        printf("%lld\n",ans);
    }
}

?