# Sum of the Maximums

### Problem Statement :

```Alexey is playing with an array, , of  integers. His friend, Ivan, asks him to calculate the sum of the maximum values for all subsegments of . More formally, he wants Alexey to find .

Alexey solved Ivan's challenge faster than expected, so Ivan decides to add another layer of difficulty by having Alexey answer  queries. The  query contains subsegment , and he must calculate the sum of maximum values on all subsegments inside subsegment .

More formally, for each query , Alexey must calculate the following function:

.

Can you help Alexey solve this problem?

Input Format

The first line contains  space-separated positive integers,  (the length of array ) and  (number of queries), respectively.
The second line contains  space-separated integers,  describing each element  (where ) in array .
Each of the  subsequent lines contains  space-separated positive integers describing the respective values for  and  in query  (where ).

Output Format

For each query  i (where 0  <= i  < m ), print its answer on a new line.```

### Solution :

```                            ```Solution in C :

In   C++  :

#include <bits/stdc++.h>

using namespace std;

#define sz(x) ((int) (x).size())
#define forn(i,n) for (int i = 0; i < int(n); ++i)
#define forab(i,a,b) for (int i = int(a); i < int(b); ++i)

typedef long long ll;
typedef long long i64;
typedef long double ld;

typedef __int128 Big;

typedef pair<Big, Big> pii;

const int inf = int(1e9) + int(1e5);
const ll infl = ll(2e18) + ll(1e10);

void add(pii &a, pii b) {
a.first += b.first, a.second += b.second;
}

const int base = 1 << 18; //135000 suka blya

pii t[base * 2];
pii upd[base * 2];

pii mul(pii a, Big b) {
return {a.first * b, a.second * b};
}

void push(int v, int len) {
add(t[v * 2 + 1], mul(upd[v], len));
add(upd[v * 2 + 1], upd[v]);
upd[v] = {Big(0), Big(0)};
}

pii get(int l, int r, int v = 1, int cl = 0, int cr = base) {
if (l <= cl && cr <= r)
return t[v];
if (r <= cl || cr <= l)
return {Big(0), Big(0)};
int cc = (cl + cr) / 2;
push(v, cr - cc);
pii res = get(l, r, v * 2, cl, cc);
add(res, get(l, r, v * 2 + 1, cc, cr));
return res;
}

void put(int l, int r, pii val, int v = 1, int cl = 0, int cr = base) {
if (l <= cl && cr <= r) {
add(t[v], {val.first * (cr - cl), val.second * (cr - cl)});
return;
}
if (r <= cl || cr <= l)
return;
int cc = (cl + cr) / 2;
push(v, cr - cc);
put(l, r, val, v * 2, cl, cc);
put(l, r, val, v * 2 + 1, cc, cr);
t[v] = t[v * 2];
add(t[v], t[v * 2 + 1]);
}

const int maxn = 150100;
int arr[maxn];
int ql[maxn], qr[maxn];
vector<int> qu[maxn];
Big ans[maxn];

int main() {
cout.precision(10);
cout.setf(ios::fixed);
#ifdef LOCAL
assert(freopen("g.in", "r", stdin));
#else
#endif

int n, m;
cin >> n >> m;
forn (i, n)
scanf("%d", arr + i);
forn (i, m) {
int l, r;
scanf("%d%d", &l, &r);
--l;
ql[i] = l, qr[i] = r;
qu[ql[i]].push_back(i);
}
vector<int> st;
st.push_back(n);
int T = 0;
for (int L = n - 1; L >= 0; --L) {
while (st.size() > 1 && arr[st.back()] <= arr[L]) {
int ql = st.back(), qr = *prev(prev(st.end()));
put(ql, qr, {Big(-arr[ql]), Big(arr[ql]) * T});
st.pop_back();
}
st.push_back(L);
int ql = st.back(), qr = *prev(prev(st.end()));
put(ql, qr, {Big(arr[ql]), Big(-arr[ql]) * T});
++T;

for (auto id: qu[L]) {
auto p = get(::ql[id], ::qr[id]);
ans[id] = p.first * T + p.second;
}
}

forn (i, m)
cout << (ll)ans[i] << '\n';

#ifdef LOCAL
cerr << "Time: " << double(clock()) / CLOCKS_PER_SEC << '\n';
#endif
}

In   Java  :

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.Collections;
import java.io.InputStream;

public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
OutputWriter out = new OutputWriter(outputStream);
SegmentMax solver = new SegmentMax();
solver.solve(1, in, out);
out.close();
}

