[PKU 3378]Crazy Thairs(平衡树)

本文主要是介绍[PKU 3378]Crazy Thairs(平衡树)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【题目大意】：

N个数（N<=50000），求5个互相不逆序的数的组合有多少个。

【题目分析】：

这个题的重要的地方在于要统计的是长度为5的正序序列的个数，我们就可以通过正序对个数的求法来类比出来正确的方法。

正序的求法我们是在平衡树中记录size，通过rank操作来进行的。其实进行一下扩展就可以得到正确的方法。我们开4个平衡树，然后rank的含义也随之改变，第一个求的就是以当前节点为尾的长度为2的正序序列的个数。第二个、第三个、第四个以此类推。这样我们就额可以很高效的在四个树上进行rank，其实求解得过程就是一个动态规划的过程，实现的实际上也就是前缀和的操作，这个题的解法其他的解题报告上基本上都是树状数组的方法。但是那种方法因为里面的数没有上界所以必须进行离散化，无疑加大了编程的复杂度。运用平衡树就可以省去这个操作。

因为组合数C(50000,4)这个数他是不超过qword的，但是C(50000,5)超了，所以在最后搞一个高精就可以了（P.s.我高精好长时间没写了，查了好半天原来错在高精上了~）

【代码】：

program PKU_3378; const inf=1000000; type node=record left,right,key,data:longint; chong,size:qword; end; bignum=array[0..100] of longint; var i,n,x:longint; tmp:qword; ans:bignum; root,tot:array[1..4] of longint; tree:array[1..4,0..50001] of node; procedure modify(depth,p:longint); begin tree[depth,p].size:=tree[depth,tree[depth,p].left].size+ tree[depth,tree[depth,p].right].size+ tree[depth,p].chong; end; procedure leftrotate(depth:longint;var p:longint); var t:longint; begin t:=tree[depth,p].left; tree[depth,p].left:=tree[depth,t].right; tree[depth,t].right:=p; modify(depth,p); p:=t; modify(depth,p); end; procedure rightrotate(depth:longint;var p:longint); var t:longint; begin t:=tree[depth,p].right; tree[depth,p].right:=tree[depth,t].left; tree[depth,t].left:=p; modify(depth,p); p:=t; modify(depth,p); end; function rank(x,p,depth:longint):qword; begin if tree[depth,p].data>x then exit(rank(x,tree[depth,p].left,depth)) else if tree[depth,p].data=x then exit(tree[depth,tree[depth,p].left].size) else exit(tree[depth,tree[depth,p].left].size+tree[depth,p].chong+rank(x,tree[depth,p].right,depth)); end; procedure insert(x:longint;var p:longint;depth:longint); begin if p=0 then begin inc(tot[depth]); p:=tot[depth]; tree[depth,p].data:=x; tree[depth,p].key:=random(inf); if depth>1 then tree[depth,p].chong:=rank(x,root[depth-1],depth-1) else tree[depth,p].chong:=1; tree[depth,p].size:=tree[depth,p].chong; tree[depth,p].left:=0; tree[depth,p].right:=0; exit; end else begin if x<tree[depth,p].data then begin insert(x,tree[depth,p].left,depth); if tree[depth,tree[depth,p].left].key<tree[depth,p].key then leftrotate(depth,p); end else if x>tree[depth,p].data then begin insert(x,tree[depth,p].right,depth); if tree[depth,tree[depth,p].right].key<tree[depth,p].key then rightrotate(depth,p); end else if depth>1 then inc(tree[depth,p].chong,rank(x,root[depth-1],depth-1)) else inc(tree[depth,p].chong); modify(depth,p); end; end; procedure add(var x:bignum;y:qword); var xx:bignum; i:longint; begin xx[0]:=0; fillchar(xx,sizeof(xx),0); while y>0 do begin inc(xx[0]); xx[xx[0]]:=y mod 10; y:=y div 10; end; if xx[0]>x[0] then x[0]:=xx[0]; for i:=1 to x[0] do begin x[i]:=x[i]+xx[i]; if x[i]>=10 then begin x[i]:=x[i]-10; x[i+1]:=x[i+1]+1; end; end; if x[x[0]+1]>0 then x[0]:=x[0]+1; end; begin assign(input,'a.in'); assign(output,'a.out'); reset(input); rewrite(output); while not seekeof do begin fillchar(tot,sizeof(tot),0); fillchar(root,sizeof(root),0); fillchar(tree,sizeof(tree),0); fillchar(ans,sizeof(ans),0); readln(n); ans[0]:=1; for i:=1 to n do begin read(x); insert(x,root[1],1); insert(x,root[2],2); insert(x,root[3],3); insert(x,root[4],4); tmp:=rank(x,root[4],4); add(ans,tmp); tmp:=1; end; for i:=ans[0] downto 1 do write(ans[i]); writeln; end; close(input); close(output); end.  

这篇关于[PKU 3378]Crazy Thairs(平衡树)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---