题面

Great Vova Wall (Version 2)

Vova 的家族正在建造伟大的 Vova 墙（这个名字是 Vova 自己起的）。Vova 的父母、祖父母、曾祖父母都为此做出了贡献。现在，最后的收尾工作完全交给了 Vova。

当前墙的状态可以用一个长度为 $n$ 的整数序列 $a$ 表示，其中 $a_i$ 表示第 $i$ 段墙的高度。

Vova 只能使用 $2\times 1$ 的砖块（他有无限多这样的砖块）。

Vova 只能将砖块水平放置在相邻且高度相等的墙段上。也就是说，如果对于某个 $i$，第 $i$ 段和第 $i+1$ 段的当前高度相同，那么 Vova 可以在这两个位置放置一块砖，从而使这两段的高度都增加 $1$。显然，Vova 不能把砖块放在墙的边界之外（不能放在第 $1$ 段的左边或第 $n$ 段的右边）。

注意，Vova 不能竖直放置砖块。

Vova 是个完美主义者，他认为墙完成的标准是：

• 墙的所有部分高度都相同；
• 墙内部没有空隙。

Vova 能否使用任意数量的砖块（可以为零）完成这堵墙？

输入格式

第一行包含一个整数 $n$（$1\le n\le 2\times 10^5$），表示墙的段数。

第二行包含 $n$ 个整数 $a_1,a_2,\dots ,a_n$（$1\le a_i\le 10^9$），表示每段墙的初始高度。

输出格式

如果 Vova 能够使用任意数量的砖块（可以为零）完成这堵墙，输出 YES。

否则，输出 NO。

思路

$\text{tag}$：math

对于一面墙，若墙在 $[l,r]$ 区间可砌，则 $a_{l-1}=a_{r+1}$ 时，$[l-1,r+1]$ 必然可砌。这类似一个合法括号序列问题，相同的 $a_i$ 为一组括号，若去除首尾的前后缀，墙是一个合法的括号序列，则墙可砌。

不同于版本1，由于不可将单独一个 $a_i$ 增加，故在高的一对、无法与其他砖配对的砖之间只能存在比它们低的砖（若高度相等可直接与之配对），所以在遍历序列时，不仅要判断是否相等，还需判断大小关系。

于是对于 $a_1\&1,a_2\&2,\cdots ,a_n\&1$ 和 $1-(a_1\&1),1-(a_2\&2),\cdots ,1-(a_n\&1)$，用一个栈存储 $a$，对于所有 $1\le i\le n$ 的 $a_i$，若 $a_i$ 与 栈顶数字相等，则栈顶数字出栈；若 $a_i$ 小于栈顶数字，则整个墙一定不可砌；否则 $a_i$ 出栈。若墙可砌，则最后栈中最多剩余一个数，若剩余，则必为全墙最大数字；否则墙不可砌。

时间复杂度 $O(n)$。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e5+5;
int a[maxn];
int n;
map<signed,int> num;
vector<int> vec;
bool check(){
	int limit=0;
	stack<int> s;
	for(int i=1;i<=n;i++){
		limit=max(limit,a[i]);
		if(s.empty()){
			s.push(a[i]);
			continue;
		}
		int x=s.top();
		if(x<a[i]) return 0;
		if(x>a[i]){
			s.push(a[i]);
		}else{
			s.pop();
		}
	}
	if(s.empty()) return 1;
	while(!s.empty()){
		if(limit!=s.top()) return 0;
		s.pop();
	}
	return 1;
}
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		vec.push_back(a[i]);
	}
	if(n<2){
		cout<<"YES\n";
		return;
	}
	if(check()) cout<<"YES\n";
	else cout<<"NO\n";
}
signed main(){
	ios::sync_with_stdio(0);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t=1;
	while(t--){
		solve();
	}
	return 0;
}

另附：题解：CF1092D1