3691. Maximum Total Subarray Value II

class SparseTableRMQ {
    int n;
    int maxLog;
    int[][] fMax;
    int[][] fMin;
    int[] lg;

    public SparseTableRMQ(int[] data) {
        n = data.length;
        maxLog = 32 - Integer.numberOfLeadingZeros(n) + 1;

        fMax = new int[n][maxLog];
        fMin = new int[n][maxLog];
        lg = new int[n + 1];

        for (int i = 2; i <= n; i++) {
            lg[i] = lg[i >> 1] + 1;
        }

        for (int i = 0; i < n; i++) {
            fMax[i][0] = data[i];
            fMin[i][0] = data[i];
        }

        for (int j = 1; j < maxLog; j++) {
            for (int i = 0; i <= n - (1 << j); i++) {
                fMax[i][j] = Math.max(
                        fMax[i][j - 1],
                        fMax[i + (1 << (j - 1))][j - 1]);

                fMin[i][j] = Math.min(
                        fMin[i][j - 1],
                        fMin[i + (1 << (j - 1))][j - 1]);
            }
        }
    }

    public int queryMax(int l, int r) {
        int k = lg[r - l + 1];
        return Math.max(
                fMax[l][k],
                fMax[r - (1 << k) + 1][k]);
    }

    public int queryMin(int l, int r) {
        int k = lg[r - l + 1];
        return Math.min(
                fMin[l][k],
                fMin[r - (1 << k) + 1][k]);
    }
}

class Solution {

    public long maxTotalValue(int[] nums, int k) {

        int n = nums.length;

        SparseTableRMQ st = new SparseTableRMQ(nums);

        PriorityQueue<long[]> pq =
                new PriorityQueue<>((a, b) -> Long.compare(b[0], a[0]));

        for (int l = 0; l < n; l++) {
            long val =
                    (long) st.queryMax(l, n - 1)
                            - st.queryMin(l, n - 1);

            pq.offer(new long[]{val, l, n - 1});
        }

        long ans = 0;

        for (int i = 0; i < k; i++) {

            long[] cur = pq.poll();

            long val = cur[0];
            int l = (int) cur[1];
            int r = (int) cur[2];

            ans += val;

            if (r > l) {

                long nextVal =
                        (long) st.queryMax(l, r - 1)
                                - st.queryMin(l, r - 1);

                pq.offer(new long[]{nextVal, l, r - 1});
            }
        }

        return ans;
    }
}

import heapq

