Sort all problems by their topics in non-decreasing order. You should pick three problems in strictly increasing order. Now you can group them by topics. To count all triples you can fix topic of second problem in increasing order, and count how many ways you can pick problem with this fixed topic, task with topic below, and task with topic above. All problems before the fixed group will have topic below, so their number is just zero-based index of first problem within the fixed group. All problems after the fixed group will have topic above, so their number is n minus zero-based index of last problem within the fixed group minus one. And number of problems with the fixed topic is just length of fixed group. Multiply those and get all triples.

I don't know. I did try to think in this way, but there are too many of possible situations. So I dropped this idea. Instead, think in other way. Suppose instead we calculated all triples with different difficulties. What are we missing after it?

1 2 0
1 2 1
1 2 2
2 2 1
2 2 2
2 2 3
1 2 3
3 2 1
3 2 2
3 2 3
3 2 4

1 2 0
1 2 1 v
1 2 2 v
2 2 1 v
2 2 2 v
2 2 3 v
1 2 3
3 2 1
3 2 2 v
3 2 3 v
3 2 4

1 2 0
1 2 1 v =
1 2 2 v
2 2 1 v
2 2 2 v =
2 2 3 v
1 2 3
3 2 1
3 2 2 v
3 2 3 v =
3 2 4

1 2 0
1 2 1 v =
1 2 2 v     r
2 2 1 v   l
2 2 2 v = l r
2 2 3 v   l
1 2 3
3 2 1
3 2 2 v     r
3 2 3 v =
3 2 4

Similar to editorial, define base staircases. The only trick I need to describe is how easily to index all stuff. Because we will have $$$O(n+m)$$$ base staircases, and we need to be able pick the one we need to operate at that moment. Idea is to store within staircase indexes of blocked cells in set in C++, then we can use lower_bound method to find next blocked cell or previous blocked cell when we need. Requirement for indexing is simple: we need their indices go one after another, so that length of empty cells would be next blocked cell minus previous blocked cell minus one. We don't actually have any other requirement for single staircase, because we'll use trick to initially install blocked blocks around whole table. So far as our new / old blocked cell is located between those indexes of blocked cells outside of table — we're fine.

And here is neat idea to index within single staircase. Notice that no matter which base staircase we choose it will have exactly two cells on each row (not taking into account restriction to being inside of table). Let's say left one of those cell is 0, and right one is 1. Now, it's easy to see, that index of left cell $$$= row * 2$$$ and index of right cell $$$= row * 2 + 1$$$ will satisfy all our requirements. All cells within staircase will go one after another, and we have very easy formulas for left cells and right cells. You can think of it like formula for apartment numbers if there are exactly 2 apartments on each floor.

Now, we need to make indices for our base staircases. We also don't need particular starting point, all we need that they also go one after another. Notice that each base staircase can be uniquely defined by set of their left cells within rows. Also note: they form a diagonal. There is easy way to index diagonal, just $$$x - y$$$, here $$$x$$$ is row number. And this is exactly what we need.

Notice, when we block cell, in one base staircase we block left one, and in other base staircase we block right one. And the one which we block right cell is next base staircase. Next diagonal (and base staircase) would be $$$x - y + 1$$$. So, each time we block cell we can implement it as block index $$$2*x$$$ in staircase $$$x - y$$$ and block index $$$2*x + 1$$$ in staircase $$$x - y + 1$$$. You could use indices of staircases $$$x - y - 1$$$ and $$$x - y$$$ correspondingly, this only change index of starting base staircase. Blocking cell removal implemented similarly. Also, checking is there already blocking cell can be also done like this.

