OJ.UZ: https://oj.uz/problem/view/IOI13_game


생각해볼 수 있는 방법은


1. 쿼드트리: 시간 초과
2. 2D Segment Tree 정적 생성: 메모리가 너무 많이 들음
3. 2D Segment Tree 동적 생성: 메모리가 그래도 많이 필요함


그러면 적당한 부분에서 메모리 사용량과 시간을 잡아야 함. 그래서 잘 보면 알겠지만, 많은 1D Segment Tree의 노드들이 원소가 하나밖에 없는데 log S 개의 노드를 안에 들고있다는 사실을 알 수 있음. 이 부분의 메모리 사용량을 줄이면 되니까, 들어간 만큼만 메모리를 사용하는 BST를 생각해 볼 수 있음.


4. 1D Segment Tree + BST: OK
5. 1D Segment Tree + 1D Segment Tree (+ 메모리를 위한 경로 압축): myungwoo 블로그 참고


나는 짜기 귀찮아서 Treap으로 짰는데, 그거때문에 시간이 느려가지고 통과를 못하길래 약간 최적화를 함.


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152#include <random> #include "game.h" // Global typedef long long int ll; static ll gcd2(ll u, ll v) { while (v > 0) { const ll tmp = u % v; u = v; v = tmp; } return u; } static std::mt19937 RAND(314159U); // Treap (1d) class Treap { public: unsigned int rr; int idx; ll val, gg; Treap *left, *right; Treap(int i1, ll i2) : idx(i1), val(i2), gg(i2) { left = right = nullptr; rr = RAND(); } }; inline ll treap_getgg(Treap *root) { return (root ? root->gg : 0LL); } inline void treap_update(Treap *root) { if (root) root->gg = gcd2(root->val, gcd2(treap_getgg(root->left), treap_getgg(root->right))); } Treap* treap_merge(Treap *left, Treap *right) { if (!left) return right; else if (!right) return left; else if (left->rr > right->rr) { left->right = treap_merge(left->right, right); treap_update(left); return left; } right->left = treap_merge(left, right->left); treap_update(right); return right; } void treap_split(Treap *root, int p, Treap *&left, Treap *&right) { if (!root) { left = right = nullptr; return; } else if (p > root->idx) { treap_split(root->right, p, root->right, right); left = root; } else { treap_split(root->left, p, left, root->left); right = root; } treap_update(root); } void treap_insert(Treap *&root, int p, ll k) { Treap *p1, *p2, *p3; if (!root) { root = new Treap(p, k); return; } treap_split(root, p, p1, p2); treap_split(p2, p + 1, p2, p3); if (p2) p2->val = p2->gg = k; else p2 = new Treap(p, k); root = treap_merge(p1, treap_merge(p2, p3)); } ll treap_query(Treap *&root, int ln, int rn) { Treap *p1, *p2, *p3; if (!root || ln > rn) return 0LL; else if (ln == rn) { for (p1 = root; p1; ) { if (p1->idx < ln) p1 = p1->right; else if (p1->idx > ln) p1 = p1->left; else return p1->val; } return 0LL; } treap_split(root, ln, p1, p2); treap_split(p2, rn + 1, p2, p3); const ll ans = treap_getgg(p2); root = treap_merge(p1, treap_merge(p2, p3)); return ans; } // Segment Tree (2d) class Segtree { public: int ldx, rdx, mdx; Segtree *left, *right; Treap *bst; Segtree(int l1, int r1) : ldx(l1), rdx(r1) { mdx = (l1 + r1) / 2; left = right = nullptr; bst = nullptr; } }; void segtree_insert(Segtree *root, int xx, int yy, ll p) { if (root->ldx == root->rdx) { return treap_insert(root->bst, yy, p); } else if (xx <= root->mdx) { if (!root->left) root->left = new Segtree(root->ldx, root->mdx); segtree_insert(root->left, xx, yy, p); } else { if (!root->right) root->right = new Segtree(root->mdx + 1, root->rdx); segtree_insert(root->right, xx, yy, p); } treap_insert(root->bst, yy, gcd2((root->left ? treap_query(root->left->bst, yy, yy) : 0LL), (root->right ? treap_query(root->right->bst, yy, yy) : 0LL))); } ll segtree_query(Segtree *root, int x1, int x2, int y1, int y2) { if (!root || x1 > root->rdx || x2 < root->ldx) return 0LL; else if (x1 <= root->ldx && root->rdx <= x2) return treap_query(root->bst, y1, y2); return gcd2(segtree_query(root->left, x1, x2, y1, y2), segtree_query(root->right, x1, x2, y1, y2)); } // Starts from here static Segtree *Idx; void init(int R, int C) { Idx = new Segtree(0, R - 1); } void update(int P, int Q, ll K) { return segtree_insert(Idx, P, Q, K); } ll calculate(int P, int Q, int U, int V) { return segtree_query(Idx, P, U, Q, V); }