Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <math.h>
- #include <string.h>
- #include <stdlib.h>
- #include <assert.h>
- #include <algorithm>
- #include <vector>
- #include <stack>
- #include <queue>
- #include <list>
- #include <set>
- #include <map>
- #include <string>
- #include <iostream>
- using namespace std;
- int gcd(int a, int b) {
- return b ? gcd(b, a % b) : a;
- }
- struct TN {
- int k, p, d;
- TN *l, *r;
- TN(int K) : k(K), p(rand()), d(K), l(0), r(0) {}
- };
- class Treap {
- TN *t;
- int getD(TN *n) {
- return n ? n->d : 0;
- }
- void update(TN *n) {
- if (n)
- n->d = gcd(n->k, gcd(getD(n->l), getD(n->r)));
- }
- TN *merge(TN *a, TN *b) {
- if (!a || !b)
- return a ? a : b;
- if (a->p > b->p) {
- a->r = merge(a->r, b);
- update(a);
- return a;
- } else {
- b->l = merge(a, b->l);
- update(b);
- return b;
- }
- }
- void split(TN *t, int k, TN *&a, TN *&b) {
- if (!t) {
- a = b = 0;
- return;
- }
- if (t->k > k) {
- split(t->l, k, a, t->l);
- b = t;
- } else {
- split(t->r, k, t->r, b);
- a = t;
- }
- update(a);
- update(b);
- }
- public:
- Treap() : t(0) {}
- void add(int n) {
- TN *a, *b;
- split(t, n, a, b);
- t = merge(merge(a, new TN(n)), b);
- }
- void del(int n) {
- TN *a, *b, *c;
- split(t, n - 1, a, b);
- split(b, n, b, c);
- b = merge(b->l, b->r);
- t = merge(merge(a, b), c);
- }
- int getGcd() {
- return t ? t->d : 1;
- }
- } t;
- int n, x;
- char c;
- int main() {
- scanf("%d", &n);
- for (int i = 0; i < n; i++) {
- scanf(" %c%d", &c, &x);
- if (c == '+')
- t.add(x);
- else
- t.del(x);
- printf("%d\n", t.getGcd());
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement