题解 AT2165 [AGC006D] Median Pyramid Hard

· · 题解

Atcoder 题面传送门 & 洛谷题面传送门

u1s1 Atcoder 不少思维题是真的想不出来，尽管在 Atcoder 上难度并不高

二分答案（这我倒是想到了），检验最上面一层的数是否 \ge x。

我们将最底下一层的数中 \ge x 的 a_i 设为 1，<x 的设为 0，那么原题可以转化为每次操作对于相邻三个数，如果 1 的个数 \ge 2，就在该位上填一个 1，否则在该位上填一个 0，求最终顶上的数是 0 还是 1。

不难发现经过二分答案这个转化，我们将原来值域在 [1,2n-1] 范围内的问题缩小为值域在 [0,1] 范围内的问题，可直接做似乎还是有些棘手，我们不妨进一步探究这里面的规律。

我们手玩几组数据即可发现一个性质，如果相邻两个数都是 1，那么它上面所有数都是 1，反正如果相邻两个数都是 0，那么它上面所有数都是 0，并且如果 i 满足 a_{i}=a_{i+1}=a_{i-2}=1，那么到了上一层第 i-1 列也会变成 1，可以看作这个 1 “蔓延”到了第 i-1 列，于是我们猜测，第 n 层的数一定与距离中心点最近的 a_{i}=a_{i+1} 的 i 有关，因为它能最快“蔓延”到第 n 列。

事实果真如此。

这里稍微证明一下。记 i=n+p 为距离中心点最近的满足 a_i=a_{i+1} 的 i，其中 p\ge 0（p<0 也同理，翻转一下就行了），如果 p=0 那显然根据之前的结论，第 n 列的数就是 a_n，符合题意。否则，由于 i=n+p 为最近的满足 a_i=a_{i+1} 的 i，必然有 [n-p,n+p] 部分的 a_i 为 01 间隔分布，即 a_{n+p-2}=a_{n+p-4}=a_{n+p-6}=\cdots=a_{n-p+2}=a_{n-p}=a_{n+p}，a_{n+p-1}=a_{n+p-3}=a_{n+p-5}=\cdots=a_{n-p+1}=1-a_{n+p}，由 a_{n+p-2}=a_{n+p}=a_{n+p+1} 可知从下往上数第二行第 n+p-1 位置上的值也是 a_{n+p}，相当于 a_{n+p} 向左蔓延了一格。而显然对于 01 分布的序列，进行一遍取中位数操作之后还是 01 间隔分布的，因此到第二行可以看作 p'=p-1 的版本继续递归下去，归纳可得最终的数就是 a_{n+p}。

有人可能会问：如果存在 p 使得 i=n+p 为距离中心点最近的满足 a_i=a_{i+1} 的 i，满足 a_{n+p}=a_{n+p+1}\ne a_{n-p}=a_{n-p-1} 怎么办呢？稍微动点脑子即可知道这种情况是不可能的，因为根据上面的证明过程可知 [n-p,n+p] 是 01 间隔分布的，因此 \forall x,y\in[n-p,n+p]，若 |x-y| 为偶数，则 a_x=a_y，反之 a_x\ne a_y，而 n-p\equiv n+p\pmod{2}，故 a_{n-p}=a_{n+p}，因此不会出现这种情况。

最后特判整个 a 数组就是 01 间隔分布的情况，此时最上面一层的数就是 a_{2n-1}。

const int MAXN=1e5;
int n,a[MAXN*2+5],b[MAXN*2+5];
bool check(int x){
    for(int i=1;i<(n<<1);i++) b[i]=(a[i]>=x);
    for(int i=0;i<n-1;i++){
        if(b[n+i]==b[n+i+1]) return b[n+i];
        if(b[n-i]==b[n-i-1]) return b[n-i];
    } return b[1];
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<(n<<1);i++) scanf("%d",&a[i]);
    int l=1,r=(n<<1)-1,mid,x=-114514;
    while(l<=r) (check(mid=l+r>>1))?(x=mid,l=mid+1):(r=mid-1);
    printf("%d\n",x);return 0;
}