CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。

=====Orac and Medians=====
====问题描述====
有一个长度为$n$的序列$a_i$，可以进行下面的操作：
选择$[L,R]$，然后把这个区间内所有的元素变为[L,R]中的中位数，如果偶数个元素就为排名$s/2$的元素的值，多组询问，求序列是否能全部变为$k$?
所有的$n$不超过$100000$

====思路====
显然我们关于中位数的题目，都可以通过0,1,2转化进行，具体来说，就是所有小于$k$的元素变为0，所有等于$k$的元素变为1，所有大于$k$的元素变为2

首先如果整个序列不存在$k$，显然不能全变成$k$。

我们还可以发现，如果$1$旁边是$2$，那么操作一下变成两个$1$，接下来就可以推到整个序列。

那么，我们考虑让$2$往两边扩展，如果有两个$2$在一个长度为3的区间内，那么我们就可以知道整个$2$可以向右推到整个序列中。

当然，如果一个长度为3的序列中含有$1$和$2$，那么显然也可以。

因此，只要讨论所有长度为2和3的序列中，含有至少两个非0元素，那么就一定可以。

CVBB ACM Team

用户工具

站点工具

页面工具