题意

给定 $n,q(n\le 10 ^ 7,q\le 10^6)$，对一个初始为空集的集合 $S$ 做如下操作：给定一个 $x(1 \le x \le n)$，若集合中含 $x$ 则删除，不含就加入，每次操作后问对于所有可能 $m \ge 2,k$，集合中能表示成 $ms + k$ 的数有多少个？

关于答案的特性

首先通过取 $m = 2$ 的同时 $k$ 在 $0$ 或者 $1$ 中任选，可以得到一个超过 $\frac{|S|}{2}$ 的答案，而且总有最优解在 $m$ 为质数时取到，这样就可以处理单次询问，但是难点其实在多次询问，注意到当修改次数不大于 $\frac{|S|}{4}$ 时答案所包含的元素中至少有 $\frac{3|S|}{8}$ 个点是原集合中保留的元素，这样就可以将单组询问的做法推广到多组询问的均摊做法。

分组处理

考虑当集合大小不大于 $3$ 的时候特判，否则对所有元素每 $6$ 个一组，每组每一对求出差的所有质因数，其中集合元素用链表处理，质因数考虑在线性筛时求出每个数的最小质因子和彻底除去这个质因子得到的数，可以得到一个高度为 $\omega(n)$ 的有根数，每次记录最小质因子并跳到完全去除后的结果即可。

这样下来我们根据前面的结论得出当一个质数被这轮操作记录为 $\frac{3|S|}{16}$ 时这个质数才有可能是取到答案的 $m$，枚举这样的质数，离线维护本询问和后续操作的元素对应的余数分布，维护的操作规模 $\frac{|S|}{4}$，我们枚举到 $\frac{5|S|}{2}$ 个对，至多在后续操作中枚举 $\frac{40}{3}\omega(n)$ 个质数，最终得到 $n + q\omega(n)$ 的做法。

最后要注意的是，虽然时空限制比较友好，但毕竟 $n,q$ 比正常的大，请加上快读并且慎用 stl :: vector。

#include<bits/stdc++.h>
using namespace std;
const int N = 10000009,Q = 1000009,PR = 700009;
int n,q,prv[N],nxt[N],a[Q],cnt,fcnt[Q],fmx,ans[Q]; 
int prcnt,pr[PR],prid[N];
int beg = 0,ed = 0;
bool npr[N],exi[N];
int dft[PR],minpr[N],to[N];
bool dst[PR];
int dat[5009],dlt[3 * Q],cntdat,cntdlt;
int s[N];
void add_list(int x) {
    exi[x] = true;
    cnt ++;
    prv[x] = ed;
    nxt[ed] = (ed > 0) * x;
    beg = (beg == 0) ? x : beg;
    ed = x;
}
void del_list(int x){ 
    exi[x] = false;
    cnt --;
    if(ed == x)
        ed = prv[x];
    if(beg == x)
        beg = nxt[x];
    if(prv[x])
        nxt[prv[x]] = nxt[x];
    if(nxt[x])
        prv[nxt[x]] = prv[x];
    nxt[x] = prv[x] = 0;
} 
int gcd(int x,int y){
    return y == 0 ? x : gcd(y,x % y);
}
#define fadd(x) \
    if(!dft[prid[x]])\
        dlt[++cntdlt] = x;\
    dft[prid[x]] ++;
