Subtask 1

Dễ dàng nhận thấy, số lớn thứ ~k~ trong dãy có giá trị ~a_1 \cdot k~.

Subtask 2

Ta gọi ~minValue~ là giá trị nhỏ nhất của mảng ~a~.

Ta có mảng ~f~ với ~f_i~ ~(0 \leq i < minValue)~ là số có giá trị nhỏ nhất trong dãy ~b~ chia ~minValue~ dư ~i~. Dựng một đồ thị gồm ~minValue~ đỉnh đánh số lần lượt từ ~0, 1, ..., minValue - 1~, nối cạnh ~u~ ~\rightarrow~ ~(u + a_i)~ ~\%~ ~minValue~ trọng số ~a_i~. Vì ~a_1 + a_2 + ...+ a_n \leq 10^6~ ~\Rightarrow~ ~minValue \leq \frac{10^6}{n}~, mỗi đỉnh có tối đa ~n-1~ cạnh nên đồ thị của ta có không quá ~\frac{10^6}{n} \cdot (n-1) \leq 10^6~ cạnh. Giả sử dãy ~b~ có chứa cả giá trị ~0~, ta đặt ~f_0 = 0~ và dùng thuật toán Dijkstra để tính mảng ~f~.

Độ phức tạp: ~O(n \cdot minValue \cdot log2(minValue))~

Từ mảng ~f~, ta suy ra số nhỏ thứ nhì chia ~minValue~ dư ~i~ là ~f_i + minValue~, số nhỏ thứ ba chia minValue dư ~i~ là ~f_i + minValue \cdot 2~, ..., số nhỏ thứ ~x~ chia minValue dư ~i~ là ~f_i + minValue \cdot (x-1)~.

Để tìm số lớn thứ ~k~ của dãy ~b~, ta dùng thuật toán chặt nhị phân các giá trị từ ~1~ đến ~10^{15}~). Để kiểm tra xem đáp án có ~\leq mid~ hay không, ta đếm số lượng giá trị của mảng ~b \leq mid~ bằng cách xét các giá trị ~f_i \leq mid~, lấy tổng ~cnt = \frac{mid}{minValue} - \frac{f_i}{minValue} + (mid \% minValue \geq f_i \% minValue)~. Nếu ~cnt \geq (k+1)~ thì đáp án sẽ ~\leq mid~ (~+1~ do không tính giá trị ~0~).

Độ phức tạp: ~O(q \cdot log2(10^{15}) \cdot minValue)~.

Subtask 3

Ta tính mảng ~f~ tương tự Subtask 2. Vì ~k \leq 5000~ nên ta có thể chuẩn bị trước các giá trị của mảng ~b~ bằng cách dùng cấu trúc dữ liệu priority_queue. Ban đầu ta cho hết tất cả các giá trị ~f_i~ vào trong priority_queue. Tại mỗi lượt, gọi ~cur~ là giá trị nhỏ nhất trong priority_queue hiện tại, ta lấy ~cur~ ra, cho giá trị ~cur~ vào mảng ~b~ và thêm giá trị ~cur + minValue~ vào lại priority_queue.

ĐPT phần này là ~O(5000 \cdot log2(minValue)~.

Subtask 4

Ta tính mảng ~f~ tương tự Subtask 2. Ta sort các giá trị của mảng ~f~ tăng dần và sort các truy vấn tăng dần theo giá trị ~k~. Sử dụng kĩ thuật sweep line để tính đáp án. Ta chia các giá trị ~i~ là dư khi chia cho ~minValue~ vào các nhóm có chỉ số ~\frac{f_i}{minValue}~.

Gọi ~sz_i~ là số lượng giá trị dư thuộc các nhóm có chỉ số ~\leq i~, ~g_i~ là số lượng số thuộc mảng ~b~ có giá trị ~< i \cdot minValue~. Ta có ~g_i~ = ~g_j~ + ~sz_j \cdot (j - i)~ với ~j~ là chỉ số nhóm lớn nhất ~< i~. Ta xác định được chỉ số ~x~ max trong số các nhóm mà ~g_x \leq k~, đặt ~tmp = k - g_x~. Đáp án của câu hỏi số lớn thứ ~k~ trong dãy ~b~ là ~(\frac{tmp}{sz_x} + x) \cdot minValue)~ + giá trị dư lớn thứ ~tmp \% sz_x + 1~ trong số các giá trị dư thuộc nhóm có chỉ số ~\leq x~.

Ta dùng cấu trúc dữ liệu Ordered Set để thuận tiện cho việc tính toán.

Độ phức tạp: ~O((minValue + q) \cdot log2(minValue))~.

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"
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
using namespace __gnu_pbds;

using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = (int)3e5+228;
const int M = (int)1e6+228;
const int INF = (int)1e9;
const long long INFLL = (long long)1e18;

int n, q, a[N], b[N];
long long f[M], res[N];

void solve()
{
    cin >> n >> q;
    for(int i=1; i<=n; ++i) cin >> a[i];
    memset(f, 0x3f, sizeof(f));
    int mi = a[1];
    for(int i=1; i<=n; ++i) mi = min(mi, a[i]);
    priority_queue<pair<long long, int>, vector<pair<long long, int> >, greater<pair<long long, int> > > pq;
    f[0] = 0;
    pq.push(make_pair(0, 0));
    while(pq.size())
    {
        long long value = pq.top().fi;
        int x = pq.top().se;
        pq.pop();
        if(f[x] != value) continue;
        for(int i=1; i<=n; ++i)
        {
            int y = (x + a[i]) % mi;
            if(f[y] > value + a[i])
            {
                f[y] = value + a[i];
                pq.push(make_pair(f[y], y));
            }
        }
    }
    // cout << q << '\n';
    vector<pair<long long, int> > g;
    for(int i=0; i<mi; ++i) if(f[i] < INFLL) g.push_back(make_pair(f[i], i));
    sort(g.begin(), g.end());

    vector<pii> qu(q);
    for(int i=0; i<q; ++i)
    {
        cin >> qu[i].fi;
        qu[i].se = i+1;
    }
    sort(qu.begin(), qu.end());

    int lst = 0, sz = 0;
    long long cnt = 0;
    int cur = 0;
    ordered_set ods;

    for(int i=0; i<=(int)g.size();)
    {
        // cout << lst << " " << sz << " ";
        long long nextCnt = (i == (int)g.size() ? INFLL : cnt + 1LL * (g[i].fi / mi - lst) * sz);
        // cout << nextCnt << ":\n";
        while(cur < (int)qu.size() && qu[cur].fi < nextCnt)
        {
            // cout << qu[cur].fi << " " << qu[cur].se << " " << '\n';
            int k = qu[cur].fi - cnt;
            int id = qu[cur].se;
            res[id] = 1LL * (k / sz + lst) * mi + *ods.find_by_order(k % sz);
            ++cur;
        }
        if(i == (int)g.size()) break;
        int sta = i;
        while(i != (int)g.size() && g[i].fi / mi == g[sta].fi / mi)
        {
            ods.insert(g[i].se);
            ++sz;
            cnt = nextCnt;
            if(cnt > INF) break;
            lst = g[i].fi / mi;
            ++i;
        }
        if(cnt > INF) break;
    }

    for(int i=1; i<=q; ++i) cout << res[i] << '\n';

}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen(task".inp" , "r" , stdin);
    //freopen(task".out" , "w" , stdout);
    solve();
    return 0;
}