CSES - Pizzeria Queries

Time Complexity: $\mathcal O(N\log N)$

When we query the minimum cost to buy a pizza at point $i$, we can split it into two cases ($i\rightarrow j$)

1. going downwards ($j < i$): the cost would be $p_j-j+i$
2. going upwards ($j > i$): the cost would be $p_j+j-i$

Since $+i$ and $-i$ are constant, we can first calculate the best cost and then add $+i$ for the downwards cost and $-i$ for the upwards cost.

Thus, if we keep two min segtrees (one for going downwards and one for going upwards), we can keep track of the minimum cost by setting each value in the downwards segtree to $p_j-j$ and each value in the upwards segtree to $p_j+j$.

To query, we can simulate going downwards or upwards from position $k$. To go downwards, we must buy pizza in the range $[1\dots k]$ so we query the minimum cost in the range $[1\dots k]$. Going upwards is similar to going downwards, but instead of buying pizza in the range $[1\dots k]$, we're buying pizza in the range $[k\dots N]$; thus we query the range $[k\dots N]$ in the upwards segtree.

Copy
#include <bits/stdc++.h>
using namespace std;

template <class T> struct SegTree {
	T U = 1e9;
	T F(T a, T b) { return min(a, b); }
	int N;
	vector<T> t;
	SegTree() {}
	SegTree(int N) : N(N), t(4 * N, U) {}