最近看到這樣一個題目 但是因為上面的題解實在看不懂證明 故在此尋求大家的幫忙
題目是這樣的:
給你一個陣列 一個元素有一個值 會有很多查詢[i,j] 請給出[i,j]內最大的
陣列元素和範圍 [a,b] (N 個元素, M次查詢)
一般最大子序列和有linear time算法, 但是這邊有M次查詢 所有複雜度為O(MN)
我看的那篇經過NlogN预處理 每次查詢只須 O(1) 所以總查詢時間為 O(M)
(以下說明index從1開始)
他是先求出
C[k] = Sum(1,k) ,
P[k] = 以k為結尾, 以1~k為開頭的最大子陣列和的左下標 (就是前面的a)
e.g: max( sum(1,k) , sum(2,k), ...., sum(k,k) )
M[k] = Sum(P[k],k)
下面就是根本看不懂推理過程的東西了:
然後對每次查詢 [i,j] , 先用RMQ得出 r , 此R使得M[r]為在[i,j]區間之最大M[..]值
若是P[R] >= i 則為所求
若是P[R] < i 則對於區間 [i-1, r-1] 以及 [r+1, j] 再作RMQ後取其大者 .....
後面就不多打了 首先看不懂為什麼 P[R] < i 之後可以分成那兩個區間
不知道是因為 "trivial"還是怎樣, 並沒有給出理由說為什麼答案可從那邊得到
而且不知道為什麼是 r-1 r+1 ==> 跳過r ?
不知道大家有沒有看過類似的說明 或是能幫忙解答這邊的理由
這提是 GDOI 2005的題目......先謝謝大家惹......
ORZ