HackerRank Sum of the Maximums problem solution

In this HackerRank Sum of the Maximums problem, we have given an array of n integers. and we need to calculate the sum of the maximum values for all subsegments of the array.

Problem solution in Java Programming.

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.InputMismatchException;

public class G3X {
    InputStream is;
    PrintWriter out;
    String INPUT = "";
    
    void solve()
    {
        int n = ni(), Q = ni();
        int[] a = na(n);
        int[][] qs = new int[Q][];
        for(int i = 0;i < Q;i++){
            qs[i] = new int[]{ni()-1, ni()-1, i};
        }
        
        int[] L = enumPrevWall(a);
        int[] R = enumPrevWall2(rev(a));

        rev(a);
        int[][] reaches = new int[n][];
        for(int i = 0;i < n;i++){
            reaches[i] = new int[]{L[i]+1, n-1-R[n-1-i]-1, i, a[i]};

        }
        
        int[][] lqs = Arrays.copyOf(qs, Q);
        Arrays.sort(lqs, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                return a[1] - b[1];
            }
        });
        int[] inds = new int[Q];
        int[] iinds = new int[Q];
        int[] ys = new int[Q];
        for(int i = 0;i < Q;i++)inds[i] = lqs[i][2];
        for(int i = 0;i < Q;i++)ys[i] = lqs[i][1];
        for(int i = 0;i < Q;i++)iinds[inds[i]] = i;
        
        int[] lb = new int[n+2];
        int lp = 0;
        for(int i = 0;i <= n+1;i++){
            while(lp < ys.length && ys[lp] < i)lp++;
            lb[i] = lp;
        }
        
        long[] ret = new long[Q];
        {
            int[][] es = new int[3*n+Q][];
            for(int i = 0;i < n;i++){
                es[i] = reaches[i];
                es[n+i] = new int[]{Math.max(0, reaches[i][0]+1), Math.min(reaches[i][1]-1, i-1), i, -a[i]};
                es[2*n+i] = new int[]{Math.max(i+1, reaches[i][0]+1), 
                        Math.min(n, reaches[i][1]-1), i, -a[i]};
                reaches[i][0]++;
                reaches[i][1]--;
            }
            for(int i = 0;i < Q;i++){
                es[3*n+i] = qs[i];
            }
            
            Arrays.sort(es, new Comparator<int[]>() {
                public int compare(int[] a, int[] b) {
                    if(a[0] != b[0])return -(a[0] - b[0]);
                    if(a[1] != b[1])return a[1] - b[1];
                    return a.length - b.length;
                }
            });
            
            
            long[] ft2 = new long[Q+3];
            long[] ft1 = new long[Q+3];
            long[] ft0 = new long[Q+3];
            long sft2 = 0, sft1 = 0, sft0 = 0;
            for(int[] e : es){
                if(e.length == 4){
                    int ind = lb[e[1]+1];

                    sft2 += -(long)e[3]*e[2]*e[2];
                    addFenwick(ft2, ind, (long)e[3]*e[2]*e[2]);
                    sft1 += (long)e[3]*e[2];
                    addFenwick(ft1, ind, -(long)e[3]*e[2]);
                    sft0 += (long)e[3];
                    addFenwick(ft0, ind, -e[3]);
                }else{

                    ret[e[2]] -= 
                            (sft2 + sumFenwick(ft2, iinds[e[2]])) +
                            (sft1 + sumFenwick(ft1, iinds[e[2]])) * (qs[e[2]][1]+qs[e[2]][0]) +
                            (sft0 + sumFenwick(ft0, iinds[e[2]])) * (qs[e[2]][1]+1) * (-qs[e[2]][0] + 1);
                }
            }
            for(int i = 0;i < Q;i++){
                ret[i] += 
                        (sft2 + sumFenwick(ft2, iinds[i])) +
                        (sft1 + sumFenwick(ft1, iinds[i])) * (qs[i][1]+qs[i][0]) +
                        (sft0 + sumFenwick(ft0, iinds[i])) * (qs[i][1]+1) * (-qs[i][0] + 1);
            }
            for(int i = 0;i < n;i++){
                reaches[i][0]--;
                reaches[i][1]++;
            }
        }

        
        {
            int[][] es = new int[2*n+Q][];
            for(int i = 0;i < n;i++){
                es[i] = reaches[i];
                es[n+i] = new int[]{i+1, reaches[i][1], i, -a[i]};
                reaches[i][0]++;
            }
            for(int i = 0;i < Q;i++){
                es[2*n+i] = qs[i];
            }
            
            Arrays.sort(es, new Comparator<int[]>() {
                public int compare(int[] a, int[] b) {
                    if(a[0] != b[0])return -(a[0] - b[0]);
                    if(a[1] != b[1])return -(a[1] - b[1]);
                    return a.length - b.length;
                }
            });
            

            long[] ft1 = new long[Q+3];
            long[] ft0 = new long[Q+3];
            for(int[] e : es){
                if(e.length == 4){
                    int ind = lb[e[1]];

                    addFenwick(ft1, ind, -(long)e[3]*(e[1]-e[2]+1));
                    addFenwick(ft0, ind, (long)e[3]*(e[1]-e[2]+1)*(e[2]+1));
                }else{
                    ret[e[2]] -= 
                            sumFenwick(ft1, iinds[e[2]]) * qs[e[2]][0] +
                            sumFenwick(ft0, iinds[e[2]]);
                }
            }
            long[] imos1 = dominatorFenwick(ft1);
            long[] imos0 = dominatorFenwick(ft0);
            for(int i = 0;i < Q;i++){
                ret[i] += imos1[iinds[i]] * qs[i][1] + imos0[iinds[i]];
            }

            for(int i = 0;i < n;i++){
                reaches[i][0]--;
            }
        }

        {
            int[][] es = new int[2*n+Q][];
            for(int i = 0;i < n;i++){
                es[i] = reaches[i];
                es[n+i] = new int[]{reaches[i][0], i-1, i, -a[i]};
                reaches[i][1]--;
            }
            for(int i = 0;i < Q;i++){
                es[2*n+i] = qs[i];
            }
            
            Arrays.sort(es, new Comparator<int[]>() {
                public int compare(int[] a, int[] b) {
                    if(a[0] != b[0])return (a[0] - b[0]);
                    if(a[1] != b[1])return (a[1] - b[1]);
                    return a.length - b.length;
                }
            });
            

            long[] ft1 = new long[Q+3];
            long[] ft0 = new long[Q+3];
            long sft1 = 0, sft0 = 0;
            for(int[] e : es){
                if(e.length == 4){
                    int ind = lb[e[1]+1];

                    sft1 += (long)e[3]*(e[2]-e[0]+1);
                    addFenwick(ft1, ind, -(long)e[3]*(e[2]-e[0]+1));
                    sft0 += (long)e[3]*(e[2]-e[0]+1)*(-e[2]+1);
                    addFenwick(ft0, ind, -(long)e[3]*(e[2]-e[0]+1)*(-e[2]+1));
                }else{
                    ret[e[2]] -= 
                            (sft1 + sumFenwick(ft1, iinds[e[2]])) * qs[e[2]][1] +
                            (sft0 + sumFenwick(ft0, iinds[e[2]]));
                }
            }
            long[] imos1 = dominatorFenwick(ft1);
            long[] imos0 = dominatorFenwick(ft0);
            for(int i = 0;i < Q;i++){
                ret[i] += (sft1 + imos1[iinds[i]+1]) * qs[i][1] + sft0 + imos0[iinds[i]+1];
            }
            for(int i = 0;i < n;i++){
                reaches[i][1]++;
            }
        }
        
        {
            long[] es = new long[n+Q];
            for(int i = 0;i < n;i++){
                es[i] = (long)n+1-reaches[i][0]<<40|(long)reaches[i][1]<<20|0<<19|i;
            }
            for(int i = 0;i < Q;i++){
                es[n+i] = (long)n+1-qs[i][0]<<40|(long)qs[i][1]<<20|1<<19|i;
            }
            
            Arrays.sort(es);
            
            long[] nft = new long[Q+3];
            for(long e : es){
                long e0 = n+1-(e>>>40);
                long e1 = e>>>20&(1L<<20)-1;
                long e2 = e&(1L<<19)-1;
                if(e<<~19>=0){
                    long e3 = a[(int)e2];
                    int ind = lb[(int)e1];
                    addFenwick(nft, ind, (long)e3*(e1-e2+1)*(e2-e0+1));
                }else{
                    ret[(int)e2] += sumFenwick(nft, iinds[(int)e2]);
                }
            }
        }

        for(long v : ret){
            out.println(v);
        }
    }
    
    public static long[] dominatorFenwick(long[] ft)
    {
        int n = ft.length;
        long[] imos = new long[n];
        for(int i = 1;i <= n-1;i++){
            imos[i] += ft[i];
            imos[Math.min(n-1, i+(i&-i))] -= ft[i];
        }
        for(int i = 0;i <= n-2;i++){
            imos[i+1] += imos[i];
        }
        return imos;
    }
    
    public static int lowerBound(int[] a, int v)
    {
        int low = -1, high = a.length;
        while(high-low > 1){
            int h = high+low>>>1;
            if(a[h] >= v){
                high = h;
            }else{
                low = h;
            }
        }
        return high;
    }
    
    public static long sumFenwick(long[] ft, int i)
    {
        long sum = 0;
        for(i++;i > 0;i -= i&-i)sum += ft[i];
        return sum;
    }
    
    public static void addFenwick(long[] ft, int i, long v)
    {
        if(v == 0)return;
        int n = ft.length;
        for(i++;i < n;i += i&-i)ft[i] += v;
    }

    
    public static int[] rev(int... a){ for(int i = 0, j = a.length-1;i < j;i++,j--){ int d = a[i]; a[i] = a[j]; a[j] = d;}return a; }
    
    public static int[] enumPrevWall(int[] a)
    {
        int n = a.length;
        int[] L = new int[n];
        for(int i = 0;i < n;i++){
            L[i] = i-1;
            while(L[i] >= 0 && a[L[i]] < a[i])L[i] = L[L[i]];
        }
        return L;
    }
    
    public static int[] enumPrevWall2(int[] a)
    {
        int n = a.length;
        int[] L = new int[n];
        for(int i = 0;i < n;i++){
            L[i] = i-1;
            while(L[i] >= 0 && a[L[i]] <= a[i])L[i] = L[L[i]];
        }
        return L;
    }
    
    void run() throws Exception
    {
        is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
        out = new PrintWriter(System.out);
        
        long s = System.currentTimeMillis();
        solve();
        out.flush();
        if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
    }
    
    public static void main(String[] args) throws Exception { new G3X().run(); }
    
    private byte[] inbuf = new byte[1024];
    private int lenbuf = 0, ptrbuf = 0;
    
    private int readByte()
    {
        if(lenbuf == -1)throw new InputMismatchException();
        if(ptrbuf >= lenbuf){
            ptrbuf = 0;
            try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
            if(lenbuf <= 0)return -1;
        }
        return inbuf[ptrbuf++];
    }
    
    private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
    private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
    
    private double nd() { return Double.parseDouble(ns()); }
    private char nc() { return (char)skip(); }
    
    private String ns()
    {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    
    private char[] ns(int n)
    {
        char[] buf = new char[n];
        int b = skip(), p = 0;
        while(p < n && !(isSpaceChar(b))){
            buf[p++] = (char)b;
            b = readByte();
        }
        return n == p ? buf : Arrays.copyOf(buf, p);
    }
    
    private char[][] nm(int n, int m)
    {
        char[][] map = new char[n][];
        for(int i = 0;i < n;i++)map[i] = ns(m);
        return map;
    }
    
    private int[] na(int n)
    {
        int[] a = new int[n];
        for(int i = 0;i < n;i++)a[i] = ni();
        return a;
    }
    
    private int ni()
    {
        int num = 0, b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }
        
        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
    
    private long nl()
    {
        long num = 0;
        int b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }
        
        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
    
    private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}

