1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
#include <iostream>
#include <set>
#include <vector>
#include <chrono>
#include <random>
using namespace std;

//#define DEBUG_BIG
//#define DEBUG

int n, q, a, result = 0, ostatni_wynik_dla_malych = 0;
bool dodany = false;

int sito[10000001], indeksy_vectora[10000001];
vector<int> pierwsze, liczby_vector;
vector<int> wyniki[1001];
int wyniki_set[1000001];

bool isPrime(int n) {
    for (int i = 0; i < pierwsze.size(); i++) {
        if (n % pierwsze[i] == 0) return false;
    }

    return true;
}

void zrobSito() {
    for (int i = 2; i <= n; i++) {
        if (!sito[i]) {
            for (int j = i; j <= n; j += i) {
                if (!sito[j]) sito[j] = i;
            }
        }
    }
}

void wczytaj_a() {
    cin >> a;

    if (indeksy_vectora[a] == -1) {
        indeksy_vectora[a] = liczby_vector.size();
        liczby_vector.push_back(a);
        dodany = true;
    } else {
        int ostatnia_liczba = liczby_vector[liczby_vector.size()-1];
        liczby_vector[indeksy_vectora[a]] = ostatnia_liczba;
        indeksy_vectora[ostatnia_liczba] = indeksy_vectora[a];
        indeksy_vectora[a] = -1;
        liczby_vector.pop_back();
        dodany = false;
    }

    #ifdef DEBUG
    cout << "WCZYTANE!" << endl;
    #endif // DEBUG
}

int daj_wynik_na_bruta() {
    int zmiana = dodany ? 1 : -1;

    for (int i = 0; i < pierwsze.size(); i++) {
        int k = pierwsze[i];
        #ifdef DEBUG
        cout << "K: " << k << endl;
        #endif // DEBUG
        if (wyniki_set[wyniki[k][a%k]]) {
            wyniki_set[wyniki[k][a%k]]--;
            #ifdef DEBUG
            cout << "WYNIK: " << wyniki[k][a%k] << " USUNIETY " << endl;
            #endif // DEBUG
        }
        #ifdef DEBUG
        cout << "CZAS NA ZMIANE" << endl;
        #endif // DEBUG
        wyniki[k][a%k] += zmiana;
        wyniki_set[wyniki[k][a%k]]++;
        #ifdef DEBUG
        cout << "WYNIK: " << wyniki[k][a%k] << " DODANY " << endl;
        #endif // DEBUG
    }

    if (wyniki_set[ostatni_wynik_dla_malych+1]) {
        ostatni_wynik_dla_malych++;
        return ostatni_wynik_dla_malych;
    }
    if (wyniki_set[ostatni_wynik_dla_malych]) {
        return ostatni_wynik_dla_malych;
    }
    ostatni_wynik_dla_malych--;
    return ostatni_wynik_dla_malych;
}

void duze_liczby() {
    int ostatni_wynik = 0;

    zrobSito();
    #ifdef DEBUG_BIG
    cout << "SITO ZROBIONE" << endl;
    #endif // DEBUG_BIG

    unsigned seed = chrono::system_clock::now().time_since_epoch().count();
    mt19937 generator (seed);

    for (int i = 2; i < 1000; i++) {
        if (isPrime(i)) {
            pierwsze.push_back(i);
            vector<int> V(i);
            wyniki[i] = V;
        }
    }

    while (q--) {
        wczytaj_a();

        int wynik_dla_malych = daj_wynik_na_bruta(), najlepszy_mozliwy = ostatni_wynik + (int)dodany;

        #ifdef DEBUG_BIG
        cout << "WYNIK DLA MALYCH: " << wynik_dla_malych << endl;
        #endif // DEBUG_BIG

        if (liczby_vector.size() <= 2) {
            ostatni_wynik = liczby_vector.size();
            cout << ostatni_wynik << endl;
            continue;
        }

        if (n <= 1009 || wynik_dla_malych == najlepszy_mozliwy) {
            // Jesli dodawalismy, to moglismy ulepszyc wynik o max 1, jesli odejmowalismy, to max zostal taki sam.
            #ifdef DEBUG_BIG
            cout << "MALE SIE SPISALY" << endl;
            #endif // DEBUG
            ostatni_wynik = wynik_dla_malych;
            cout << wynik_dla_malych << endl;
            continue;
        }

        set<pair<int, int>> kandydaci;

        if (dodany) {
            // Bierzemy roznice z innymi liczbami. Jako ze wynik jest co najmniej 1/2 liczby liczb, to mamy 1/2^K
            // szansy ze chybimy, gdzie K to liczba kandydatow.
            for (int i = 0; i < 25; i++) {
                int wylosowane = liczby_vector[generator() % liczby_vector.size()];
                int roznica = abs(wylosowane - a);

                #ifdef DEBUG_BIG
                cout << "WYLOSOWALEM " << wylosowane << endl;
                #endif // DEBUG

                while (roznica > 1) {
                    #ifdef DEBUG_BIG
                    cout << "KANDYDAT: " << sito[roznica] << endl;
                    #endif // DEBUG
                    kandydaci.insert(make_pair(sito[roznica], a));
                    roznica /= sito[roznica];
                }
            }
        } else {
            // Wywalilismy liczbe, losujemy zatem pary. Kazdy element pary ma >50% szansy byc w wyniku, czyli para ma >25%.
            // Zeby miec sensowna szanse przy milionie zapytan (pol miliona usuniec), chcemy 42 - to daje nam ~1/500000.
            // Poza tym 42 jest zawsze odpowiedzia :D
            for (int i = 0; i < 42; i++) {
                int wylosowane = liczby_vector[generator() % liczby_vector.size()];
                int roznica = abs(wylosowane - liczby_vector[generator() % liczby_vector.size()]);

                while (roznica > 1) {
                    kandydaci.insert(make_pair(sito[roznica], wylosowane % sito[roznica]));
                    roznica /= sito[roznica];
                }
            }
        }

        // Jak dodajemy, to wynik sie na pewno nie pogorszyl, jak usuwamy, to pogorszyl sie max o 1.
        int best = dodany ? max(wynik_dla_malych, ostatni_wynik) : max(wynik_dla_malych, ostatni_wynik-1);

        for (auto it = kandydaci.begin(); it != kandydaci.end(); it++) {
            int wynik = 0;
            int kandydat = (*it).first;
            int start = (*it).second;
            #ifdef DEBUG_BIG
            cout << "TESTUJE KANDYDATA: " << kandydat << endl;
            #endif // DEBUG_BIG

            for (int i = start % kandydat; i <= n; i+= kandydat) {
                if (indeksy_vectora[i] == -1) continue;

                wynik++;

                if (wynik + (n-i)/kandydat < best) break;
            }

            #ifdef DEBUG_BIG
            cout << "WYNIK: " << wynik << endl;
            #endif // DEBUG_BIG

            best = max(best, wynik);
            if (best == najlepszy_mozliwy) break;
        }

        ostatni_wynik = best;
        cout << best << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(0);

    cin >> n >> q;

    for (int i = 0; i <= n; i++) {
        indeksy_vectora[i] = -1;
    }

    if (n > 1000) {
        duze_liczby();
        return 0;
    }

    for (int i = 2; i < n; i++) {
        if (isPrime(i)) {
            pierwsze.push_back(i);
            vector<int> V(i);
            wyniki[i] = V;
        }
    }

    #ifdef DEBUG
    cout << "PIERWSZE POLICZONE" << endl;
    #endif

    while (q--) {
        wczytaj_a();

        cout << daj_wynik_na_bruta() << endl;
    }
}