线段树内每个节点4个关键域: 最大和线段的左右端点位置,以线段左端点为左端点的最大和线段的右端点位置,以线段右端点为右端点的最大和线段的左端点位置,然后就可以递推了

> 分成logn层，每个都是长的为2^k长度。
> 那么我们每次要查询的段都是logn段
> 那么
> 答案要么在这logn段的某个段内，要么是横跨好几个段的
> 对于第一个问题我们在预处理的时候用nlogn可以做出来
> 第二个问题就相当于是在logn个数中查找最大子段和~这个是o(m)的，m=logn
> 那么每次查询就是O(logn)那么总复杂度就是NlogN
> 
> 线段树会退化吧？感觉是，不太清楚。你说说你具体咋想的

• 怎么递推？我当时想线段树觉得有问题， (90) ACM06060 2007-10-30 14:59:53
  • Re:怎么递推？我当时想线段树觉得有问题， (245) wangfangbob 2007-10-30 15:59:33
    • 。。这和线段树就没什么关系了吧。。直接二分做呗意思~ (269) ACM06060 2007-10-30 18:45:14
      • Re:。。这和线段树就没什么关系了吧。。直接二分做呗意思~ (53) wangfangbob 2007-10-30 20:52:43
        • Re:。。这和线段树就没什么关系了吧。。直接二分做呗意思~ (14) faintzw 2007-10-30 21:22:22
          • Re:。。这和线段树就没什么关系了吧。。直接二分做呗意思~ (10) wangfangbob 2007-10-30 21:38:18
            • 这个贴的形状和题目有关么......... (14) z12y12l12 2007-10-31 16:55:50
              • 哈哈， 有关系 (0) wangfangbob 2007-10-31 17:21:40