Problem solution in C++ programming.

#include<bits/stdc++.h>
 
using namespace std;
 
typedef pair<int,int>   II;
typedef vector< II >      VII;
typedef vector<int>     VI;
typedef vector< VI >    VVI;
typedef long long int   LL;
 
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(a) (int)(a.size())
#define ALL(a) a.begin(),a.end()
#define SET(a,b) memset(a,b,sizeof(a))
 
#define si(n) scanf("%d",&n)
#define dout(n) printf("%d\n",n)
#define sll(n) scanf("%lld",&n)
#define lldout(n) printf("%lld\n",n)
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
 
#define TRACE
 
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
 
//FILE *fin = freopen("in","r",stdin);
//FILE *fout = freopen("out","w",stdout);
 
const int N = int(1.35*1e5)+10;
const int SQRT = 400;
LL A[N],dp[N],dp2[N],PS[N],ans[N],dp3[N];
int st[N],top,arr[N],len,st2[N],top2;
VI B[N];
struct query{
  int l,r;
}Q[N];
bool cmp(int i,int j){
  return Q[i].r < Q[j].r;
}
LL get2(int ll,int rr,int n,int L,int len){
  LL ret = 0;assert(len>0);LL mx = -int(1e9);
  for(int i=rr;i>=ll;i--){
    mx = max(mx,A[i]);
    if(mx >= A[arr[len]]){ret += mx*(n + 1 - L);continue;}
    int l = 1, h = len, ans = 0;
    while(l<=h){
      int m = (l+h)/2;
      if(A[arr[m]] >= mx){ans = m;h = m-1;}
      else l = m+1;
    }
    ret += (mx*(arr[ans]-L));
    ret += PS[len]-PS[ans-1];
  }
  return ret;
}
LL get(int l,int r){
  LL ret = 0;top2=0;
  int R = l;
  while(R <= r){
    while(top2 && A[st2[top2]] <= A[R])top2--;
    int lpos = (top2?st2[top2]:l-1);
    dp3[R] = (R -lpos)*A[R] + (top2?dp3[lpos]:0);
    st2[++top2]=R;
    ret+=dp3[R];
    R++;
  }
  return ret;
}
int main()
{
  int n,q;
  si(n);si(q);
  for(int i=1;i<=n;i++)sll(A[i]);
  for(int i=1;i<=q;i++){
    si(Q[i].l);si(Q[i].r);
    B[Q[i].l/SQRT].PB(i);
  }
  for(int i=0;i<N;i++){
    sort(ALL(B[i]),cmp);
    int L = (i+1)*SQRT, R = L;top = len = 0;
    LL add = 0;
    for(int j=0;j<SZ(B[i]);j++){
      int idx = B[i][j];
      int l = Q[idx].l,r = Q[idx].r;
      ans[idx] = get(l,min(r,L-1));
      if(r<L)continue;
      while(R <= r){
        while(top && A[st[top]] <= A[R])top--;
        int lpos = (top?st[top]:L-1);
        dp2[R] = (R -lpos)*A[R] + (top?dp2[lpos]:0);
        st[++top] = R;
        if(!len || A[R]>A[arr[len]]){
          if(len){
            dp[arr[len]] = (R - arr[len])*A[arr[len]];
            PS[len] = PS[len-1] + dp[arr[len]];
          }
          arr[++len]=R;
          dp[R] = (r - R + 1)*A[R];
          PS[len] = PS[len-1] + dp[R];
        }
        add += dp2[R];R++;
      }
      dp[arr[len]] = (r - arr[len] + 1)* A[arr[len]];
      PS[len] = PS[len-1] + dp[arr[len]];
      ans[idx] += add;
      ans[idx] += get2(l,L-1,r,L,len);
    }
  }
  for(int i=1;i<=q;i++)
    lldout(ans[i]);
  return 0;
}

