推 suhorng: 对答案二分搜 02/27 23:16
→ suhorng: O(n log n log RANGE), 不能说是 o(n^2) 就是... 02/27 23:18
→ suhorng: http://tioj.ck.tp.edu.tw/problems/1208 这里可以传~ 02/27 23:18
→ suhorng: ^^^^^ 这边不确定一个 log 还两个 log 02/28 02:07
→ FRAXIS: 应该是一个log 没错 02/28 02:21
说到 RANGE
最近刚好有学到一个 fourier transform 的方法 分享一下
时间复杂度是 O(n + RANGE log RANGE)
首先计算前缀和 prefix_sum(x) = a[0] + ... + a[x]
连续和就是 prefix_sum(j) - prefix_sum(i-1) 两数相减的形式
这个东西可以套用 pairwise sum problem
http://en.wikipedia.org/wiki/Pairwise_summation
把第二个阵列头尾颠倒一下，另外扣个常数，就是两数相减的形式了
算法大概是这样：
1. 先用 O(n) 算前缀和
2. 再用 O(n + RANGE) 从循序储存，换成索引储存(counting sort那样子)
3. 跑个 fourier transform 换到频域去算，再换回来，总共 O(RANGE log RANGE)
然后这个板之前有个问题也可以这样解
┌─────────────────────────────────────┐
│ 文章代码(AID): #1FP0xbjA (Prob_Solve) [ptt.cc] [问题] 貌似Facebook面试题 │
│ 文章网址: https://www.ptt.cc/bbs/Prob_Solve/M.1331957477.A.B4A.html │
│ 这一篇文章值 39 Ptt币 │
└─────────────────────────────────────┘