每周编程题 （3/5 - 9/5）

本周推介：
http://www.spoj.com/problems/NBIN/

另外，以下两题只能 TLE，请指教：
A. http://www.spoj.com/problems/IITWPC4D/
B. http://www.spoj.com/problems/BGRAVITY/

遇到困难，请试试睇 TopCoder 教学网页，亦欢迎发问。

常用 SPOJ 题术语解释：
AC - 代表 Accepted，表示答案符合要求，已被接受。WA - 代表 Wrong Answer，表示答案出错。TLE - 代表 Time Limited Exceeded，表示超出时间限制。RTE - 代表 Run Time Error，表示执行时出现错误。

只睇得明第三题

全部明白了

[ 本帖最后由 Susan﹏汪汪 於 2014-5-3 10:44 PM 编辑 ]

解决咗 A 题：IITWPC4D。
先讲测试方法。好简单，只要所有 i， A[ i ] <= i 都成立，就代表有唯一排列方法。
最直观方法：
假设阵列 A 能解。
1. 在阵列 A 中，搵最小值者，如相同，则选最大素引者，假设素引值为 i；
2. 设 H[ i ] = n，n = n - 1；
3. 将阵列 A 内素引大过 i 嘅所有元素减去一；
4. 重复 1，直至 n = 0。

但问题系，以上算法复杂度系 O(n^2)。因 n 最大系 100,000，O(n^2) = O(10^10)，只能 TLE。
好明显，要及时完成，必须搵到一个 O(n log n) 或更好嘅算法。

我利用线段树(segment tree)，使到直观方法中步骤一及三，复杂度由 O(n) 变成 O(log n)。
实作步骤一并不困难，只要每个树节点内 (val, idx)，记载住子树嘅最小值(val)，相同取最大素引者(idx)。
树根内嘅 idx，就系之前方法所讲嘅 i。
实作步骤三就须要在节点中，加入一个栏 acc，用作表示此节点及两棵子树，都须要将值减去它 (val - acc)，来计算真正嘅值。
受影响嘅节点，将 acc 加一。利用线段树特性，此动作只须更新 O(log n) 节点。
然后，将㨂选嘅 idx 相关节点（叶），改值为无限大，并由此向上更新整棵树。

我嘅完成时间并不理想，只系 1.25s，21 个人中排 18。
我谂系因为比我快嘅人，能将步骤一及三合拼，又或使用更高效率嘅数据结构。
至於点样做到，留番畀呢度嘅高人指点。