bzoj 1303: [CQOI2009]中位数图 dp 乘法原理

我们从d的点往左扫,然后我们用一个变量维护大于小于d点值的数量,即大于d点就++,小于d点就–。然后我们每次记录一下不同的这个变量的数量。然后我们同理处理右侧。我们考虑如果左侧有变量维护为1,意味着我们缺少一个小于d的量。那我们去右侧找-1,然后相乘即可。记得算上这个变量为0的情况。和d本身是一个区间的这个事实。

发表评论