#include <bits/stdc++.h> using namespace std; const int K = 19; const int N = 1 << K; int tab[N]; struct tree; int memcount; vector<tree*> nodes[K+1]; tree* alloc(); struct tree { int a, b; int val; tree *left, *right; void add() { nodes[__builtin_ctz(b - a)].push_back(this); } static tree* create(int A, int B) { auto t = alloc(); t->a = A; t->b = B; if(B == A + 1) { t->val = tab[A]; t->left = t->right = nullptr; } else { t->left = create(A, (A + B) / 2); t->right = create((A + B) / 2, B); } t->add(); return t; } static tree *dup(const tree &p) { tree *t = alloc(); *t = p; t->add(); return t; } tree* insert(int p, int x) { tree *t = dup(*this); if(b == a + 1) t->val = x; else if(p < (a + b) / 2) t->left = left->insert(p, x); else t->right = right->insert(p, x); return t; } }; tree memory[N*(K+3) + 5]; tree *tr[N]; tree* alloc() { return memory + (memcount++); } int main() { int n, m; scanf("%d %d", &n, &m); for(int i = 1; i <= n; i++) scanf("%d", tab + i); int k = 1; while(k <= n) k *= 2; tr[1] = tree::create(0, k); for(int i = 2; i <= m; i++) { int p, x; scanf("%d %d", &p, &x); tr[i] = tr[i-1]->insert(p, x); } for(int i = 1; i <= K; i++) { vector<pair<pair<int, int>, tree*>> vec; for(auto n: nodes[i]) vec.push_back({{n->left->val, n->right->val}, n}); sort(vec.begin(), vec.end()); int nr = 0; for(int j = 0; j < vec.size(); j++) { if(j > 0 && vec[j].first != vec[j-1].first) nr++; vec[j].second->val = nr; } } vector<pair<int, int>> vec; for(int i = 1; i <= m; i++) vec.emplace_back(tr[i]->val, i); sort(vec.begin(), vec.end()); for(auto x: vec) printf("%d ", x.second); puts(""); }
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 | #include <bits/stdc++.h> using namespace std; const int K = 19; const int N = 1 << K; int tab[N]; struct tree; int memcount; vector<tree*> nodes[K+1]; tree* alloc(); struct tree { int a, b; int val; tree *left, *right; void add() { nodes[__builtin_ctz(b - a)].push_back(this); } static tree* create(int A, int B) { auto t = alloc(); t->a = A; t->b = B; if(B == A + 1) { t->val = tab[A]; t->left = t->right = nullptr; } else { t->left = create(A, (A + B) / 2); t->right = create((A + B) / 2, B); } t->add(); return t; } static tree *dup(const tree &p) { tree *t = alloc(); *t = p; t->add(); return t; } tree* insert(int p, int x) { tree *t = dup(*this); if(b == a + 1) t->val = x; else if(p < (a + b) / 2) t->left = left->insert(p, x); else t->right = right->insert(p, x); return t; } }; tree memory[N*(K+3) + 5]; tree *tr[N]; tree* alloc() { return memory + (memcount++); } int main() { int n, m; scanf("%d %d", &n, &m); for(int i = 1; i <= n; i++) scanf("%d", tab + i); int k = 1; while(k <= n) k *= 2; tr[1] = tree::create(0, k); for(int i = 2; i <= m; i++) { int p, x; scanf("%d %d", &p, &x); tr[i] = tr[i-1]->insert(p, x); } for(int i = 1; i <= K; i++) { vector<pair<pair<int, int>, tree*>> vec; for(auto n: nodes[i]) vec.push_back({{n->left->val, n->right->val}, n}); sort(vec.begin(), vec.end()); int nr = 0; for(int j = 0; j < vec.size(); j++) { if(j > 0 && vec[j].first != vec[j-1].first) nr++; vec[j].second->val = nr; } } vector<pair<int, int>> vec; for(int i = 1; i <= m; i++) vec.emplace_back(tr[i]->val, i); sort(vec.begin(), vec.end()); for(auto x: vec) printf("%d ", x.second); puts(""); } |