AT2165 Median Pyramid Hard 题解【二分答案】【构造】

点击量：203

    很难想到二分答案吧。。。

目录

Problem Statement

We have a pyramid with \(N\) steps, built with blocks. The steps are numbered \(1\) through \(N\) from top to bottom. For each \(1\ \leq\ i\ \leq\ N\), step \(i\) consists of \(2i-1\) blocks aligned horizontally. The pyramid is built so that the blocks at the centers of the steps are aligned vertically.

A pyramid with \(N=4\) steps

Snuke wrote a permutation of \((1,2,…,2N−1)\) into the blocks of step \(N\) . Then, he wrote integers into all remaining blocks, under the following rule:

• The integer written into a block \(b\) must be equal to the median of the three integers written into the three blocks directly under \(b\) , or to the lower left or lower right of \(b\).

Writing integers into the blocks

Afterwards, he erased all integers written into the blocks. Now, he only remembers that the permutation written into the blocks of step \(N\) was \((a_1,a_2, …… ,a_{2N-1})\).

Find the integer written into the block of step \(1\).

输入样例#1：

4
1 6 3 7 4 5 2

输出样例#1：

4

输入样例#2：

2
1 2 3

输出样例#2：

2

Constraints

• \(2\le N\le 10^5\);
• \((a_1,a_2, …… , a_{2N-1})\) is a permutation of \((1,2,……,2N-1)\).

题意：

    给定一个\(N\)及一个长度为\(2N-1\)的排列作为最下面一层。每往上一层会减少左右两边各一个数，剩下的数值是它下一层紧挨着的三个数的中位数。问当一层只剩一个数时剩下的数是多少。

题解：

    一开始什么都发现不了，手推也没有结果，最后打了暴力……

    这个题的正解做法以前是见过的，是二分答案。（bzoj4552排序）把小于等于mid的数置0，把比mid大的数置1，可以发现规律：

    一个格子的下面三个格子如果大于等于两个0，它就是0，否则它是1(会发现在哪里转化都是一样的)。因此如果最后一行的一部分01序列是交替的，那么上面一行也有一部分的01序列是交替的(上图第3,4列)。而一旦有连着相同的，那么上面一列全部都会变成这样，也就是说，例如00出现在一起，那么上面这一列都会变成00（可以手玩一下）。因为对于这两列来说，他们怎么在下面转移都是0。

    而这样是不是就有助于帮助我们解决子问题呢？其实不是子问题，我们继续向下看，整个问题都会迎刃而解。

    可以发现，因为连续的00或11垄断了边上的其他部分，所以最后中间段一定是01交替的，那么也因此垄断列会每次向内靠一格（每次都能找到一个相同元素而此元素作为中位数）所以会形成一个/两个类似上三角的结构。可以看出哪个垄断列与中间（第$ N$个数）隔得近，哪个就会先爬到第一层去。而我们知道最下面一层是0/1交替的，所以不会同时出现对称的00和11。

    如果只有一端有垄断列，那么答案就是这个垄断列的数值。而如果两端都没有，第一层就是最中间一个数\(\mathrm{xor} \ (n\mathrm{and} \ 1) \mathrm{xor} \ 1\)。(也是特殊情况手玩)。

    因此我们只要二分答案，如果最上面一个数得出是0，说明答案$ \le mid$，如果最上面一个数是1，说明答案$ \ge mid$。

Code：

#include<cstdio>
#include<cstring>
int a[2001000];//膜你赛数据开到了1e6
int b[2001000];
int n,L;
void turn(int x)//<=x的是0，>x的是1
{
    for(int i=1;i<=L;i++)
        if(a[i]<=x)
            b[i]=0;
        else
            b[i]=1;
}
int main()
{
    scanf("%d",&n);
    L=(n<<1)-1;
    for(int i=1;i<=L;i++)
        scanf("%d",&a[i]);
    int l=1,r=L,mid;
    while(l<r)
    {
        int flag=0;
        mid=(l+r>>1);
        turn(mid);
        for(int i=1;i<n;i++)//枚举从b[n]向左右扩展的长度
        {
            if(b[n+i]==b[n+i-1])
            {
                if(b[n+i]==0)
                    r=mid;
                else
                    l=mid+1;
                flag=1;
                break;
            }
            if(b[n-i]==b[n-i+1])
            {
                if(b[n-i]==0)
                    r=mid;
                else
                    l=mid+1;
                flag=1;
                break;
            }
        }
        if(!flag)//说明找不到垄断列
        {
            if(b[n]^(n&1)^1)
                l=mid+1;
            else
                r=mid;
        }
    }
    printf("%d\n",l);
    return 0;
}