All we left to do is to figure out how many stairs there are initially after installing all blocking cells around the table. To do that, we can just walk over all base staircases, and find those with at least two blocking cells (there shouldn't be any with 3 or more blocking cells), and count number of staircases within as usual.

131469659

This solution will work in $$$O(n\cdot2^n + A)$$$ where $$$A$$$ is total length of brackets sequences.

Notice, that for any fixed mask of used brackets sequences, there is fixed balance. Because balance is sum, and no matter how do you rearrange sequence, it will still have same balance in the end.

Notice, that for any prefix of used backets sequences, if there is better arrangement for this set of brackets sequence, you can change into it, and get better result. Thus any prefix should be optimal for corresponding mask.

Thus we have idea of following dp[mask] — number of RBS prefixes in best arrangement of sequences from bit mask mask. But idea is slightly different. Let's say dp[mask] is this thing if and only if it still potentially may have more RBS prefixes, otherwise None in Python or minus infinity in C++ or Python as well.

In this case, any potential answer is either dp[mask] as is, or dp[mask] + single sequence of brackets after which we can't have any more RBS prefixes.

Suppose we somehow maintain total balance for mask: it could be additional dp for balance of masks, or precalc, or other approaches. Then, when we append sequence to current mask, we need to somehow find out how many times we reach 0 balance to count additional RBS and also we need to find out do we reach negative balance at any moment. To do that, it's pretty straightforward. Just precalc balance of each sequence, and minimum, and how many times it reach minimum. To count how many times we reach 0 we use number of times we reach minimum. Because, if we reach 0 when it's not minimum, then we will have negative balance and won't update dp[] because we don't store sequences which failed to continue. So when we reach 0 it should be minimum within this sequence of brackets. Also this shows us how to check does it fail for continuation.

Now, tricky part. In the way above we can get maximum over dp[mask], but there are also cases when best answer is some dp[mask] + sequence of brackets after which we won't have any additional RBS prefixes. For this case we already know what balance of mask of sequences. Let's call this balance of mask b. We only need to know how many additional RBS prefixes we will get when we add single sequence of brackets. And, this is just how many times balance of this single sequence reach -b, because at that point mask has balance b, so to reach 0 it should add -b. But it could fail to be RBS before reaching 0, for example, fourth time. So, we actually need to know how many times this single sequence of brackets reach balance -b before reaching balance which is -b-1 (less by one). And this quantity we can precalculate in linear time of $$$A$$$, in other words, in linear time of total length of brackets sequences. Just make array for each sequence, and in its index b store how many times balance reach -b before reaching -b-1. Balance never grows more than length of brackets sequence, so total space of this precalculation is total length of brackets sequences $$$O(A)$$$.

So, for each sequence of brackets we precalculate: how many times it reach balance -b before reaching -b-1. Also, for each mask we maintain or precalculate total balance of sequence within mask. And write dp[mask] = maximum RBS prefixes for some arrangement of mask which still may have additional RBS-prefixes. Otherwise None in Python or minus infinity in C++ or Python as well. Then, answer is either maximum dp[mask] or some dp[mask] + sequence of brackets after which we won't have any additional RBS prefixes.

131544153

Lets calculate the number of staircases of both types at $$$cell (i,j)$$$ using Dynamic Programming

$$$L[i][j] =$$$ number of staircases starting at $$$cell (i,j)$$$ of type $$$1$$$

$$$D[i][j] =$$$ number of staircases starting at $$$cell (i,j)$$$ of type $$$2$$$

Notice that at $$$cell (i,j)$$$, all staircases of type $$$1$$$, lead to all staircases of type $$$2$$$ in $$$cell(i,j+1)$$$

Also note that at $$$cell (i,j)$$$, all staircases of type $$$2$$$, lead to all staircases of type $$$1$$$ in $$$cell(i+1,j)$$$

This leads to the recurrence formula:

$$$L[i][j] = 1+D[i][j+1], D[i][j] = 1+L[i+1][j]$$$ (if $$$cell (i,j)$$$ is free)

$$$L[i][j] = D[i][j] = 0$$$ (if $$$cell (i,j)$$$ is blocked)

The total number of staircases = sum of all $$$L[i][j]$$$ and $$$D[i][j]$$$ minus count of all free $$$1*1$$$ cells.

This is so because both types of staircases are $$$1*1$$$ squares so we have to subtract due to overcounting.

As for queries, we can just update $$$cell (i,j)$$$ to new status and recalculate all dp values but this is too slow since there are $$$N*M$$$ values to update.

You can observe that if one cell is updated, not all dp values change. The only dp values that change are the ones that can reach $$$cell (i,j)$$$ through a valid staircase of either type. The number of such cells is at most $$$min(n,m)*2$$$ for either staircase type. So all we need to do is update only those cells, which is $$$O(min(n,m))$$$ per query. To do that, we can update current cell then run a dfs from current cell to all cells that can be visited either by going up or down and update the dp values for those cells. The sum of all $$$L[i][j]$$$ and $$$D[i][j]$$$ can be stored in a sum variable and updated accordingly. The same thing can be done for the number of free cells.

Time Complexity: $$$O(NM + Q*min(N,M))$$$

code