static class SegmentMax {
int n;
int m;
int[] a;
int[] l;
int[] r;
int[] leftMax;
int[] rightMax;
final List<Event> events = new ArrayList<>();
final int inf = (int) 1e9 + 100;

public void solve(int testNumber,
a = new int[n];
for (int i = 0; i < n; i++) {
}
l = new int[m];
r = new int[m];
for (int i = 0; i < m; i++) {
}
leftMax = new int[n];
rightMax = new int[n];
final int[] stackValue = new int[n + 1],
stackPos = new int[n + 1];
int stackLen = 0;
stackValue[stackLen] = inf;
stackPos[stackLen++] = -1;
for (int i = 0; i < n; i++) {
while (stackLen > 0 && stackValue[stackLen - 1]
<= a[i]) {
stackLen--;
}
leftMax[i] = stackPos[stackLen - 1];
stackPos[stackLen] = i;
stackValue[stackLen++] = a[i];
}
stackLen = 0;
stackValue[stackLen] = inf;
stackPos[stackLen++] = n;
for (int i = n - 1; i >= 0; i--) {
while (stackLen > 0 &&
stackValue[stackLen - 1] < a[i]) {
stackLen--;
}
rightMax[i] = stackPos[stackLen - 1];
stackPos[stackLen] = i;
stackValue[stackLen++] = a[i];
}
for (int i = 0; i < n; i++) {
int l = leftMax[i] + 1, r = rightMax[i] - 1;
addQuad(0, l - 1, r + 1, n - 1, 0, 0, 0, 1L *
(i - l + 1) * (r - i + 1) * a[i]);
(i - r - 1) * a[i], 0, 1L * (i + 1) * (r - i + 1) * a[i]);
(i - l + 1) * a[i], 1L * (1 - i) * (i - l + 1) * a[i]);
a[i], 1L * (i + 1) * a[i], (-1L * i * i + 1) * a[i]);
}
for (int i = 0; i < m; i++) {
}
Collections.sort(events);
final Fenwick LR = new Fenwick(n), L =
new Fenwick(n), R = new Fenwick(n), C = new Fenwick(n);
final long[] ansLR = new long[m], ansL =
new long[m], ansR = new long[m], ansC = new long[m];
for (Event e : events) {
if (e.type == -1 || e.type == 1) {
LR.update(e.l, e.r, e.LR * -e.type);
L.update(e.l, e.r, e.L * -e.type);
R.update(e.l, e.r, e.R * -e.type);
C.update(e.l, e.r, e.C * -e.type);
}
if (e.type == 0) {
int r = this.r[e.index];
ansLR[e.index] = LR.getValue(r);
ansL[e.index] = L.getValue(r);
ansR[e.index] = R.getValue(r);
ansC[e.index] = C.getValue(r);
}
}
for (int i = 0; i < m; i++) {
out.printLine(ansLR[i] * l[i] * r[i] +
ansL[i] * l[i] + ansR[i] * r[i] + ansC[i]);
}
}

long LR, long L, long R, long C) {
if (l > r || b > t) {
return;
}
}

static class Event implements Comparable<Event> {
public final int x;
public final int type;
public final int l;
public final int r;
public final long LR;
public final long L;
public final long R;
public final long C;
public final int index;

public Event(int x, int type, int l, int r,
long LR, long l1, long r1, long c, int index) {
this.x = x;
this.type = type;
this.l = l;
this.r = r;
this.LR = LR;
L = l1;
R = r1;
C = c;
this.index = index;
}

int l, int r, long LR, long L, long R, long C) {
return new Event(x, -1, l, r, LR, L, R, C, -1);
}

public static Event quadEnd(int x, int l,
int r, long LR, long L, long R, long C) {
return new Event(x, 1, l, r, LR, L, R, C, -1);
}

public static Event point(int x, int index) {
return new Event(x, 0, -1, -1,
-1, -1, -1, -1, index);
}

public int compareTo(Event o) {
int k = Integer.compare(x, o.x);
return k != 0 ? k : Integer.compare(type, o.type);
}

}

}

static class OutputWriter {
private PrintWriter writer;

public OutputWriter(Writer writer) {
this.writer = new PrintWriter(writer);
}

public OutputWriter(OutputStream stream) {
this(new OutputStreamWriter(stream));
}

public void print(Object... args) {
for (Object arg : args) {
writer.print(arg);
}
}

public void printLine(Object... args) {
print(args);
writer.println();
}

void close() {
writer.close();
}

}

private StringTokenizer tokenizer;

}

}

public String nextLine() {
try {
} catch (IOException e) {
throw new RuntimeException(e);
}
}

while (tokenizer == null || !tokenizer.hasMoreTokens()) {
tokenizer = new StringTokenizer(nextLine());
}
}

}

}

static class Fenwick {
public final int n;
public final long[] a;

public Fenwick(int n) {
this.n = n;
a = new long[n];
}

public long getValue(int r) {
long result = 0;
for (; r >= 0; r = (r & (r + 1)) - 1) {
result += a[r];
}
return result;
}

public void update(int l, int r, long value) {
if (l > r) {
return;
}
update(r + 1, -value);
update(l, value);
}

public void update(int x, long value) {
for (; x < n; x = x | (x + 1)) {
a[x] += value;
}
}

}
}```
```

## Truck Tour

Suppose there is a circle. There are N petrol pumps on that circle. Petrol pumps are numbered 0 to (N-1) (both inclusive). You have two pieces of information corresponding to each of the petrol pump: (1) the amount of petrol that particular petrol pump will give, and (2) the distance from that petrol pump to the next petrol pump. Initially, you have a tank of infinite capacity carrying no petr

## Queries with Fixed Length

Consider an -integer sequence, . We perform a query on by using an integer, , to calculate the result of the following expression: In other words, if we let , then you need to calculate . Given and queries, return a list of answers to each query. Example The first query uses all of the subarrays of length : . The maxima of the subarrays are . The minimum of these is . The secon

## QHEAP1

This question is designed to help you get a better understanding of basic heap operations. You will be given queries of types: " 1 v " - Add an element to the heap. " 2 v " - Delete the element from the heap. "3" - Print the minimum of all the elements in the heap. NOTE: It is guaranteed that the element to be deleted will be there in the heap. Also, at any instant, only distinct element