H - Water Tank Editorial by en_translator
For \(n=1,2,\ldots,N\), consider how \(A _ i\ (i\lt n)\) looks like right before \(A _ n\) becomes positive for the first time.
Derivation via deduction
We will prove the following two properties on the operations.
For an integer \(i\) with \(1\leq i\leq N\), we will denote by \(P(i)\) the proposition \(A _ {i-1}\leq\max\lbrace H _ i,A _ i\rbrace\).
- Right after an operation, \(P(i)\) holds for all \(i=1,2,\ldots,N\).
- The operation can be rephrased as follows.
- Replace \(i _ {\mathrm C}\) with the minimum \(i\ (1\leq i\leq N)\) such that .\(A _ {i-1}\lt\max\lbrace H _ i,A _ i\rbrace\) (or \(N+1\,\) if absent.)
- Increase \(A _ {i _ {\mathrm C}-1}\) by \(1\).
First, we show that \(1\implies2\).
Proof
Note that \(P(i)\) is equivalent to \(\neg(A _ {i-1}\gt A _ i\wedge A _ {i-1}\gt H _ i)\).
Before an operation starts, \(A _ {i-1}=\max\lbrace H _ i,A _ i\rbrace\) holds for \(1\leq i\lt i _ {\mathrm C}\). When performing step 2 against \(i\), \(A _ {i-1}\) has been increased by \(1\) by step 2 against \(i-1\) or step 1, so \(A _ {i-1}\gt A _ i\) and \(A _ {i-1}\gt H _ i\) holds.
Right after step 1 is performed and step 2 is performed against \(1\leq i\lt i _ {\mathrm C}\), only \(A _ {i _ {\mathrm C}-1}\) has been increased by \(1\). By the choice of \(i _ {\mathrm C}\), the preposition \(P(i _ {\mathrm C})\) also holds right before performing step 2 against \(i=i _ {\mathrm C}\). Thus, \(A _ {i _ {\mathrm C}}\) stays invariant. By the assumption, \(P(i)\) holds for all \(i _ {\mathrm C}\lt i\), so the condition on performing step 2 is never satisfied against \(i _ C\lt i\).
Therefore, \(1\implies2\) has been shown.
Next, we will show \(1\). We prove it by induction on the number of operations.
Proof
Initially, \(A _ 0=A _ 1=\dotsb=A _ N=0\), so the condition is met.
We will prove that when the condition is met, after performing an operation once the condition is still met.
By the proof above, if you perform an operation when the condition is met, only \(A _ {i-1}\) against the minimum \(i\) such that \(A _ {i-1}\lt\max\lbrace H _ i,A _ i\rbrace\) or \(N+1\,\) if absent) increases by \(1\).
Thus, for \(i\neq i _ {\mathrm C}-1,i _ {\mathrm C}\), the values \(A _ {i-1},A _ i\) remain invariant, keeping \(P(i)\) true.
For \(i=i _ {\mathrm C}-1\), the value \(A _ i\) increases, so \(\max\lbrace H _ i,A _ i\rbrace\) never decreases, and \(P(i _ {\mathrm C}-1)\) holds. If \(i _ {\mathrm C}\leq N\), for \(i=i _ {\mathrm C}\), we have \(A _ {i-1}\lt\max\lbrace H _ i,A _ i\rbrace\) by definition of \(i _ {\mathrm C}\), so \(P(i _ {\mathrm C})\) still holds after incrementing \(A _ {i-1}\).
Therefore, \(1\) has been shown.
By the representation 2, it turns out that \(i _ {\mathrm C}=n\) is necessary for an operation that makes \(A _ n\) positive for the first time. That is, right before this operation, \(A _ {i-1}=\max\lbrace H _ i,A _ i\rbrace\) for all \(1\leq i\lt n\).
Then one can determine the values of \(A _ i\) for \(i=n-1,n-2,\dotsc,1,0\) in this order, thus deriving \(\displaystyle A _ i=\max _ {i\lt j\leq n}H _ j\ (0\leq i\lt n)\).
By a thorough observations on the conditions or experiments, it turns out that \(\displaystyle A _ i=\max _ {i\lt j\leq n}H _ j\ (0\leq i\lt n)\) holds right before \(A _ n\) becomes positive for the first time.
Since \(\displaystyle\sum _ {i=0} ^ NA _ i=0\) initially, and an operation increases \(\displaystyle\sum _ {i=0} ^ NA _ i\) by one, the answer for \(i=n) is the value \[\sum _ {i=0} ^ NA _ i=1+\sum _ {i=0} ^ {n-1}\max _ {i\lt j\leq n}H _ j.\]
Considering the delta of \(\displaystyle X _ i\coloneqq\max _ {i\lt j\leq n}H _ j\) when \(n\) increases, one can rephrase the problem as follows.
There is a length-\(N\) sequence \(X=(X _ 1,X _ 2,\dotsc,X _ N)\). Initially, \(X _ 1=X _ 2=\dotsb=X _ N=0\). For \(i=1,2,\ldots,N\) in order, perform the following operation.
- For \(1\leq j\leq i\), set \(X _ j\leftarrow\max\lbrace X _ j,H _ i\rbrace\).
Find \(\displaystyle1+\sum _ {i=1} ^ NX _ i\) right after each operation.
There are several approaches to solve it.
- Use a stack to manage the sequence of pairs \(\bigl(H _ i, (\)the number of indices \(j\) with \(X _ j=H _ i)\bigr)\).
- On \(X _ j\leftarrow\max\lbrace X _ j,H _ i\rbrace\), repeatedly pop the initial pair \((v,c)\) of the stack while \(v\leq H _ i\), and push \(\bigl(H _ i,(\)the sum of \(c\) that have been taken out \({}+1)\bigr)\).
- Update \(\sum X _ i\) accordingly in the same manner as an operation against the stack.
- Use a lazy segment tree to regard them as segment-update and segment-sum queries.
- Since \(X\) monotonically decreases, the segment to be updated can be found with a binary search.
- Use the “segment tree beats” to process segment-chmax & segment-sum queries.
For the first approach, the time and spacial complexity is \(\Theta(N)\); for the second and third, the time complexity is \(\Theta(N\log N)\) and the spacial complexity is \(\Theta(N)\).
The following is sample code. This implementation adopts the first approach.
#include <iostream>
#include <utility>
#include <vector>
int main() {
using namespace std;
unsigned N;
cin >> N;
// Manage (height, count) in monotonically descending order of height
vector<pair<unsigned, unsigned>> rectangles;
// 1 + ∑ (height x count)
unsigned long ans = 1;
for (unsigned i = 0, H; i < N; ++i) {
cin >> H;
// height is H, and count is initially 1
unsigned count = 1;
// Update while there is something lower than H
while (!empty(rectangles) && rectangles.back().first <= H) {
const auto &[h, c] = rectangles.back();
// subtrcact (h x c) from the sum,
ans -= static_cast<unsigned long>(h) * c;
// increase the count,
count += c;
// and remote it from the sequence
rectangles.pop_back();
}
// Add (H × count) to the sum
ans += static_cast<unsigned long>(H) * count;
rectangles.emplace_back(H, count);
cout << ans << " ";
}
cout << endl;
return 0;
}
posted:
last update: