1846. GCD 2010

#include<bits/stdc++.h>
#define ll int
using namespace std;
#define MAX 100005

ll tree[400005];

void update(ll node,ll b,ll e,ll i, ll val)
{
    if(i<b || i>e)
    {
        return;
    }
    if(b==e)
    {
        tree[node]=val;
        return;
    }

    ll left=0,right=0,mid=0;
    left=2*node;
    right=2*node+1;
    mid=(b+e)/2;

    update(left,b,mid,i,val);
    update(right,mid+1,e,i,val);

    tree[node]=__gcd(tree[left],tree[right]);
    return;
}

int main()
{
    ll n,m,i,j,a;
    char ch;
    map<ll,ll>mp,mp1;
    while(scanf("%d",&n)!=EOF)
    {
        memset(tree,0,sizeof tree);
        mp.clear();
        mp1.clear();
        j=1;
        for(i=1;i<=MAX;i++)
            update(1,1,MAX,i,0);

        for(i=1; i<=n; i++)
        {
//            for(ll k=1;k<=15;k++)
//                cout<<tree[j]<<ends;
//            cout<<endl;
            getchar();
            scanf("%c %d",&ch,&m);

            if(ch=='+')
            {
                if(mp.count(m)>0)
                {
                    mp[m]++;
                }
                else
                {
                    update(1,1,MAX,j,m);
                    mp[m]++;
                    mp1[m]=j;
                    j++;
                }
                printf("%d\n",max(1,tree[1]));
            }
            if(ch=='-')
            {
                if(mp[m]>1)
                {
                    mp[m]--;
                }
                else if(mp[m]==1)
                {
                    mp[m]--;
                    a=mp1[m];
                    update(1,1,MAX,a,0);
                }
                printf("%d\n",max(1,tree[1]));
            }
        }
    }
    return 0;
}