T-Shirts
题目描述
The big consignment of t-shirts goes on sale in the shop before the beginning of the spring. In all $ n $ types of t-shirts go on sale. The t-shirt of the $ i $ -th type has two integer parameters — $ c_{i} $ and $ q_{i} $ , where $ c_{i} $ — is the price of the $ i $ -th type t-shirt, $ q_{i} $ — is the quality of the $ i $ -th type t-shirt. It should be assumed that the unlimited number of t-shirts of each type goes on sale in the shop, but in general the quality is not concerned with the price.
As predicted, $ k $ customers will come to the shop within the next month, the $ j $ -th customer will get ready to spend up to $ b_{j} $ on buying t-shirts.
All customers have the same strategy. First of all, the customer wants to buy the maximum possible number of the highest quality t-shirts, then to buy the maximum possible number of the highest quality t-shirts from residuary t-shirts and so on. At the same time among several same quality t-shirts the customer will buy one that is cheaper. The customers don't like the same t-shirts, so each customer will not buy more than one t-shirt of one type.
Determine the number of t-shirts which each customer will buy, if they use the described strategy. All customers act independently from each other, and the purchase of one does not affect the purchase of another.
输入格式
The first line contains the positive integer $ n $ ( $ 1<=n<=2·10^{5} $ ) — the number of t-shirt types.
Each of the following $ n $ lines contains two integers $ c_{i} $ and $ q_{i} $ ( $ 1<=c_{i},q_{i}<=10^{9} $ ) — the price and the quality of the $ i $ -th type t-shirt.
The next line contains the positive integer $ k $ ( $ 1<=k<=2·10^{5} $ ) — the number of the customers.
The next line contains $ k $ positive integers $ b_{1},b_{2},...,b_{k} $ ( $ 1<=b_{j}<=10^{9} $ ), where the $ j $ -th number is equal to the sum, which the $ j $ -th customer gets ready to spend on t-shirts.
输出格式
The first line of the input data should contain the sequence of $ k $ integers, where the $ i $ -th number should be equal to the number of t-shirts, which the $ i $ -th customer will buy.
样例 #1
样例输入 #1
3
7 5
3 5
4 3
2
13 14
样例输出 #1
2 3
样例 #2
样例输入 #2
2
100 500
50 499
4
50 200 150 100
样例输出 #2
1 2 2 1
提示
In the first example the first customer will buy the t-shirt of the second type, then the t-shirt of the first type. He will spend 10 and will not be able to buy the t-shirt of the third type because it costs 4, and the customer will owe only 3. The second customer will buy all three t-shirts (at first, the t-shirt of the second type, then the t-shirt of the first type, and then the t-shirt of the third type). He will spend all money on it.
首先很明显要用平衡树。一个貌似很对的做法是，用 FHQ-Treap 分成大于等于 \(v\) 和小于 \(v\) 的两棵树，然后在大于等于 \(v\) 的那棵子树打一个减 \(v\) 。同时维护买的衣服的件数 \(c\)，打一个件数 \(+1\) 的标记，在合并回去。
但是 FHQ-Treap 中的合并操作一定要满足一颗子树中的数全部小于另一颗子树中的数。我们可以尝试拆成三部分，分成 \(V_i<v\)，\(v\le V_i\le 2v,V_i>v\)，然后再把中间那棵树里的全部 \(-v\) ，暴力插入第一棵树中。第三棵树打个标记就可以了。
由于 \(V_i\) 每次被暴力插入时，满足 \(v\le V_i\le 2v\)，那么 \(V_i\) 减去 \(v\) 后至少折半。所以最多会有 \(O(nlogn)\) 次暴力插入操作，总复杂度 \(O(nlog^2n)\)
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
mt19937_64 gen(300000001);
int c[N],q[N],id[N],b[N],rt,idx,n,k,ans[N];
struct node{
int lc,rc,id,c,v,tagc,tagv,pr;
}tr[N];
int newnode(int x)
{
++idx;
tr[idx].id=x;
tr[idx].pr=gen();
tr[idx].v=b[x];
return idx;
}
void pushdown(int o)
{
if(tr[o].tagv)
{
tr[tr[o].lc].tagv+=tr[o].tagv;
tr[tr[o].rc].tagv+=tr[o].tagv;
tr[tr[o].lc].v+=tr[o].tagv;
tr[tr[o].rc].v+=tr[o].tagv;
}
if(tr[o].tagc)
{
tr[tr[o].lc].tagc+=tr[o].tagc;
tr[tr[o].rc].tagc+=tr[o].tagc;
tr[tr[o].lc].c+=tr[o].tagc;
tr[tr[o].rc].c+=tr[o].tagc;
}
tr[o].tagc=tr[o].tagv=0;
}
int merge(int x,int y)//x<=y
{
if(!x||!y)
return x|y;
pushdown(x);
pushdown(y);
if(tr[x].pr>tr[y].pr)
{
tr[x].rc=merge(tr[x].rc,y);
return x;
}
tr[y].lc=merge(x,tr[y].lc);
return y;
}
void split(int x,int y,int&p,int&q)//<=y,>y
{
if(!x)
return p=q=0,void();
pushdown(x);
if(tr[x].v<=y)
{
p=x;
split(tr[x].rc,y,tr[x].rc,q);
}
else
{
q=x;
split(tr[x].lc,y,p,tr[x].lc);
}
}
int cmp(int x,int y)
{
if(q[x]^q[y])
return q[x]>q[y];
return c[x]<c[y];
}
void dfs(int x)
{
if(!x)
return;
pushdown(x);
ans[tr[x].id]=tr[x].c;
dfs(tr[x].lc);
dfs(tr[x].rc);
}
void sou(int x,int c)
{
pushdown(x);
// printf("%d\n",x);
if(!x)
return;
sou(tr[x].lc,c);
sou(tr[x].rc,c);
tr[x].lc=tr[x].rc=0;
tr[x].v-=c,tr[x].c++;
int t1,t2;
split(rt,tr[x].v,t1,t2);
tr[x].pr=gen();
rt=merge(t1,merge(x,t2));
}
void put(int x)
{
pushdown(x);
if(!x)
return;
put(tr[x].lc);
// printf("%d %d\n",tr[x].v,tr[x].c);
put(tr[x].rc);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d",c+i,q+i),id[i]=i;
sort(id+1,id+n+1,cmp);
scanf("%d",&k);
for(int i=1,t1,t2,t;i<=k;i++)
{
scanf("%d",b+i);
t=newnode(i);
split(rt,b[i],t1,t2);
rt=merge(t1,merge(t,t2));
// printf("%d %d %d\n",t1,t,t2);
}
// printf("%d %d %d %d\n",tr[1].lc,tr[1].rc,tr[2].lc,tr[2].rc);
// put(rt);
for(int i=1,c,t1,t2;i<=n;i++)
{
c=::c[id[i]];
split(rt,c-1,rt,t1);
split(t1,2*c-1,t1,t2);
// printf("%d %d %d\n",rt,t1,t2);
sou(t1,c);
tr[t2].c++;
tr[t2].tagc++;
tr[t2].v-=c;
tr[t2].tagv-=c;
rt=merge(rt,t2);
// put(rt);
}
dfs(rt);
for(int i=1;i<=k;i++)
printf("%d ",ans[i]);
return 0;
}