JOI春合宿 2011-day4 apples
問題文 : リンゴの出荷
解法 :
濃さD のリンゴを, 区間[D, D + B + 1)に対応させて,
・ある区間に値x を足す
・ある区間の和を求める
ことが出来れば, 出荷依頼に高速に答えることができる. これは, Starry Sky 木を改造することで実現することが可能である.
ただし, セグメント木のノードをすべて作っていてはMLE が必至なので, 必要なノードだけを生成する動的なセグメント木の構築を行う.
これをすることで, O(logD) 時間で1 つのクエリに応答することが出来る. ただし, D はリンゴの濃さの最大値である.
コード :
#include <set> #include <cstdio> #include <vector> #include <algorithm> using namespace std; int M, B; multiset<int> apples; struct Node { int ct, ma; Node *par, *left, *right; Node(){ par = left = right = NULL; ct = ma = 0; } } *root; const int size = 1000000001; Node pool[8000000]; int ptr; Node *alloc() { return (&pool[ptr++]); } void add(int a, int b, int x, Node *pos = root, int l = 0, int r = size) { if (b <= l || r <= a) return; if (a <= l && r <= b){ pos->ct += x; while (pos->par != NULL){ pos = pos->par; int ct = 0; if (pos->left != NULL) ct = max(ct, pos->left->ct + pos->left->ma); if (pos->right != NULL) ct = max(ct, pos->right->ct + pos->right->ma); pos->ma = ct; } return; } if (pos->left == NULL){ pos->left = alloc(); pos->left->par = pos; } add(a, b, x, pos->left, l, (l + r) / 2); if (pos->right == NULL){ pos->right = alloc(); pos->right->par = pos; } add(a, b, x, pos->right, (l + r) / 2, r); } int getIndex(int val, Node *pos = root, int carry = 0, int l = 0, int r = size) { carry += pos->ct; if (pos->right != NULL && pos->right->ma + pos->right->ct + carry >= val) return (getIndex(val, pos->right, carry, (l + r) / 2, r)); else if (pos->left != NULL && pos->left->ma + pos->left->ct + carry >= val) return (getIndex(val, pos->left, carry, l, (l + r) / 2)); return (l); } int main() { scanf("%d %d", &M, &B); root = alloc(); for (int i = 0; i < M; i++){ char q[2]; int arg; scanf("%s", q); if (q[0] == 'E') break; if (q[0] == 'A'){ scanf("%d", &arg); add(arg, min(size, arg + B + 1), 1); apples.insert(arg); } else { scanf("%d", &arg); if (root->ct + root->ma < arg) printf("NO\n"); else { int pos = getIndex(arg); multiset<int>::iterator it; vector<int> v; for (int i = 0; i < arg; i++){ it = apples.upper_bound(pos); it--; v.push_back(*it); add(*it, min(size, *it + B + 1), -1); apples.erase(it); } for (int i = arg - 1; i >= 0; i--){ printf("%d%c", v[i], i == 0 ? '\n' : ' '); } } fflush(stdout); } } return (0); }