本题有一种很形象的解法，在[l,r]上种树可以表示为在l处添加一个左括号，在r处添加一个右括号。求[l,r]之间种的树的种类数即[1,r]中左括号的数量-[1,l-1]中右括号的数量。而求和操作可以利用树状数组在O(logn)的时间复杂度内完成，所以总的时间复杂度是O(mlogn)。
注意在种树时要维护的数组变量的元素的下标在计算中有可能会超过word的范围，要用longint。之前没发现这一点，以为是Vijos对writeln处理的bug导致最后两个点超时多交了几次。
R1185426 Accepted 100 From IwfWcf－ P1448 FPC Vivid Puppy 2009-3-23 23:50:35
帖子
0 评论:
发表评论