Sink

A hole is a source. If cell u is already a sink, then an adjacent cell v becomes a sink when $a[v] >= a[u]$. So sink status travels from lower/equal values to higher/equal values.

Static Grid

Compress every connected component of equal-valued cells. Inside such a component, every cell can reach every other cell because equality works both ways. Between two different components, an edge always goes from the smaller value to the larger value.

Now we have a DAG: values strictly increase along non-equal edges. In a DAG, the minimum number of starting points needed to reach everything is the number of source components. Here, a source component is exactly an equal-valued connected component with no adjacent cell of strictly smaller value.

So the beauty is:

number of equal-value connected components with no smaller neighbor.

These are basically local-minimum plateaus. Not local minimum cells, local minimum plateaus. If you count cells, you get cooked by equal values.

Why Updates Are Annoying

A query decreases one cell. If that cell belonged to a big equal plateau, removing it can split the plateau. DSU does not split, so a naive dynamic connected-components approach is dead on arrival.

The key observation is the escape hatch:

When a cell of value old is decreased to x < old, every remaining piece of its old equal plateau is adjacent to the lowered cell. Therefore every such piece has a smaller neighbor now, so none of those pieces can ever contribute to the answer.

Even better: once a plateau stops contributing, it never becomes useful again. Values only decrease. If later some cell inside it is decreased, any split pieces touch that newly decreased cell, which is again smaller. So dead plateaus stay dead. Morbid, but convenient.

This lets us use DSU without deletion. We are allowed to over-merge dead stuff, because dead stuff contributes 0 anyway.

Version Nodes

Instead of changing a DSU node's value, create a fresh node for every new version of an updated cell.

Maintain:

• last[cell]: the current DSU node representing this cell;
• val[root]: the fixed value of this DSU component;
• important[root]: whether this root currently contributes 1 to the beauty;
• DSU unions only between components with the same value.

Initially, create one node per grid cell. Mark a node as not important if it has a smaller neighbor. Then union adjacent equal-valued cells. The component's importance is the minimum of its members' importance values.

Processing One Query

Suppose cell u decreases to value x.

Only these roots can change:

• the old root containing u;
• the roots of the current versions of the at most four neighboring cells.

Collect those roots in a small set and subtract their important values from the answer.

Now kill every collected root with val[root] > x:

• if it is a neighboring component, it now has adjacent smaller cell u;
• if it is the old component of u, all pieces left after removing u touch the new smaller version of u.

Create a new DSU node for u with value x. It starts important unless some current neighbor has value < x.

Then union this new node with every collected root whose value is exactly x. Equal neighbors are now part of the same plateau. If any merged part was already dead, the merged component is dead too, so union uses min on important.

Update last[u] to the new node. Recollect the roots around u and add their important values back.

That is the whole trick: local accounting plus versioned DSU. No splitting required.

Correctness Proof

First, consider a fixed grid. Compress equal-valued connected components. A hole inside a component can cover the whole component. Edges between different components go from smaller values to larger values. A component with no incoming edge from a smaller component cannot be reached from outside, so it needs a hole. Conversely, every component in this DAG is reachable from some source component, so one hole in every source component is enough. Thus the beauty equals the number of equal-valued components with no smaller neighbor.

Now consider the dynamic algorithm. The only cell whose value changes in a query is u, so any component not touching u keeps the same adjacencies and cannot change whether it contributes. Thus it is enough to update the old root of u and the roots of its neighbors.

When u is lowered from old to x, every remaining connected piece of its old equal-valued component is adjacent to u; otherwise that piece could not have been connected to u before removing it. Since x < old, all those pieces now have a smaller neighbor, so they do not contribute. Any neighboring component with value greater than x also gets a smaller neighbor and stops contributing. Marking those roots as not important is therefore correct.

The new component containing u contributes exactly when it has no smaller neighbor. We initialize the new node using the minimum value among its current neighbors, then union it with equal-valued neighbor roots. Taking the minimum important value during unions is correct because one smaller neighbor anywhere kills the whole equal plateau.

After subtracting old local contributions and adding the new local contributions, the answer is exactly the number of contributing plateaus again. By induction over the queries, every printed answer is correct.

Complexity

There are n*m + q DSU nodes. Each query touches at most five roots, so the total complexity is O((n*m + q) alpha(n*m + q)) with linear memory. In practice, it is basically constant-time per query.