Constructive Problem

标签：operation int MEX test Problem Constructive cases array

Constructive Problem time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

As you know, any problem that does not require the use of complex data structures is considered constructive. You are offered to solve one of such problems.

You are given an array a of n non-negative integers. You are allowed to perform the following operation exactly once: choose some non-empty subsegment al,al+1,…,ar,+1,…, of the array a and a non-negative integer k, and assign value k to all elements of the array on the chosen subsegment.

The task is to find out whether MEX(a)MEX⁡() can be increased by exactly one by performing such an operation. In other words, if before the operation MEX(a)=mMEX⁡()= held, then after the operation it must hold that MEX(a)=m+1MEX⁡()=+1.

Recall that MEXMEX of a set of integers c1,c2,…,ck1,2,…, is defined as the smallest non-negative integer x which does not occur in the set c.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤500001≤≤50000) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer n (1≤n≤2000001≤≤200000) — the number of elements of array a.

The second line of each test case contains n integers a1,a2,…,an1,2,…, (0≤ai≤1090≤≤109) — elements of array a.

It is guaranteed that the sum n over all test cases does not exceed 200000200000.

Output

For each test case, print "Yes" if you can increase MEX(a)MEX⁡() by exactly one by performing the operation from the statement exactly once, otherwise print "No".

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Example input Copy 4 3 1 2 1 4 0 2 2 0 4 3 2 0 2 1 0 output Copy

Yes
Yes
No
No

Note

In the first test case, MEX(a)=0MEX⁡()=0. If you set all elements of a to 00, then MEXMEX of the resulting array will be 11, and thus will increase by one.

In the second test case, MEX(a)=1MEX⁡()=1. If we assign a value of 11 to the elements of a on a subsegment from 22 to 33, we get an array [0,1,1,0][0,1,1,0] for which MEXMEX is 22, and thus is increased by one compared to the original.

It can be shown that in the third and fourth test cases it is impossible to perform an operation so that the value of MEX(a)MEX⁡() increases by exactly one.

 

#include <bits/stdc++.h>
//#define int long long
using namespace std;
const int N=2e5+10,mod=1e9+7;
string s;
int n,t,a[N],f[N],res,num,ans,m;
bool vis[N];
int mex()//寻找mex
{
    unordered_map<int,int>g;
    for(int i=0;i<n;i++) g[a[i]]=1;
    for(int i=0;i<=n;i++)
        if(!g.count(i)) return i;
}
int main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=0;i<n;i++) cin>>a[i];
        num=mex();
        int l=-1,r=-1;
        for(int i=0;i<n;i++){//这一步是记录下来数组里k+1的左端点和右端点
            if(a[i]==num+1){
                if(l==-1) l=i;
                r=i;
            }
        }
        if(l==-1&&r==-1){//如果数组里面没有k+1,那么要判断
        //如果k>=n的话就不行,例如 0 1 2 3 ,k=4,那就不行,因为数不够,否则就可以
            if(num<n) cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
            continue;
        }
        else{
            for(int i=l;i<=r;i++) a[i]=num;//改完之后再判断一次
            ans=mex();
            if(ans==num+1) cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }
    }
    return 0;
}

 

标签：operation,int,MEX,test,Problem,Constructive,cases,array
From： https://www.cnblogs.com/o-Sakurajimamai-o/p/17517682.html