备战蓝桥杯---前缀和与差分

作者：盐析白兔 | 2024-04-06 21:18:45

踩

备战蓝桥杯---前缀和与差分

话不多说，直接上题。

分析：

这是法1的AC代码：

这是法2的AC代码：

还可不可以对差分再优化呢？

注意到，上面的差分一方面地址可以存在结构体中以节省空间（离散化），另一方面，我们可以观察到当值从0变为1时代表它进入了去掉树的区间，这样就可以通过做差来快速求解，下面是AC代码：

继续

分析：

我们不关心对于某个中位数旁边的具体值，而是关心它是否比他大。

因此，确定一个值，和他一样的写为0，比他大的为1，比他小的为-1.问题等价于求一个奇数序列，使其值为0并且包含0的值。

于是，以0为分界，左边进行后缀和,右边进行前缀和，依次匹配即可。

下面是AC代码：

接下来，我们引进二维前缀和的概念

分析：

AC代码：

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/374379