SGU - 311 Ice-cream Tycoon(線段樹)

SGU - 311 Ice-cream Tycoon(線段樹)

Description

You've recently started an ice-cream business in a local school. During a day you have many suppliers delivering the ice-cream for you, and many students buying it from you. You are not allowed to set the prices, as you are told the price for each piece of ice-cream by the suppliers.

The day is described with a sequence of queries. Each query can be either

ARRIVE nc

, meaning that a supplier has delivered n pieces of ice-cream priced c each to you, or

BUY nt

, meaning that a student wants to buy n pieces of ice-cream, having a total of t money. The latter is processed as follows: in case n cheapest pieces of ice-cream you have cost no more than t (together), you sell those n cheapest pieces to the student; in case they cost more, she gets nothing. You start the day with no ice-cream.

For each student, output

HAPPY

if she gets her ice-cream, and

UNHAPPY

if she doesn't.

Input

The input file contains between 1 and 10 ⁵ queries (inclusive), each on a separate line. The queries are formatted as described above, either

ARRIVE nc

or

BUY nt

, 1 ≤ n, c ≤ 10 ⁶, 1 ≤ t ≤ 10 ¹².

Output

For each

BUY

-query output one line, containing either the word

HAPPY

or the word

UNHAPPY

(answers should be in the same order as the corresponding queries).

Sample Input

sample input

sample output

ARRIVE 1 1
ARRIVE 10 200
BUY 5 900
BUY 5 900
BUY 5 1000

HAPPY
UNHAPPY
HAPPY

題意：一個商店，有兩種操作：（1）ARRIVE n c表示進貨n個，每個c元。（2）BUY n t表示一個買貨的人要買n個，一共拿了t元錢。如果現在店裡的貨的數量大於等於n且最便宜的n個的價格小於等於t則將最便宜的賣給他。否則不賣。

思路：離線的線段樹，我們以價格作為結點，然後離散化，好久沒做，看了final爺kuangbing的題解，注意的是優先處理最小的n個

#include 
#include 
#include 
#include 
#include 
#define lson(x) (x<<1)
#define rson(x) ((x<<1)|1)
typedef long long ll;
using namespace std;
const int maxn = 100010;

struct Node {
	int l, r;
	ll num;
	ll sum;
	int flag;
} segTree[maxn<<2];
int x[maxn];

void pushdown(int x) {
	if (segTree[x].l == segTree[x].r) 
		return;
	if (segTree[x].flag != -1) {
		segTree[lson(x)].sum = segTree[rson(x)].sum = 0;
		segTree[lson(x)].num = segTree[rson(x)].num = 0;
		segTree[lson(x)].flag = segTree[rson(x)].flag = 0;
		segTree[x].flag = -1;
	}
}

void pushup(int x) {
	if (segTree[x].l == segTree[x].r) 
		return;
	segTree[x].sum = segTree[lson(x)].sum + segTree[rson(x)].sum;
	segTree[x].num = segTree[lson(x)].num + segTree[rson(x)].num;
}

void build(int x, int l, int r) {
	segTree[x].r = r;
	segTree[x].l = l;
	segTree[x].sum = segTree[x].num = 0;
	segTree[x].flag = -1;
	if (l == r) return;
	int mid = l + r >> 1;
	build(lson(x), l, mid);
	build(rson(x), mid+1, r);
}

void Add(int i, int c, int n) {
	segTree[i].sum += (ll) c * n;
	segTree[i].num += n;
	if (x[segTree[i].l] == c && x[segTree[i].r] == c)
		return;
	pushdown(i);

	if (c <= x[segTree[lson(i)].r]) 
		Add(lson(i), c, n);
	else Add(rson(i), c, n);
}

ll query(int i, int n) {
	if (segTree[i].l == segTree[i].r) {
		return (ll) n * x[segTree[i].l];
	}
	pushdown(i);
	if (segTree[lson(i)].num >= n) 
		return query(lson(i), n);
	else return segTree[lson(i)].sum + query(rson(i), n-segTree[lson(i)].num);
}

void clear(int i, int n) {
	if (segTree[i].l == segTree[i].r) {
		segTree[i].num -= n;
		segTree[i].sum = segTree[i].num * x[segTree[i].l];
		return;
	}

	pushdown(i);
	if (segTree[lson(i)].num >= n)
		clear(lson(i), n);
	else {
		clear(rson(i), n-segTree[lson(i)].num);
		segTree[lson(i)].num = segTree[lson(i)].sum = 0;
		segTree[lson(i)].flag = 0;
	}
	pushup(i);
}

struct Query {
	char op[10];
	int n;
	ll c;
} q[maxn];

int main() {
	int n = 0;
	int tot = 0;
	while (scanf("%s%d%lld", q[n].op, &q[n].n, &q[n].c) != EOF) {
		if (q[n].op[0] == 'A')
			x[tot++] = q[n].c;
		n++;
	}
	sort(x, x+tot);
	tot = unique(x, x+tot) - x;
	build(1, 0, tot-1);

	for (int i = 0; i < n; i++) {
		if (q[i].op[0] == 'A')
			Add(1, q[i].c, q[i].n);
		else {
			if (segTree[1].num < q[i].n) 
				printf("UNHAPPY\n");
			else {
				if (query(1, q[i].n) > q[i].c)
					printf("UNHAPPY\n");
				else {
					printf("HAPPY\n");
					clear(1, q[i].n);
				}
			}
		}
	}
	return 0;
}