哦,比如一个区间[a,b]分成[a,c]和[c,b],那么[a,b]的4个关键域可以被[a,c]和[c,b]的关键域推出来:

比如[a,b]的最大和线段有3种情况:
1,在区间[a,c]里
2,在区间[c,b]里
3,横跨c点,横跨c点的最大和线段是从[a,c]区间的"以线段右端点为右端点的最大和线段的左端
点位置"这个点到[c,b]区间的"以线段左端点为左端点的最大和线段的右端点位置"这个点

然后这3个线段比一下和的大小就行了

其它的3个关键域也类似推出可以

• 。。这和线段树就没什么关系了吧。。直接二分做呗意思~ (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