class SparseTableRMQ:
    def __init__(self, nums):
        self.n = len(nums)
        self.log = [0] * (self.n + 1)

        for i in range(2, self.n + 1):
            self.log[i] = self.log[i // 2] + 1

        k = self.log[self.n] + 1

        self.mx = [[0] * self.n for _ in range(k)]
        self.mn = [[0] * self.n for _ in range(k)]

        for i in range(self.n):
            self.mx[0][i] = nums[i]
            self.mn[0][i] = nums[i]

        j = 1
        while (1 << j) <= self.n:
            length = 1 << j
            half = length >> 1

            for i in range(self.n - length + 1):
                self.mx[j][i] = max(
                    self.mx[j - 1][i],
                    self.mx[j - 1][i + half]
                )

                self.mn[j][i] = min(
                    self.mn[j - 1][i],
                    self.mn[j - 1][i + half]
                )

            j += 1

    def queryMax(self, l, r):
        j = self.log[r - l + 1]
        return max(
            self.mx[j][l],
            self.mx[j][r - (1 << j) + 1]
        )

    def queryMin(self, l, r):
        j = self.log[r - l + 1]
        return min(
            self.mn[j][l],
            self.mn[j][r - (1 << j) + 1]
        )


class Solution:
    def maxTotalValue(self, nums, k):

        n = len(nums)
        st = SparseTableRMQ(nums)

        pq = []

        for l in range(n):
            val = st.queryMax(l, n - 1) - st.queryMin(l, n - 1)
            heapq.heappush(pq, (-val, l, n - 1))

        ans = 0

        for _ in range(k):
            val, l, r = heapq.heappop(pq)
            ans += -val

            if r > l:
                nxt = st.queryMax(l, r - 1) - st.queryMin(l, r - 1)
                heapq.heappush(pq, (-nxt, l, r - 1))

        return ans

class SparseTableRMQ {
public:
    int n;
    vector<int> lg;
    vector<vector<int>> mx, mn;

    SparseTableRMQ(vector<int>& nums) {
        n = nums.size();

        lg.resize(n + 1);

        for (int i = 2; i <= n; i++)
            lg[i] = lg[i / 2] + 1;

        int K = lg[n] + 1;

        mx.assign(K, vector<int>(n));
        mn.assign(K, vector<int>(n));

        for (int i = 0; i < n; i++) {
            mx[0][i] = nums[i];
            mn[0][i] = nums[i];
        }

        for (int j = 1; j < K; j++) {
            for (int i = 0; i + (1 << j) <= n; i++) {
                mx[j][i] = max(mx[j-1][i], mx[j-1][i+(1<<(j-1))]);
                mn[j][i] = min(mn[j-1][i], mn[j-1][i+(1<<(j-1))]);
            }
        }
    }

    int queryMax(int l,int r){
        int j = lg[r-l+1];
        return max(mx[j][l], mx[j][r-(1<<j)+1]);
    }

    int queryMin(int l,int r){
        int j = lg[r-l+1];
        return min(mn[j][l], mn[j][r-(1<<j)+1]);
    }
};

class Solution {
public:
    long long maxTotalValue(vector<int>& nums, int k) {

        int n = nums.size();

        SparseTableRMQ st(nums);

        priority_queue<vector<long long>> pq;

        for(int l=0;l<n;l++){

            long long val=
            st.queryMax(l,n-1)-st.queryMin(l,n-1);

            pq.push({val,l,n-1});
        }

        long long ans=0;

        while(k--){

            auto cur=pq.top();
            pq.pop();

            long long val=cur[0];
            int l=cur[1];
            int r=cur[2];

            ans+=val;

            if(r>l){

                long long nxt=
                st.queryMax(l,r-1)-st.queryMin(l,r-1);

                pq.push({nxt,l,r-1});
            }
        }

        return ans;
    }
};

class SparseTableRMQ {

    constructor(nums){

        this.n=nums.length;

        this.log=new Array(this.n+1).fill(0);

        for(let i=2;i<=this.n;i++)
            this.log[i]=this.log[i>>1]+1;

        let K=this.log[this.n]+1;

        this.mx=Array.from({length:K},()=>Array(this.n).fill(0));
        this.mn=Array.from({length:K},()=>Array(this.n).fill(0));

        for(let i=0;i<this.n;i++){
            this.mx[0][i]=nums[i];
            this.mn[0][i]=nums[i];
        }

        for(let j=1;j<K;j++){

            for(let i=0;i+(1<<j)<=this.n;i++){

                this.mx[j][i]=Math.max(
                    this.mx[j-1][i],
                    this.mx[j-1][i+(1<<(j-1))]
                );

                this.mn[j][i]=Math.min(
                    this.mn[j-1][i],
                    this.mn[j-1][i+(1<<(j-1))]
                );
            }
        }
    }

    queryMax(l,r){

        let j=this.log[r-l+1];

        return Math.max(
            this.mx[j][l],
            this.mx[j][r-(1<<j)+1]
        );
    }

    queryMin(l,r){

        let j=this.log[r-l+1];

        return Math.min(
            this.mn[j][l],
            this.mn[j][r-(1<<j)+1]
        );
    }
}

class MaxHeap{

    constructor(){
        this.data=[];
    }

    push(x){
        this.data.push(x);
        this.data.sort((a,b)=>b[0]-a[0]);
    }

    pop(){
        return this.data.shift();
    }
}

var maxTotalValue=function(nums,k){

    const n=nums.length;

    const st=new SparseTableRMQ(nums);

    const pq=new MaxHeap();

    for(let l=0;l<n;l++){

        let val=
        st.queryMax(l,n-1)-st.queryMin(l,n-1);

        pq.push([val,l,n-1]);
    }

    let ans=0;

    while(k--){

        let [val,l,r]=pq.pop();

        ans+=val;

        if(r>l){

            let nxt=
            st.queryMax(l,r-1)-st.queryMin(l,r-1);

            pq.push([nxt,l,r-1]);
        }
    }

    return ans;
};