题目：

题解：

import "math/rand"type node struct {ch       [2]*nodepriority intval      int
}func (o *node) cmp(b int) int {switch {case b < o.val:return 0case b > o.val:return 1default:return -1}
}func (o *node) rotate(d int) *node {x := o.ch[d^1]o.ch[d^1] = x.ch[d]x.ch[d] = oreturn x
}type treap struct {root *node
}func (t *treap) _put(o *node, val int) *node {if o == nil {return &node{priority: rand.Int(), val: val}}if d := o.cmp(val); d >= 0 {o.ch[d] = t._put(o.ch[d], val)if o.ch[d].priority > o.priority {o = o.rotate(d ^ 1)}}return o
}func (t *treap) put(val int) {t.root = t._put(t.root, val)
}func (t *treap) lowerBound(val int) (lb *node) {for o := t.root; o != nil; {switch c := o.cmp(val); {case c == 0:lb = oo = o.ch[0]case c > 0:o = o.ch[1]default:return o}}return
}func maxSumSubmatrix(matrix [][]int, k int) int {ans := math.MinInt64for i := range matrix { // 枚举上边界sum := make([]int, len(matrix[0]))for _, row := range matrix[i:] { // 枚举下边界for c, v := range row {sum[c] += v // 更新每列的元素和}t := &treap{}t.put(0)s := 0for _, v := range sum {s += vif lb := t.lowerBound(s - k); lb != nil {ans = max(ans, s-lb.val)}t.put(s)}}}return ans
}func max(a, b int) int {if a > b {return a}return b
}