在线设计平台的消费者分析,山西常见网站建设推荐优化,积分支付 WordPress,土巴兔装修公司一个初始为空的二叉搜索树T#xff0c;以及1到N的一个排列P: {a1, a2, ..., aN}。我们向这个二叉搜索树T添加这些数#xff0c;从a1开始, 接下来是 a2, ...#xff0c; 以aN结束。在每一个添加操作后#xff0c;输出T上每对节点之间的距离之和。例如#xff1a;4 7 3 1 8 … 一个初始为空的二叉搜索树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 节点两两之间的距离和 6554321544321433213221211213 76 Input 第1行1个数N。(1 N 100000) 第2 - N 1行每行1个数对应排列的元素。(1 ai N) Output 输出共N行每行1个数对应添加当前元素后每对节点之间的距离之和。 先把树求出来。。具体的话就是每次添加元素之后找到这个数的前驱后继哪个有空位这个元素就在哪。随便写个什么数据结构。 求节点的距离和的话。。我写了点分治每次查找完往里面加点...查找啊去重啊什么的都是一样的套路... 1 #includecstdio2 #includeiostream3 #includecstring4 #includealgorithm5 #includequeue6 #includecmath7 #includecstdlib8 #includebitset9 //#includectime10 #define ll long long11 #define ull unsigned long long12 #define ui unsigned int13 #define d double14 //#define ld long double15 using namespace std;16 const int maxn100233,mxnodemaxn;17 struct zs{int too,pre;}e[maxn1];int tot,last[maxn];18 int lc[mxnode],rc[mxnode],v[mxnode],rnd[mxnode],tt;int V,PRE,AFT,rt;bool u[maxn][2];19 int sz[maxn],mx[maxn],RT,POI,dis[maxn],st[maxn],top,mxdep[maxn];bool del[maxn];20 int bel[maxn][20],belson[maxn1][20],dist[maxn][20],_sz[maxn],_sonsz[maxn1];int ID;21 ll _sum[maxn],_sonsum[maxn1];22 int a[maxn];23 int i,j,k,n,m;24 25 int ra,fh;char rx;26 inline int read(){27 rxgetchar(),ra0,fh1;28 while((rx0||rx9)rx!-)rxgetchar();29 if(rx-)fh-1,rxgetchar();30 while(rx0rx9)rara*10rx-48,rxgetchar();return ra*fh;31 }32 inline void maxs(int a,int b){if(ba)ab;}33 inline void lturn(int x){int Rrc[x];rc[x]lc[R],lc[R]x,xR;}34 inline void rturn(int x){int Llc[x];lc[x]rc[L],rc[L]x,xL;}35 inline void insert(int x){36 if(!x){xtt,v[x]V,rnd[x]rand();return;}37 if(Vv[x]){38 insert(lc[x]);39 if(rnd[lc[x]]rnd[x])rturn(x);40 }else{41 insert(rc[x]);42 if(rnd[rc[x]]rnd[x])lturn(x);43 }44 }45 void getpre(int x){46 if(!x)return;47 if(v[x]V)PREv[x],getpre(rc[x]);else getpre(lc[x]);48 }49 void getaft(int x){50 if(!x)return;51 if(v[x]V)AFTv[x],getaft(lc[x]);else getaft(rc[x]);52 }53 inline void ins(int a,int b){54 e[tot].toob,e[tot].prelast[a],last[a]tot;55 e[tot].tooa,e[tot].prelast[b],last[b]tot;56 }57 58 59 void getrt(int x,int fa){60 sz[x]1,mx[x]0;61 for(int ilast[x];i;ie[i].pre)if(e[i].too!fa!del[e[i].too])62 getrt(e[i].too,x),maxs(mx[x],sz[e[i].too]),sz[x]sz[e[i].too];63 maxs(mx[x],POI-sz[x]);64 if(mx[x]mx[RT])RTx;65 }66 void getpoi(int x,int fa){67 dis[x]dis[fa]1,st[top]x,sz[x]1;68 for(int ilast[x];i;ie[i].pre)if(e[i].too!fa!del[e[i].too])69 getpoi(e[i].too,x),sz[x]sz[e[i].too];70 }71 void work(int x,int dep){72 int i,p;73 RT0,getrt(x,0),xRT,mxdep[x]dep,bel[x][dep]x,dist[x][dep]dis[x]0;74 for(ilast[x];i;ie[i].pre)if(!del[e[i].too]){75 getpoi(e[i].too,x);ID;76 while(top)pst[top--],bel[p][dep]x,belson[p][dep]ID,dist[p][dep]dis[p];77 }78 del[x]1,sz[x]-233;79 for(ilast[x];i;ie[i].pre)if(!del[e[i].too])80 POIsz[e[i].too],work(e[i].too,dep1);81 }82 83 int main(){84 nread();85 for(i1;in;i){86 a[i]read();87 if(i1){88 PREAFT0,Va[i],getpre(rt),getaft(rt),89 insert(rt);90 if(!PRE||!AFT)ins(PRE|AFT,a[i]),u[PRE|AFT][PRE0]1;91 else if(!u[PRE][1])u[PRE][1]1,ins(PRE,a[i]);92 else u[AFT][0]1,ins(AFT,a[i]);93 }else Va[i],insert(rt);94 }95 // for(i1;in;i)for(jlast[i];j;je[j].pre)printf(%d--%d\n,i,e[j].too);96 97 mx[0]130,POIn,work(a[1],1);ll ans0;int fa,son,dis;98 for(i1;in;i){99 ka[i];
100
101 ans_sum[k],_sz[k];
102 for(jmxdep[k]-1;j;j--)
103 fabel[k][j],sonbelson[k][j],disdist[k][j],
104 ans1ll*dis*(_sz[fa]-_sonsz[son])_sum[fa]-_sonsum[son],
105 _sz[fa],_sonsz[son],_sum[fa]dis,_sonsum[son]dis;
106
107 printf(%lld\n,ans);
108 }
109 } View Code 转载于:https://www.cnblogs.com/czllgzmzl/p/5956304.html
