CSES - Increasing Array Queries

Time Complexity: $\mathcal O((N + Q) \log N)$.

In this problem, we can answer the queries offline (i.e. read in the queries and process them in a different order). More specifically, we process queries in order of their left endpoints.

First, let's think about how we'd answer a single query $(l, r)$. Consider the following algorithm:

• Let $\texttt{mx}_0 = 0$ and $j = 0$.
• For each $i$ in $[l, r]$:
  • If $x_i > \texttt{mx}_j$, then set $\texttt{mx}_{j + 1} = x_i$ and increment $j$.
  • Otherwise, add $\texttt{mx}_j - x_i$ to the answer.

Notice how each $\texttt{mx}_j$ (except the last) contributes a fixed amount to the answer, regardless of $r$. If $\texttt{pref}$ is the prefix sum array of $x$ and $\texttt{idx}_j$ is the index of $\texttt{mx}_j$ in $x$, then this amount is

This means that for a fixed $l$, we can compute each $\texttt{mx}_j$ and their contributions, and then use std::upper_bound and a BIT to answer queries with variable $r$!

If we want to change $l$, notice how we can update $\texttt{mx}$ efficiently by using a monotone stack. Since each $\texttt{mx}_j$'s contribution depends on $x_i$ after it, the contributions of the old $\texttt{mx}_j$ don't change.

Again, we use std::upper_bound and a BIT to answer queries.

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const ll INF = 1e18;

int n, q;
ll x[200002], pref[200002], ans[200002];
ll contrib[200002], bit[200002];
vector<pair<int, int>> bckt[200001];