最近看到这样一个题目 但是因为上面的题解实在看不懂证明 故在此寻求大家的帮忙
题目是这样的:
给你一个阵列 一个元素有一个值 会有很多查询[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