题意：供应商提供n块价格为c的冰淇淋，一个学生想买n块冰淇淋，手中的钱数总共有t元，为了不让买n块冰淇淋所花费的钱数不超过t元，先尽可能卖给这个学生便宜的冰淇淋。
如果这个学生不能买到所需要的冰淇淋则输出“UNHAPPY”，能则输出“HAPPY”。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 200000
using namespace std; long long x[maxn];
struct node1
{
char str[];
int n;
long long w;
}p[maxn];
struct node
{
int l,r;
long long num;
long long sum;
int flag;
}tree[maxn*]; void up(int i)
{
if(tree[i].l==tree[i].r) return ;
tree[i].sum=tree[i<<].sum+tree[i<<|].sum;
tree[i].num=tree[i<<].num+tree[i<<|].num;
}
void down(int i)
{
if(tree[i].l==tree[i].r) return ;
if(tree[i].flag!=-)
{
tree[i<<].sum=tree[i<<|].sum=;
tree[i<<].num=tree[i<<|].num=;
tree[i<<].flag=tree[i<<|].flag=;
tree[i].flag=-;
}
} void build(int i,int l,int r)
{
tree[i].l=l; tree[i].r=r;
tree[i].num=tree[i].sum=;
tree[i].flag=-;
if(l==r) return ;
int mid=(l+r)>>;
build(i<<,l,mid);
build(i<<|,mid+,r);
} void deal(int i,int n,int c)
{
tree[i].sum+=(long long)c*n;
tree[i].num+=n;
if(x[tree[i].l]==c&&x[tree[i].r]==c) return ;
down(i);
if(c<=x[tree[i<<].r]) deal(i<<,n,c);
else deal(i<<|,n,c);
} long long search1(int i,int n)
{
if(tree[i].l==tree[i].r)
{
return (long long)n*x[tree[i].l];
}
down(i);
if(tree[i<<].num>=n) return search1(i<<,n);
else
return tree[i<<].sum+search1(i<<|,n-tree[i<<].num);
} void change(int i,int n)
{
if(tree[i].l==tree[i].r)
{
tree[i].num-=n;
tree[i].sum=tree[i].num*x[tree[i].l];
return ;
}
down(i);
if(tree[i<<].num>=n)
{
change(i<<,n);
}
else
{
change(i<<|,n-tree[i<<].num);
tree[i<<].num=;
tree[i<<].sum=;
tree[i<<].flag=;
}
up(i);
}
int main()
{
int cnt=,t1=;
while(scanf("%s %d%I64d",p[cnt].str,&p[cnt].n,&p[cnt].w)==)
{
if(p[cnt].str[]=='A')
{
x[t1++]=p[cnt].w;
}
cnt++;
}
sort(x,x+t1);
t1=unique(x,x+t1)-x;
build(,,t1-);
for(int i=; i<cnt; i++)
{
if(p[i].str[]=='A')
{
deal(,p[i].n,p[i].w);
}
else
{
if(tree[].num<p[i].n) printf("UNHAPPY\n");
else
{
if(search1(,p[i].n)>p[i].w) printf("UNHAPPY\n");
else
{
printf("HAPPY\n");
change(,p[i].n);
}
}
}
}
return ;
}