Problem solution in C programming.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


unsigned floor_square_root(unsigned self) {
    
    unsigned
        root = 0,
        length = self;

    while (length > 1)
        if ((root * root + length * ((length >> 2) + root)) < self) {
            root += length >> 1;
            length -= length >> 1;
        } else
            length >>= 1;

    return root;
}

unsigned floor_log2(unsigned self) {
    static const unsigned de_bruijn[] = {
        0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
        8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
    };

    self |= self >> 1;
    self |= self >> 2;
    self |= self >> 4;
    self |= self >> 8;
    self |= self >> 16;

    return de_bruijn[(self * 0x07C4ACDDU) >> 27];
}

static inline unsigned arg_max(
    unsigned length,
    unsigned log2_limit,
    unsigned (*max)[length][log2_limit],
    long *weights,
    unsigned low,
    unsigned high
) {
    unsigned length_log2 = floor_log2(high - low + 1);
    return max[0][
        ((weights[max[0][low][length_log2]] > weights[max[0][(high - (1U << length_log2) + 1)][length_log2]])
            ? low : (high - (1U << length_log2) + 1))
    ][length_log2];
}

int main(int argc, const char * argv[]) {
    unsigned at, others, count, query_cnt;
    scanf("%u %u", &count, &query_cnt);

    long items[count + 2];
    for (at = 1; at <= count; scanf("%ld", &items[at++]));

    unsigned
        history[count + 1],
        log2_limit = floor_log2(count + 1) + 1;

    unsigned (*max)[count + 1][log2_limit] = malloc(sizeof(unsigned) * (count + 1) * log2_limit);
    for (at = 0; ++at <= count; max[0][at][0] = at);

    unsigned log2_length;
    for (log2_length = 0; (log2_length + 1) < log2_limit; log2_length++)
        for (at = 0; (++at + (1 << log2_length)) <= count;
             max[0][at][log2_length + 1] = max[0][at +
                ((items[max[0][at][log2_length]] < items[max[0][at + (1U << log2_length)][log2_length]])
                    << log2_length)
            ][log2_length]);

    long
        end_sums[count + 2],
        start_sums[count + 2];

    unsigned
        left_greater[count + 1],
        right_greater[count + 1];

    items[history[0] = 0] = 0x7FFFFFFFFFFFFFFFL;
    end_sums[0] = 0;
    for (others = (at = 1); at <= count; history[others++] = at++) {
        for (; items[history[others - 1]] <= items[at]; others--);
        left_greater[at] = history[others - 1];

        end_sums[at] = items[at] * (at - left_greater[at]) + end_sums[left_greater[at]];
    }

    items[history[0] = (count + 1)] = 0x7FFFFFFFFFFFFFFFL;
    start_sums[count + 1] = 0;
    for (others = 1; --at; history[others++] = at) {
        for (; items[history[others - 1]] <= items[at]; others--);
        right_greater[at] = history[others - 1];

        start_sums[at] = items[at] * (right_greater[at] - at) + start_sums[right_greater[at]];
    }

    unsigned
        block_length = floor_square_root(count + 1);

    long
        total,
        spans[((count + 1) / block_length) + 1][((count + 1) / block_length) + 1];

    memset(spans, 0, sizeof(spans));
    for (at = 1; at <= count; at += block_length) {
        long sums[count + 1];
        total = 0;

        for (others = at; others <= count; others++) {
            sums[others]
                = (left_greater[others] < at)
                ? (items[others] * (others - at + 1))
                : (items[others] * (others - left_greater[others]) + sums[left_greater[others]]);

            total += sums[others];
            if ((others % block_length) == 0)
                spans[at / block_length][others / block_length] = total;
        }
    }

    unsigned low, high;
    for (; query_cnt--; printf("%ld\n", total + spans[low / block_length][high / block_length])) {
        scanf("%u %u", &low, &high);

        for (total = 0; high % block_length && high >= low; high--)
            if (left_greater[high] < low)
                total += items[high] * (high - low + 1);
            else {
                others = arg_max(count + 1, log2_limit, max, items, low, high);
                total += end_sums[high] - end_sums[others] + items[others] * (others - low + 1);
            }

        for (; (low % block_length) != 1 && low <= high; low++)
            if (right_greater[low] > high)
                total += items[low] * (high - low + 1);
            else {
                others = arg_max(count + 1, log2_limit, max, items, low, high);
                total += start_sums[low] - start_sums[others] + items[others] * (high - others + 1);
            }
    }

    return 0;
}