namespace IO{
    char ibuf[99967],*ip1 = ibuf,*ip2 = ibuf;
    char gc(){
        return (ip1 == ip2) && (ip2 = (ip1 = ibuf) + fread(ibuf,1,99967,stdin),ip1 == ip2) ? EOF : *ip1++;
    } 
    void fstin(int &x){
        x = 0;
        char c = gc();
        while(!isdigit(c))
            c = gc();
        while(isdigit(c))
            x = (x << 1) + (x << 3) + c - '0',c = gc(); 
    }
    char wbuf[99967],*wp1 = wbuf,*wp2 = wbuf + 99967;
    inline void pc(const char c){
        if(wp1 == wp2){
            fwrite(wbuf,1,99967,stdout);
            wp1 = wbuf;
        }
        *wp1 ++ = c;
    }
    void write(int x){
        if(x > 9)
            write(x / 10);
        pc((x % 10) ^ 48);
    }
};
using namespace IO;
int main(){
//    #ifndef LOCAL
    //    freopen("h.in","r",stdin);
    //    freopen("h.out","w",stdout);
    //#endif
    fstin(n),fstin(q);
//    cerr << n << ' ' << q << '\n';
    npr[0] = true,npr[1] = true;
    for(int i = 2; i <= n; i ++){
        if(!npr[i]){
            pr[++prcnt] = i;
            minpr[i] = i;
            prid[i] = prcnt;
            to[i] = 1;
        }
        for(int j = 1; j <= prcnt && i * pr[j] <= n; j ++){
            npr[i * pr[j]] = true;
            minpr[i * pr[j]] = pr[j];
            to[i * pr[j]] = i;
            if(minpr[i * pr[j]] == minpr[i]){
                to[i * pr[j]] = to[i];
                break; 
            }
        }
    }
//    cerr << prcnt;
//    return 0;
//    return 0;
    for(int i = 1; i <= q; i ++){
        fstin(a[i]);
    }
//    return 0;
    for(int i = 1; i <= q; i ++){
        //assert(prv[0] == 0);
        //assert(nxt[0] == 0);
        //cout << i << endl;
        if(exi[a[i]]){
            del_list(a[i]);
        }
        else{
            add_list(a[i]);
        }
        //if(cnt > 0){
    ///        for(int fi = beg; fi != 0; fi = nxt[fi])
    //            pc(' '),write(fi),pc('\n'),assert(!ntp[fi]),assert(exi[fi]),exi.reset(fi),ntp.set(fi);
    //        for(int fi = beg; fi != 0; fi = nxt[fi])
    //            exi.set(fi),ntp.reset(fi);
    //    }
        if(cnt == 0){
            pc('0'),pc('\n');
        }
        else if(cnt == 1){
            pc('1'),pc('\n');
        }
        else if(cnt == 2){
            pc(49 + (abs(beg - ed) != 1)),pc('\n');
        }
        else if(cnt == 3){
            pc(50 + (gcd(abs(beg - ed),abs(ed - prv[ed])) != 1)),pc('\n');
        }
        else{
            for(int fi = beg; fi != 0; ){
                int a1 = 0,a2 = 0,a3 = 0,a4 = 0,a5 = 0,a6 = 0;
                a1 = fi;
                fi = nxt[fi];
                if(fi){
                    a2 = fi,fi = nxt[fi];
                    int o = abs(a2 - a1);
                    while(o > 1){
                        fadd(minpr[o])
                        o = to[o];
                    }
                    if(fi){
                        a3 = fi,fi = nxt[fi];
                        o = abs(a3 - a1);
                        while(o > 1){
                            fadd(minpr[o])
                            o = to[o];
                        }
                //        cerr << "3-1\n";
                        o = abs(a2 - a3);
                        while(o > 1){
                            fadd(minpr[o])
                            o = to[o];
                        }
                        if(fi){
                            a4 = fi,fi = nxt[fi];
                            o = abs(a4 - a1);
                            while(o > 1){
                                fadd(minpr[o])
                                o = to[o];
                            }
                    //        cerr << "4-1";
                            o = abs(a4 - a2);
                            while(o > 1){
                                fadd(minpr[o])
                                o = to[o];
                            }
                    //        cerr << "4-2";
                            o = abs(a4 - a3);
                            while(o > 1){
                                fadd(minpr[o])
                                o = to[o];
                            }
                            if(fi){
                                a5 = fi, fi = nxt[fi];
                                o = abs(a5 - a1);
                                while(o > 1){
                                    fadd(minpr[o])
                                    o = to[o];
                                }
                        //        cerr << "5-1";
                                o = abs(a5 - a2);
                                while(o > 1){
                                    fadd(minpr[o])
                                    o = to[o];
                                }
                        //        cerr << "5-2";
                                o = abs(a5 - a3);
                                while(o > 1){
                                    fadd(minpr[o])
                                    o = to[o];
                                }
                    //            cerr << "5-3";
                                o = abs(a5 - a4);
                                while(o > 1){
                                    fadd(minpr[o])
                                    o = to[o];
                                }
                                if(fi){
                                    a6 = fi,fi = nxt[fi];
                                    o = abs(a6 - a1);
                                    while(o > 1){
                                        fadd(minpr[o])
                                        o = to[o];
                                    }
                    //                cerr << "6-1";
                                    o = abs(a6 - a2);
                                    while(o > 1){
                                        fadd(minpr[o])
                                        o = to[o];
                                    }
                    //                cerr << "6-2";
                                    o = abs(a6 - a3);
                                    while(o > 1){
                                        fadd(minpr[o])
                                        o = to[o];
                                    }
                        //            cerr << "6-3";
                                    o = abs(a6 - a4);
                                    while(o > 1){
                                        fadd(minpr[o])
                                        o = to[o];
                                    }
                        //            cerr << "6-4";
                                    o = abs(a6 - a5);
                                    while(o > 1){
                                        fadd(minpr[o])
                                        o = to[o];
                                    }
                                }
                            }
                        }
                    }
                }
            }
            for(int fi = 1; fi <= cntdlt; fi ++){
                if(dft[prid[dlt[fi]]] >= cnt * 3 / 16){
                    dst[prid[dlt[fi]]] = true;
                    dat[++cntdat] = dlt[fi];
                }
                dft[prid[dlt[fi]]] = 0;
            }
            cntdlt = 0;
            int step = min(q - i,cnt / 4);
            for(int fi = 1; fi <= cntdat; fi ++){
                int p = dat[fi];
                fcnt[0] = 0x3f3f3f3f;
                for(int j = beg; j != 0; j = nxt[j]){
                //    write(j),pc(' '),write(j % p),pc(' '),write(s[j % p]),pc(' '),write(fmx),pc('\n');
                    fcnt[s[j % p]] --;
                    s[j % p] ++;
                    fcnt[s[j % p]] ++;
                    if(fcnt[fmx + 1] > 0)
                        fmx ++;
                }
            //    write(p),pc(' '),write(fmx),pc('\n');
                ans[i] = max(ans[i],fmx);
                for(int j = i + 1; j <= i + step; j ++){
                    if(exi[a[j]]){
                        exi[a[j]] = false;
                        fcnt[s[a[j] % p]] --;
                        s[a[j] % p] -- ;
                        fcnt[s[a[j] % p]] ++;
                        if(fcnt[fmx] == 0)
                            fmx --;
                    }
                    else{
                        exi[a[j]] = true;
                        fcnt[s[a[j] % p]] --;
                        s[a[j] % p] ++;
                        fcnt[s[a[j] % p]] ++;
                        if(fcnt[fmx + 1] > 0)
                            fmx ++;
                    }
                    ans[j] = max(ans[j],fmx);
                }
                for(int j = i + step; j > i; j --){
                    if(exi[a[j]]){
                        exi[a[j]] = false;
                        fcnt[s[a[j] % p]] --;
                        s[a[j] % p] -- ;
                        fcnt[s[a[j] % p]] ++;
                        if(fcnt[fmx] == 0)
                            fmx --;
                    }
                    else{
                        exi[a[j]] = true;
                        fcnt[s[a[j] % p]] --;
                        s[a[j] % p] ++;
                        fcnt[s[a[j] % p]] ++;
                        if(fcnt[fmx + 1] > 0)
                            fmx ++;
                    }
                }
                for(int j = beg; j != 0; j = nxt[j]){
                    fcnt[s[j % p]] --;
                    s[j % p] --;
                    fcnt[s[j % p]] ++;
                    if(fcnt[fmx] == 0)
                        fmx --;
                }
            //    write(fcnt[0] == 0x3f3f3f3f),pc('\n');
            }
            for(int fi = 1; fi <= cntdat; fi ++){
                dst[prid[dat[fi]]] = false;
            }
            fmx = 0;
            cntdat = 0;
            write(ans[i]);
            pc('\n');
            for(int fi = i + 1; fi <= i + step; fi ++){
                if(exi[a[fi]])
                    del_list(a[fi]);
                else
                    add_list(a[fi]);
                write(ans[fi]);
                pc('\n');
            }
            i = i + step;
            //cerr << "end\n";
        }
    }
    fwrite(wbuf,1,wp1 - wbuf,stdout);
    return 0;
}