Sliding Tiles

The trick is to stop thinking about individual tiles. Individual tiles are a trap here. This is a tilt puzzle, not a tiny physics simulator. Simulating cells is how your $O(n^2)$ solution goes to the shadow realm.

Row View

Look at one fixed row $y$ during the first operation, the right tilt.

A tile exists in column $i$ on this row iff

$a_i \ge y.$

The bar between columns $i$ and $i+1$ blocks movement on this row iff

$h_i \ge y.$

So on row $y$, active bars split the row into independent horizontal segments. Inside one segment, the right tilt is extremely simple: if the segment has $c$ tiles, those $c$ tiles end up in the rightmost $c$ cells of the segment.

After that, the down tilt only stacks each column downward. Therefore the final answer for column $j$ is just the number of rows where column $j$ is occupied after the right tilt.

So the whole problem becomes:

For every row $y$, split columns by bars with $h_i \ge y$. In each segment, count active tile columns with $a_i \ge y$, then add $1$ to the rightmost count columns of that segment.

Still sounds expensive if done row by row. Now we make it offline.

Sweep Rows From Top To Bottom

Process rows $y=n,n-1,\dots,1$.

As $y$ decreases:

• a column $i$ becomes active exactly when $y=a_i$;
• an edge between $i$ and $i+1$ becomes passable exactly when $y=h_i+1$.

Why $h_i+1$? Because a bar of height $h_i$ blocks rows $1..h_i$. It does not block row $h_i+1$. For $h_i=0$, the edge is passable even on row $1$.

Use a DSU where each component is a contiguous interval of columns. For every component, store:

• L, R: its interval;
• cnt: how many active tile columns are inside it;
• last: the highest row from which the component's current state has been valid.

For a component $[L,R]$ with cnt = c, the occupied cells after the right tilt are exactly the suffix

$[R-c+1,R].$

Flushing Contributions

A component's occupied suffix only changes when:

1. a tile column becomes active;
2. two neighboring components merge.

Before changing a component at row $y$, add its current contribution for all rows where it was unchanged.

If its last value is $t$, then the unchanged rows are

$t, t-1, \dots, y+1,$

so there are $t-y$ rows. Add $t-y$ to every column in its current occupied suffix.

At the end, flush every remaining component down to row $0$, contributing its rows $last..1$.

Range additions over columns are handled with a simple difference array, because each flush just adds a constant to one interval.

Events

At each row $y$ from $n$ down to $1$:

• activate all columns with $a_i=y$;
• merge all edges with $h_i+1=y$.

Both events start being true on row $y$, so we flush old state to boundary $y$, mutate, and set last = y.

Complexity

Every column activates once. Every edge merges once. Every event does a constant number of DSU operations and one or two range additions.

Total time:

$O(n\alpha(n))$

Memory:

$O(n).$