[??记录]AT2165 [AGC006D] Median Pyramid Hard

**题意** ： 给出一个 $N$ 层方格金字塔，自顶向下依次标号为第 $1$ 到第 $N$ 层。 其中第 $i$ 层有 $2i − 1$ 个方格。（具体形态见图）  第 $N$ 层有一个 $1$ 到 $2N-1$ 的排列，其他层的数字按以下规则生成：方格 $b$ 中填写的整数，是方格 $b$ 正下方，左下方和右下方方格中所写整数的中位数。 现在给出第 $N$ 层的数字，求第一层的数字。 $N\leq 10^5$ ,时限 $\texttt{2s}$。 ------------ 中位数和大小比较有关，考虑二分答案。 若数 $\leq mid$ 则设为 $0$ ，否则设为 $1$。 则金字塔的生成方法可以改为 ： 若下方的三个格子中 $1$ 多则填 $1$ ，否则填写 $0$。 若最终第一层的数字为 $0$ 则表示答案 $\leq mid$ ，否则 $>mid$。 现在问题变为快速求解 $01$ 金字塔。 这个问题似乎很有规律，手玩可以发现，若有两个相邻的 $0/1$ ，就会一直向上传递到顶。 （不懂手玩……规则简单/偏组合就手玩，复杂就分析？） 而且，两个的相邻 $0/1$ 会吞噬周围孤立的 $0/1$。  综合上述两条，不难发现，答案是距离中心最近的对子的值。 由于底端长为奇数，可以证明不会出现两个距离中心一样近的对子。 然而，一种特殊情况是没有任何对子，特判掉就好了。 复杂度 $O(n\log n)$。 ```cpp #include<algorithm> #include<cstdio> #define MaxN 200500 using namespace std; int n,a[MaxN];bool b[MaxN]; bool chk(int lim) { for (int i=1;i<=2*n-1;i++)b[i]=(a[i]>=lim); int dis=n,fl; for (int i=1;i<n;i++) if (b[i]==b[i+1]&&n-i<dis) {dis=n-i;fl=b[i];} for (int i=n+1;i<=n*2-1;i++) if (b[i-1]==b[i]&&i-n<dis) {dis=i-n;fl=b[i];} return (dis==n) ? b[1] : fl; } int main() { scanf("%d",&n); for (int i=1;i<=n*2-1;i++)scanf("%d",&a[i]); int l=1,r=n*2-1,mid; while(l<r){ mid=(l+r+1)>>1; if (chk(mid))l=mid; else r=mid-1; }printf("%d",l); return 0; } ```