I used sqrt-decomposition and got AC in 358ms

My idea was like this:
1. Keep an array of the elements we have so far
2. For each sqrt-size block of the array compute the GCD
3. To insert an element: append it to the array and update its block
4. To remove an element: swap the element to be deleted with last element (I used a set of pairs<value, index> to get them quickly) and update their blocks

Insert (sqrt n)
Delete (sqrt n)
O(q sqrt n) where n is number of elements in the array

Do you mean that after every insertion, we have to update the block containing the element as well as the block size?
If block size is also updated, then shouldn't we have to update the whole array we've had so far?
I used sqrt too but in a slightly different way from yours. I read all the queries and store all the values of query + to an array, decide the block size and compute GCD for each block. Then I loop the array again to answer the queries. If it is query +, I simply increase the counter x and call GCD(a[1..x]) (because I completely computed GCD of all blocks before). If it is query -, I erase x in the present array. Specifically, I recompute the GCD of the block without erased value x.
This way caused me TLE on test #17, though :((