~cnt_x~ là số lần xuất hiện giá trị ~x~ trong đoạn con độ dài ~k~ đang xét

~f_x~ là số lượng số là bội của ~x~ trong đoạn con độ dài ~k~ đang xét

Đồng thời ta sẽ chuẩn bị trước ước của tất cả các giá trị trong đoạn ~[1,10^5]~

Để tìm số lượng số có nhiều bội nhất và nhỏ nhất thì sử dụng priority queue. Khi xoá ~1~ số khỏi dãy độ dài ~k~, ta gỉảm số lượng bội của mỗi ước đi ~1~. Khi thêm ~1~ số vào dãy độ dài ~k~, ta tăng số lượng bội của mỗi ước lên ~1~, nếu số này có ~cnt_x > 0~ thì mình sẽ cho lại vào priority queue Lúc này khi trả lời truy vấn thì đáp án sẽ là những giá trị đầu tiên trong priority queue, nếu giá trị của nó đang bị sai thì cập nhật lại, còn không thì in ra kết quả.

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 MAX = (int)1e5;

vector<int> divs[N];
int n, k, a[N];
int cnt[N], f[N];
priority_queue<pii, vector<pii>, less<pii> > pq;

void solve()
{
    for(int i=1; i<=MAX; ++i)
    {
        for(int j=i; j<=MAX; j+=i) divs[j].push_back(i);
    }
    cin >> n >> k;
    for(int i=1; i<=n; ++i) cin >> a[i];
    for(int i=1; i<=k; ++i)
    {
        for(int j=0; j<(int)divs[a[i]].size(); ++j)
        {
            int x = divs[a[i]][j];
            f[x]++;
        }
    }

    for(int i=1; i<=k; ++i)
    {
        cnt[a[i]]++;
        if(cnt[a[i]] == 1) pq.push(make_pair(f[a[i]], -a[i]));
    }

    for(int i=1; i+k-1 <= n; ++i)
    {
        while(pq.size())
        {
            int x = -pq.top().se, c = pq.top().fi;
            if(f[x] == c && cnt[x] > 0) break;
            pq.pop();
            if(cnt[x] > 0 && f[x] > 0) pq.push(make_pair(f[x], -x));
        }
        assert((int)pq.size() > 0);
        cout << -pq.top().se << " ";
        if(i >= 1)
        {
            for(int j=0; j<(int)divs[a[i]].size(); ++j)
            {
                int x = divs[a[i]][j];
                f[x]--;
            }
            cnt[a[i]]--;
        }
        if(i+k <= n)
        {
            for(int j=0; j<(int)divs[a[i+k]].size(); ++j)
            {
                int x = divs[a[i+k]][j];
                f[x]++;
                if(cnt[x] > 0 && x != a[i+k]) pq.push(make_pair(f[x], -x));
            }
            cnt[a[i+k]]++;
            pq.push(make_pair(f[a[i+k]], -a[i+k]));
        }
    }
}

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;
}