timus1846.cpp

#include <cstdio>
#include <cctype>
#include <algorithm>
#define fs first
#define sc second
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)

using namespace std;

#define MAXN 100010

struct node
{
    int fs, sc, td;
};

bool cmp(const node &a, const node &b)
{
    return a.fs < b.fs;
}

int t[MAXN << 2], howmany[MAXN], k = 0, q, size = 0, tt;
node in1[MAXN], in2[MAXN];

int gcd(int a, int b)
{
    while (b != 0)
    {
        tt = b;
        b = a % b;
        a = tt;
    }
    return a;
}

void remove(int pos, int tl = 1, int tr = 100000, int v = 1)
{
    if (tl == tr && tl == pos)
    {
        t[v] = 0;
    }
    else
    {
        int tm = (tl + tr) >> 1;
        if (pos <= tm) remove(pos, tl, tm, v<<1);
        else remove(pos, tm+1, tr, v<<1|1);

        t[v] = gcd(t[v<<1], t[v<<1|1]);
    }
}

void insert(int val, int pos, int tl = 1, int tr = 100000, int v = 1)
{
    if (tl == tr && tl == pos)
    {
        t[v] = val;
    }
    else
    {
        int tm = (tl + tr) >> 1;
        if (pos <= tm) insert(val, pos, tl, tm, v<<1);
        else insert(val, pos, tm+1, tr, v<<1|1);

        t[v] = gcd(t[v<<1], t[v<<1|1]);
    }
}

int last = -1;

int main()
{
    scanf("%d", &q);
    char sign[2];
    int x, pos;
    rep(i, q)
    {
        scanf("%s", sign);
        scanf("%d", &x);
        in1[i].fs = in2[i].fs = x;
        in1[i].sc = in2[i].sc = sign[0];
        in1[i].td = i;
    }
    sort(in1, in1+q, cmp);

    rep(i, q)
    {
        if (last != in1[i].fs) k++;
        last = in1[i].fs;
        in2[in1[i].td].td = k;
    }

    rep(i, q)
    {
        pos = in2[i].td;
        if (in2[i].sc == '-')
        {
            if (howmany[pos] == 1) remove(pos);
            howmany[pos] --;
            size --;
        }
        else
        {
            howmany[pos] ++;
            insert(in2[i].fs, pos);
            size ++;
        }
        printf("%d\n", size ? t[1] : 1);
    }
    return 0;
}