web analytics

BZOJ1303 [CQOI2009]中位数图

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1303

分析:

首先对数字进行操作.
因为数值在本题不重要.
所以排列中如果比B大就变成1 如果比B小就变成-1

你会发现这样我们可以巧妙的使用和为零就可以来判断.

之后就是怎么维护这个序列.

我们可以发现如果两边和为0则左边与右边和一定互为相反数.

所以做一个类似前缀和的处理.
由于负数不能为下标.做一个平移量的处理即可.

还要初始化.

Post a Comment

You must be logged in to post a comment.