Untitled
plain_text
a month ago
3.5 kB
1
Indexable
Never
constexpr int MAX_NODE = 18000; constexpr int HASH_SIZE = 30000; struct Node { Node* parent; Node* child[3]; int num; bool valid; } NodePool[MAX_NODE]; int PoolCnt, GroupCnt; struct HashNode { int key; Node* data; } HashTbl[HASH_SIZE]; Node* hashFind(int key) { unsigned long h = key % HASH_SIZE; int cnt = HASH_SIZE; while (HashTbl[h].key != 0 && cnt--) { if (HashTbl[h].key == key) { return HashTbl[h].data; } h = (h + 1) % HASH_SIZE; } return nullptr; } void hashAdd(int key, Node* data) { unsigned long h = key % HASH_SIZE; while (HashTbl[h].key != 0) { if (HashTbl[h].key == key) { HashTbl[h].data = data; return; } h = (h + 1) % HASH_SIZE; } HashTbl[h].key = key; HashTbl[h].data = data; } void delNode(Node* node) { if (node == nullptr) return; node->valid = false; for (int i = 0; i < 3; ++i) delNode(node->child[i]); } void init(int N, int mId[], int mNum[]) { PoolCnt = 0; for (int i = 0; i < HASH_SIZE; ++i) { HashTbl[i].key = 0; } GroupCnt = N; for (int i = 0; i < N; ++i) { Node* node = &NodePool[PoolCnt++]; hashAdd(mId[i], node); node->valid = true; node->parent = nullptr; node->child[0] = node->child[1] = node->child[2] = nullptr; node->num = mNum[i]; } } int add(int mId, int mNum, int mParent) { Node* node = &NodePool[PoolCnt++]; Node* parent = hashFind(mParent); if (parent->child[0] == nullptr) { parent->child[0] = node; } else if (parent->child[1] == nullptr) { parent->child[1] = node; } else if (parent->child[2] == nullptr) { parent->child[2] = node; } else { return -1; } Node* curr = parent; while (curr) { curr->num += mNum; curr = curr->parent; } hashAdd(mId, node); node->valid = true; node->parent = parent; node->child[0] = node->child[1] = node->child[2] = nullptr; node->num = mNum; return parent->num; } int remove(int mId) { Node* node = hashFind(mId); if (!node || !node->valid) { return -1; } Node* parent = node->parent; if (parent->child[0] == node) { parent->child[0] = nullptr; } else if (parent->child[1] == node) { parent->child[1] = nullptr; } else if (parent->child[2] == node) { parent->child[2] = nullptr; } Node* curr = parent; while (curr) { curr->num -= node->num; curr = curr->parent; } delNode(node); return node->num; } int distribute(int K) { int low = 1, high = 0; for (int i = 0; i < GroupCnt; ++i) { if (NodePool[i].num > high) high = NodePool[i].num; } while (low <= high) { int mid = (low + high) / 2; int sum = 0; for (int i = 0; i < GroupCnt; ++i) { if (NodePool[i].num <= mid) sum += NodePool[i].num; else sum += mid; } if (sum <= K) { low = mid + 1; } else { high = mid - 1; } } return high; }