Algorithm
Problem Name: Data Structures -
In this HackerRank in Data Structures -
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.
Code Examples
#1 Code Example with C Programming
Code -
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;
}
#2 Code Example with C++ Programming
Code -
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;
}
#3 Code Example with Java Programming
Code -
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)>; }
}