hackercupai/hackercup huggingface dataset:
Let a line segment \((a, b)\) refer to a consecutive pair of columns with distinct heights \(a\) and \(b\), such that \(a < b\). If the column indices are \(i\) and \(i+1\), then we'll refer to \(i\) as the line segment's *position*.

We'll define the *weight* \(w\) of a line segment to be the number of spider paths which would cross it. If its index is \(i\), then \(w = i*(N-i)\). We'll say that each line segment has two separate *endpoints* with values \(a\) and \(b\), each with weight \(w\), and with weighted values \(w*a\) and \(w*b\).

When evaluating an \(S\) value for a water level \(W\), we'll define a *relevant line segment endpoint* as one with a value greater than \(W\). We'll start by computing the sum of relevant \(b\) endpoints' weighted values, and subtract the sum of relevant \(a\) endpoints' weighted values. There may be line segments for which we only added the \(b\) endpoint but didn't subtract the \(a\) endpoint (due to it being having a value no greater than \(W\)). To account for this, we'll take the sum of relevant \(b\) endpoints' weights, subtract the sum of relevant \(a\) endpoints' weights, multiply that difference by \(W\), and finally subtract that product to arrive at our final answer.

In order to compute the above values efficiently, we can maintain 4 Fenwick (binary indexed) trees, containing the \(a\) / \(b\) endpoints' weights / weighted values (in each case indexed by the endpoints' values). Assuming these have been maintained, we can compute each \(S\) value in \(O(log(N))\) time.

At first glance, it appears we'll need to perform up to \(O(NM)\) updates to these trees, given that up to \(N\) line segments may be affected by each of the \(M\) earthquakes. However, we can observe that setting the heights of an interval of columns \([L, R]\) causes all line segments at positions in \([L, R-1]\) to disappear, causes at most 2 new line segments (at positions \(L-1\) and \(R\)) to appear, and doesn't update any other line segments. Therefore, across all of the earthquakes, only \(O(N + M)\) line segments need to be updated, and we just need to not waste time iterating over positions not featuring line segments.

This can be done either by maintaining a set of intervals of equal-height columns (such that there's a line segment between each consecutive pair of intervals), or by maintaining a segment tree of column heights combined with a set of line segment positions. Either way, these data structures may be updated in amortized \(O(log(N))\) time per earthquake and allow us to only update the Fenwick trees described above for \(O(N + M)\) line segments overall. The total complexity is therefore \(O((N + M) log(N))\).