 赛后题解)
题目传送门
思路
根据定义，用户终端 \(a\) 的顺序就是在树上从左往右的叶子节点。
可以发现建树时相当于每次选两个相邻的点，满足 \(|a_i-a_{i+1}|\le1\)，将他们连起来，父节点权值为 \(\min(a_i,a_{i+1})\)，即删掉其中更大的权值。
如果中间某一部无法再合并 或 剩下的唯一节点权值大于 0，则无解，否则有解。
考虑优先删大的点。
理由如下：
- 若没有相临的与其相等，则没有点能删掉他，删掉这一个点一定不更劣；
- 若有相临的与其相等，将这一段连续的最大值看作一个整体，没有点能删掉他们，提前删掉这一个点一定不更劣。
做法
优先队列维护当前最大的点，双向链表维护每个点的当前左、右侧的点。
（其实写复杂了，其中没有动态修改，优先队列可以改为 sort，然后遍历）
时间复杂度：\(O(T\times n \log_2 n)\)，可以通过 \(\sum n\le 2\times 10^5\)。
代码
#include<bits/stdc++.h>
using namespace std;
int a[200005], lst[200005], nex[200005];
void del(int pos)
{nex[lst[pos]] = nex[pos];lst[nex[pos]] = lst[pos];
}
signed main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);freopen("latency.in", "r", stdin);freopen("latency.out", "w", stdout);int _;cin >> _;while(_ --){int n;cin >> n;priority_queue<pair<int, int> > pq; //权值，编号a[0] = a[n + 1] = 2e9; //使双向链表更好维护for(int i = 1; i <= n; i ++){cin >> a[i];pq.push(make_pair(a[i], i));lst[i] = i - 1;nex[i] = i + 1;}while(pq.size() > 1){pair<int, int> u = pq.top();pq.pop();if(abs(a[u.second] - a[lst[u.second]]) <= 1|| abs(a[u.second] - a[nex[u.second]]) <= 1) //左右是否有能删掉这一位的{del(u.second);}else{cout << "NO" << endl;goto Nex; //别学我用 goto}}if(pq.top().first == 0) cout << "YES" << endl;else cout << "NO" << endl;Nex:;}return 0;
}