URAL_1846
思考之后一个可行的方式就是对于每次插入、删除完毕之后快速的求出剩余数的gcd。
但是直接去求是不行的，不过思考一下之后会发现gcd和求和运算有一些相似的地方，比如gcd(a,b,c,d)=gcd(gcd(a,b)+gcd(c,d))就好比sum(a,b,c,d)=sum(sum(a,b),sum(c,d))，于是就想到可不可以用线段树去查询呢？当然可以，只要线段树上其余的值初始化成0，树顶的元素就是所有值的gcd。
想到这里就还剩一个问题了，每个数怎么和线段树上的位置对应起来，因为我们要完成插入、删除操作就必须快速找到对应元素的位置，我是用哈希表处理的，网上也有离散化去处理的。
#include<stdio.h>
#include<string.h>
#define HASH 1000003
#define MAXD 100010
int N, M, head[HASH], tree[4 * MAXD], next[MAXD], a[MAXD];
char op[5];
int hash(int x)
{
return (((x << 1) ^ (x >> 1)) & 0x7fffffff) % HASH;
}
int gcd(int x, int y)
{
return y == 0 ? x : gcd(y, x % y);
}
void init()
{
memset(tree, 0, sizeof(tree));
memset(head, -1, sizeof(head));
for(M = 1; M < N + 2; M <<= 1);
}
void update(int i)
{
int x, y;
for(; i ^ 1; i >>= 1)
{
if(tree[i] < tree[i ^ 1])
x = tree[i ^ 1], y = tree[i];
else
x = tree[i], y = tree[i ^ 1];
tree[i >> 1] = gcd(x, y);
}
}
void in(int s)
{
int i, j, h = hash(a[s]);
next[s] = head[h];
head[h] = s;
tree[M + s] = a[s];
update(M + s);
}
void out(int s)
{
int i, j, k, h = hash(a[s]);
i = head[h];
if(a[i] == a[s])
{
head[h] = next[i];
k = i;
}
else
{
for(; i != -1; i = next[i])
if(a[next[i]] == a[s])
break;
k = next[i];
next[i] = next[next[i]];
}
tree[M + k] = 0;
update(M + k);
}
void solve()
{
int i, j, k;
for(i = 0; i < N; i ++)
{
scanf("%s%d", op, &a[i]);
if(op[0] == '+')
in(i);
else
out(i);
printf("%d\n", tree[1] == 0 ? 1 : tree[1]);
}
}
int main()
{
while(scanf("%d", &N) == 1)
{
init();
solve();
}
return 0;
}