Xử lý truy vấn trên dãy bằng cách phân tách tại phần tử lớn nhất. Chi phí tối ưu được tính bằng công thức:

\[f(l,r)=\min\left(\sum_{i=l}^{t}h_t + f(t+1,r), \sum_{i=t}^{r}h_t + f(l,t-1)\right)\]

với \(t\) là vị trí phần tử lớn nhất trong đoạn \([l,r]\). Tận dụng cấu trúc cây Descartes:

1. Xây dựng cây Descartes từ dãy chiều cao
2. Quản lý hàm DP \(f_{p,r}\) (chi phí từ biên trái tới \(r\) tại gốc \(p\))

Nhận xét quan trọng:

• Khi \(r\) tăng, chi phí nhánh phải tăng đều \(h_t\)
• Chi phí nhánh trái tăng chậm hơn \(h_t\)
• Thay thế \(\min\) bằng tìm nhị phân điểm chuyển đổi

Cài đặt cây phân đoạn hỗ trợ:

struct SegmentTree {
    struct Node {
        ll val, addTag, slope, base;
        int left, right, len;
        bool isLinear;
    } tree[MAXN * 4];

    void pushLinear(int node, ll k, ll b) {
        tree[node].isLinear = true;
        tree[node].slope = k;
        tree[node].base = b;
        tree[node].val = k * tree[node].len + b;
    }

    void pushAdd(int node, ll delta) {
        tree[node].val += delta;
        if (tree[node].isLinear) 
            tree[node].base += delta;
        else 
            tree[node].addTag += delta;
    }

    void propagate(int node) {
        if (tree[node].isLinear) {
            pushLinear(node->left, tree[node].slope, tree[node].base);
            pushLinear(node->right, tree[node].slope, 
                      tree[node].base + tree[node->left.len * tree[node].slope);
            tree[node].isLinear = false;
        }
        if (tree[node].addTag) {
            pushAdd(node->left, tree[node].addTag);
            pushAdd(node->right, tree[node].addTag);
            tree[node].addTag = 0;
        }
    }

    int findSplit(int node, int L, int R, ll k, ll b) {
        if (L == R) return (tree[node].val >= k + b) ? L : L - 1;
        propagate(node);
        int mid = (L + R) / 2;
        if (tree[left].val >= k * tree[left].len + b) 
            return findSplit(right, mid+1, R, k, k*tree[left].len + b);
        return findSplit(left, L, mid, k, b);
    }

    void updateLinear(int node, int l, int r, ll k, ll b) {
        // Cập nhật đoạn [l,r] thành dãy số học
    }

    void updateAdd(int node, int l, int r, ll delta) {
        // Cộng delta cho toàn đoạn
    }
};

Quy trình xử lý trên cây Descartes:

void processNode(int root) {
    if (!root) return;
    processNode(left[root]);
    processNode(right[root]);
    
    if (!left[root] && !right[root]) {
        segTree.updateLinear(root, root, 0, h[root]);
    } else if (!left[root]) {
        segTree.updateAdd(root, rightBound, h[root]);
    } else {
        ll baseVal = segTree.query(root - 1);
        int pos = segTree.findSplit(root+1, rightBound, h[root], 
                                  baseVal - h[root]*(root - leftBound));
        segTree.updateLinear(root, pos, h[root], baseVal);
        segTree.updateAdd(pos+1, rightBound, h[root]*(root - leftBound + 1));
    }
    
    for (auto query : queries[root]) {
        query.res = segTree.query(query.r);
    }
}

Độ phức tạp: \(O(n \log n)\) nhờ tối ưu hóa cây phân đoạn.