Fərqli ədədlərin sayı (Həll təhlili)

İdeya

$n$ uzunluğunda gizli $a$ massivimiz var. Hər sorğu indekslərin permutasiyasıdır və cavab olaraq hər element üçün seçdiyimiz sıralamada neçə qonşusunun eyni qiymətə malik olduğunu öyrənirik. Massivdəki fərqli ədədlərin sayını ən çox \frac{n}{2} + 1 sorğu ilə tapmaq lazımdır.

Əsas müşahidə 1: qonşu bərabərliklərin bərpası

Tutaq ki, hər hansı permutasiya ilə sorğu etdik və $b$ massivini aldıq. \text{eq}[i] = 1 olsun, əgər p_i = p_{i+1}, əks halda $0$. Onda:

Buradan bütün $\text{eq}[i]$ qiymətlərini ardıcıl bərpa edə bilərik:

Beləliklə, bir sorğudan permutasiyamızdakı hər qonşu cüt üçün $a$ massivində eyni qiymətə malik olub-olmadığını öyrənirik.

Əsas müşahidə 2: bütün cütlərin əhatəsi

Hansı indekslərin eyni qiymətə malik olduğunu tam müəyyən etmək üçün hər indeks cütü $(i,j)$ ən azı bir sorğuda qonşu olmalıdır.

Bu klassik round-robin turnir planlaşdırması məsələsidir: $n$ oyunçu hər kəslə oynayır və hər turda hər oyunçu tam bir oyun oynayır. Cüt $n$ üçün n - 1 tur lazımdır, lakin bizə yalnız \frac{n}{2} tur kifayətdir, burada hər tur qonşu cütləri bütün lazımi cütləri əhatə edən permutasiya verir.

Konstruksiya belədir: əgər $n$ təkdirsə, m = n + 1-ə (cüt) qədər tamamlayırıq. Sonra hər tur k = 0, 1, \ldots, \frac{m}{2} - 1 üçün $k$ elementindən başlayaraq, k - 1, k + 1, k - 2, k + 2, \ldots elementlərini növbələşdirərək, k + \frac{m}{2} elementi ilə bitirərək permutasiya qururuq (bütün indekslər $m$ üzrə modulda götürülür; əgər indeks $\ge n$ — onu atlayırıq).

Bu tam \frac{n}{2} (yuxarı yuvarlaqlaşdırılmış) sorğu verir ki, bu da \frac{n}{2} + 1 limitinə uyğundur.

Nəticələrin DSU ilə birləşdirilməsi

DSU (Disjoint Set Union) strukturu saxlayırıq. Hər sorğudan sonra, əgər \text{eq}[i] = 1 olarsa, $q[i]$ və q[i+1] indekslərini birləşdiririk ($q$ — bizim permutasiyamızdır). Bütün sorğulardan sonra DSU-dakı komponentlərin sayı cavabdır — massivdəki fərqli qiymətlərin sayı.

Bu niyə doğrudur?

İki indeks $i$ və $j$ eyni DSU komponentinə düşür ancaq və ancaq a_i = a_j olduqda. Əgər a_i = a_j olarsa, onların qonşu olduğu sorğuda \text{eq} = 1 alırıq və onları birləşdiririk. Əgər a_i \neq a_j olarsa, onlar heç vaxt birləşdirilmir, çünki qonşu olduqları hər sorğuda \text{eq} = 0 olur.

Tranzitivliyi DSU təmin edir: əgər a_i = a_j və a_j = a_k olarsa, $(i,k)$ cütü birbaşa qonşu kimi yoxlanmasa belə, hər üçü eyni komponentə düşür.

Asimptotika

Sorğuların sayı: O\!\left(\frac{n}{2}\right).

Permutasiyaların qurulması: O(n^2).

Evristikalarla DSU: hər sorğu üçün O(n \cdot \alpha(n)).

Ümumi: O(n^2), bu n \le 2 \cdot 10^3 üçün sürətlə işləyir.

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> p, sz;
    DSU(int n = 0) {
        p.resize(n);
        sz.assign(n, 1);
        iota(p.begin(), p.end(), 0);
    }
    int find(int v) {
        return p[v] == v ? v : p[v] = find(p[v]);
    }
    void unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return;
        if (sz[a] < sz[b]) swap(a, b);
        p[b] = a;
        sz[a] += sz[b];
    }
};

vector<vector<int>> build_queries(int n) {
    int m = n + n % 2;
    vector<vector<int>> queries;
    for (int k = 0; k < m / 2; k++) {
        vector<int> q;
        auto add = [&](int x) {
            x = (x % m + m) % m;
            if (x < n) q.push_back(x);
        };
        add(k);
        for (int t = 1; t <= m / 2 - 1; t++) {
            add(k - t);
            add(k + t);
        }
        add(k + m / 2);
        queries.push_back(q);
    }
    return queries;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;

    DSU dsu(n);
    auto queries = build_queries(n);

    for (auto &q : queries) {
        cout << "? ";
        for (int i = 0; i < n; i++) {
            if (i) cout << ' ';
            cout << q[i] + 1;
        }
        cout << endl;

        vector<int> b(n);
        for (int i = 0; i < n; i++) cin >> b[i];

        if (n == 1) continue;

        vector<int> eq(n - 1);
        eq[0] = b[0];
        for (int i = 1; i < n - 1; i++)
            eq[i] = b[i] - eq[i - 1];

        for (int i = 0; i < n - 1; i++)
            if (eq[i] == 1)
                dsu.unite(q[i], q[i + 1]);
    }

    int ans = 0;
    for (int i = 0; i < n; i++)
        if (dsu.find(i) == i) ans++;

    cout << "! " << ans << endl;
    return 0;
}