Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

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);
}