Gọi ~mi_a~ là giá trị nhỏ nhất của mảng ~a~, ~ma_a~ là giá trị lớn nhất của mảng ~a~, ~x~ là giá trị cần tạo.

Nhận xét: Nếu ~mi_a \le x \le ma_a~ thì ta sẽ tạo được số ~x~ từ mảng ~a~.

Chứng minh: Sau khi thực hiện ~n - 1~ thao tác, ta cần đạt được ~mi_a = ma_a = x~. Ta chứng minh được sau mỗi thao tác, ~mi_a~ sẽ không giảm và ~ma_a~ sẽ không tăng, ta sẽ chia ra ~2~ trường hợp sau:

• ~x < mi_a~ hoặc ~ma_a < x~: Vì ~mi_a~ sẽ không giảm và ~ma_a~ sẽ không tăng sau mỗi thao tác nên điều kiện ~mi_a = ma_a = x~ sẽ không thể đạt được.

• ~mi_a \le x \le ma_a~: Ta có thể thực hiện tạo số ~x~ bằng cách sau: Chọn ~2~ số tương ứng với ~mi_a~ và ~ma_a~, xóa ~2~ số đi, thêm ~x~ vào. Sau đó, ở ~n - 2~ thao tác còn lại, chọn số ~x~ và một số bất kỳ trong mảng, xóa ~2~ số này và tiếp tục thêm số ~x~ vào. Dễ thấy, số còn lại trong mảng luôn là ~x~.

Độ phức tạp: ~O(n + q)~.

Code mẫu

//TrungNotChung
#include <bits/stdc++.h>
#define pii pair<int , int>
#define fi first
#define se second
#define BIT(x,i) (1&((x)>>(i)))
#define MASK(x)  (1LL<<(x))
#define CNT(x) __builtin_popcountll(x)
#define task "tnc"  

using namespace std;
const int N = (int)1e5+228;
const int INF = (int)1e9+7;

int n, q, a[N];

void solve()
{
    cin >> n >> q;
    for(int i=1; i<=n; ++i) cin >> a[i];

    int mi = INF, ma = -INF;
    for(int i=1; i<=n; ++i)
    {
        mi = min(mi, a[i]);
        ma = max(ma, a[i]);
    }

    while(q--)
    {
        int x; 
        cin >> x;
        if(x < mi || x > ma) cout << "No\n";
        else cout << "Yes\n";
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    #ifndef ONLINE_JUDGE
    freopen(task".inp","r",stdin);
    freopen(task".out","w",stdout);
    #endif // ONLINE_JUDGE
    solve();
    return 0;
}