计数

今天做洛谷 P1950，是计算长方形数量，总结了一些有关计数问题的观点：

一个计数问题，一定有给定的最终计数对象，其数量就是答案，另外，我们确立辅助计数对象来辅助计数，它们统称为计数对象。
一个有用的辅助计数对象要么有更好的性质，例如极值性质；要么更容易遍历，最好的情况是它本身是一串连续的数字。
两个计数对象的数量可能相同，这也就是说它们存在一一对应，这在保持数量的同时能够改变计数对象的性质；也可能不同，此时要么相差固定的个数（或许由于纳入了边界情况）或倍数（或许由于重复计算)
最后，它们也可能是这样的关系：计数对象 B 构成的集合是计数对象 A 构成集合的划分，通俗地说，我们对 A 进行了分类讨论，每个计数对象 B 就是一个分类。
然而，尽管最后一种情况总是等价于一个分类讨论的过程，这并不意味着”分类“本身一定是好的视角，注意到一个事实，集族 B 是集合 A 的划分，几乎（除非 B 中有空集）等价于存在从 A 到 B 的映射，映射关系是属于关系。所以，我们完全可以不以集合划分的视角看待它，而仅仅是考虑从现有计数对象 A 到新对象 B 的映射
在本题中，通过按底边所在行分类，来到本题核心：对“山”字形中触底的长方形数量进行计数，我们称这是对象 A，这个时候，A 很任意，也就是性质很不好（外延越大，内涵越小），于是考虑一个映射，把 A 映射到具有极值性质的对象上，方法是尽可能把长方形向上延伸，触顶后尽可能向左右延伸，这样得到的长方形是计数对象 B，有很好的极值性质。现在我们希望遍历 B，数出对于每个 B，有多少 A 映射到它，累加即得结果。为了遍历 B ，我们希望建立一个从 B 构成的集合到指标集合的映射，然后遍历指标集合。自然的想法是把列号作为指标，方法是：对应每一个矩形，由于它是尽可能向上延伸而成，那么此时一定有上方的限制，可能有多个列同时限制了高度，取最左边的列号，这样就完成了映射。现在反过来看，对每一个列号，它对应的矩形的高度等于列的高度，向左延伸直到遇到高度小于等于它的列，向右延伸直到遇到高度小于它的列，这个构造过程是明确的，因此一个列号要么对应一个矩形，要么不对应任何矩形。现在考虑已知一个矩形 B，如何确定对应的 A 有几个，显然，A 包含于（在格子的意义上） B ，但并非包含于 B 的 A 都符合，事实上，只需要取出所有限制列，然后保证 A 至少包含其中一个限制列即可。自然地，在实际计算时，先考虑包含最左限制列的，再考虑剩下的长方形中包含次左限制列的，以此类推，不重不漏。
以上做法能够解决此题，但并不完美，我们仔细考虑一个列号何时能够映射回矩形，何时不能，不难发现，当这一列包含在某个矩形 B 中但不是最左限制列，这一列就不能映射回矩形，但巧合的是，在最终的计数中，我们恰恰需要统计不包含更左边限制列而包含此限制列的小矩形的数目，于是可以抛弃中间对象 B（当然，也可以认为是修改了 B 的定义），直接考虑每一列，向左延伸直至遇到高度小于等于它的列，向右延伸直至遇到小于它的列，这样延伸结束后，计算包含此列的小矩形，这样就统一了这一列作为原来的对象 B 的最左限制列和非最左限制列的情况。这样就更好地完成了本题。
这段文字发表在“想法”栏目，而不是“题解”栏目，（因为？所以？）更加意识流，偏向表达内心想法而非作为教程，因此看不明白实属正常。