A. Constructive Problem

题意:给定一个长度为n的非负数组a,我们可以进行一次操作,操作是将l~r这个区间内的所有数变为k(k >= 0),得到b,能不能使mex(a)+ 1 = mex(b)

思路:我是先排了个序,去了一下重,然后得到的这个数组其实只有两种情况
7fadb345668574e200b410c44f14b05.jpg
cdc76ad46ad0e20e462b088d676162b.jpg
一种每两个数之间的增量为1
一种是每两个数之间的增量大于1
对于第一种情况
我们考虑原数组大小如果和去重后数组大小相同,这种情况是不能增大的
否则说明有重复元素,我们只需要将重复元素变为n+1即可也就是说一定有解
对于第二种情况
我们考虑第一个增量不为一的地方
假如这个地方的增量为2这样我们就需要将这包含这个数的最小区间内的所有数变成mex(a)+1
然后扫一遍check以下就做完了
假如第一个增量不为一的地方的增量>=3则一定有解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int a[N], n;
vector<int>b;
void run()
{
b.clear();
cin >> n;
for(int i = 1; i <= n; ++ i) scanf("%d", &a[i]), b.push_back(a[i]);
sort(b.begin(), b.end());
if(n == 1 && a[1] == 0)
{
puts("NO");
return;
}
b.erase(unique(b.begin(), b.end()), b.end());
if(b[0] != 0)
{
puts("YES");
return;
}
if(b.size() - 1 == b[b.size() - 1])
{
if(n == b.size())
{
puts("NO");
return;
}
else
{
puts("YES");
return;
}
}
int t = 0;
for(int i = 0; i < b.size(); ++ i)
{
if(b[i] != i) break;
t = i;
}
if(b[t + 1] - b[t] >= 3) puts("YES");
else
{
int l = 0, r = 0;
for(int i = 1; i <= n; ++ i)
{
if(a[i] == b[t + 1])
{
l = i;
break;
}
}
for(int i = n; i >= 1; -- i)
{
if(a[i] == b[t + 1])
{
r = i;
break;
}
}
map<int, int>mp;
for(int i = 1; i <= n; ++ i)
{
if(i >= l && i <= r) continue;
mp[a[i]] = 1;
}
for(int i = 0; i <= b[t]; ++ i)
{
if(mp.find(i) == mp.end())
{
puts("NO");
return;
}
}
puts("YES");
}
}

int main()
{
// freopen("1.in", "r", stdin);
int t;cin >> t;
while(t --) run();
return 0;
}