分成logn层，每个都是长的为2^k长度。
那么我们每次要查询的段都是logn段
那么
答案要么在这logn段的某个段内，要么是横跨好几个段的
对于第一个问题我们在预处理的时候用nlogn可以做出来
第二个问题就相当于是在logn个数中查找最大子段和~这个是o(m)的，m=logn
那么每次查询就是O(logn)那么总复杂度就是NlogN

线段树会退化吧？感觉是，不太清楚。你说说你具体咋想的

• Re:见内 (312) wangfangbob 2007-10-30 14:42:56
  • 怎么递推？我当时想线段树觉得有问题， (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