3378专题

[PKU 3378]Crazy Thairs(平衡树)

【题目大意】: N个数(N<=50000),求5个互相不逆序的数的组合有多少个。 【题目分析】: 这个题的重要的地方在于要统计的是长度为5的正序序列的个数,我们就可以通过正序对个数的求法来类比出来正确的方法。 正序的求法我们是在平衡树中记录size,通过rank操作来进行的。其实进行一下扩展就可以得到正确的方法。我们开4个平衡树,然后rank的含义也随之改变,第一个求的就是以当前节点为尾的