第二部分解题报告

1、 解题华东师范大学第二附属中学【时空限制】每个测试点时限 秒，空间限制无。【问题描述】有 棵树从 到 标号。现要把这些树种在一条直线上，第 棵树的种植位置 如下确定： ； 。每棵树种植的费用，是所有标号比它小的树与它的距离之和。计算各棵树费用之积，模。【数据规模和约定】N,L200000; 【试题】如果朴素地解决此问题，时间复杂度将为 ，这是不能接受的。必须降低每次计算费用的代价。注意到第 棵树的费用，尝试将绝对值拆开，则有从而容易发现，只需要一种数据结构，能够查询一段区域内的数据个数及其和即可，这可以用线段树、树状数组、平衡二叉查找树等实现。具体地，以线段树为例。按标号从小到大计算树的费用。

2、计算树 的费用时，分别查询两侧的树的个数及距离和，计算得出费用。最后将 线段树，相关值。【算法描述】建立线段树。按标号从小到大计算树的费用。计算树 的费用时，首先查询 左侧所有树的个数 及位置之和 ，则 即为树 左侧标号比 小的树到树 的距离之后。同理求得 为右侧距离和，相加即得树 费用。然后将 线段树，相关值。此算法每次查询和每次的时间复杂度均为 ，故总时间复杂度为 。【其他算法】本题还有一些算法，通过让数据结构不同的值来解决问题，例如线段树中结点区间内所有点到左、右端点距离之和等等。这些算法和上述算法的本质相同，此处不再赘述。【实现情况】实现情况【感谢】感谢 在 er上提供的题解。【附录】

3、原题Problem SementThere are N trees numbered 0 to N-1, and you must plant them along a straight line. Tree i will be planted atcoordinate Xi, where X is constructed using the following recursive definition:X0 = X0 MOD LXi = (Xi-1*A+B) MOD L (notet Xi-1*A+B may overflow a 32-biteger)The price of planti

4、ng tree i is the sum of the distanbetn tree i and each tree numbered lessn i.Calculate the product of the pri1,000,000,007.of all the trees (except tree 0), and return this number moduloDefinitionClass:ProductOfPriMethod:productParameters:,Returns:Method signature:product(N,L,X0,A,B)(be sure your me

5、thod is public)Constras-N will be betn 2 and 200,000, inclusive.-L will be betn 1 and 200,000, inclusive.-X0,A,B will each be betn 0 and 1,000,000,000, inclusive.Exles0)510311Returns: 180The trees are planted atitions: 3, 4, 5, 6, 7. Their priare (starting from tree 1): 1, 3, 6, 10. Theproduct of priis 1 * 3 * 6 * 10 = 180.1)320523Returns: 642)421171Returns: 30873)1010043711Returns: 5918607674)5200000999999999123456789987654321Returns: 499739175This problem sement is the exclusive and proprietary property of TopCoder, Inc.Any unauthorized use or reproduction of this information witho