题目传送门
分析：
对于每个人直接算物品数无法优化，考虑每个物品对人的贡献
优先价值最高的物品，那么先把物品按价值从高到低排序，每件物品会让剩余钱数\(\geq c\)的人钱数减少\(c\)，答案\(+1\)
考虑用数据结构维护这个过程，用平衡树解决，权值为钱数
每次把平衡树split成大于和不大于\(c\)的两份，大于\(c\)的减去\(c\)，答案标记加一，再合并回去
发现这样直接合并就不满足平衡树的定义了
出问题的区间为\([1,c]\)和\([c+1,2c]\)，我们看能不能暴力合并这两个区间，把后者的元素重新暴力insert进去
发现这样复杂度没有问题，对于每个单独的值\(v\)，它在某一个\(c\)的询问上被合并了，说明\(c>\frac{v}{2}\)，那么\(v\)每次会减去一个大于\(\frac{v}{2}\)的数
那么一个\(v\)就最多会被减\(logv\)次，直接暴力合并即可
总复杂度\(O(nlog^2n)\)
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<vector>
#define maxn 600005
#define INF 0x3f3f3f3f
using namespace std;
inline int getint()
{
int num=0,flag=1;char c;
while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;
while(c>='0'&&c<='9')num=num*10+c-48,c=getchar();
return num*flag;
}
int n,m;
int ch[maxn][2];
int num[maxn],ans[maxn],lznum[maxn],lzans[maxn],rd[maxn];
int rt;
struct node{
int c,q;
}a[maxn];
inline bool cmp(node x,node y)
{return x.q==y.q?x.c<y.c:x.q>y.q;}
inline void pushdown(int x)
{
if(lznum[x])
{
lznum[ch[x][0]]+=lznum[x],lznum[ch[x][1]]+=lznum[x];
num[ch[x][0]]+=lznum[x],num[ch[x][1]]+=lznum[x];
lznum[x]=0;
}
if(lzans[x])
{
lzans[ch[x][0]]+=lzans[x],lzans[ch[x][1]]+=lzans[x];
ans[ch[x][0]]+=lzans[x],ans[ch[x][1]]+=lzans[x];
lzans[x]=0;
}
}
inline void split(int rt,int k,int &x,int &y)
{
if(!rt){x=y=0;return;}
pushdown(rt);
if(num[rt]<k)x=rt,split(ch[rt][1],k,ch[rt][1],y);
else y=rt,split(ch[rt][0],k,x,ch[rt][0]);
}
inline int merge(int x,int y)
{
if(!x||!y)return x|y;
if(rd[x]<rd[y]){pushdown(x),ch[x][1]=merge(ch[x][1],y);return x;}
else{pushdown(y),ch[y][0]=merge(x,ch[y][0]);return y;}
}
inline int insert(int rt,int k)
{
int x=0,y=0;
split(rt,num[k],x,y);
return merge(x,merge(k,y));
}
inline int dfs(int x,int y)
{
if(!x)return y;
pushdown(x);
y=dfs(ch[x][0],y);
y=dfs(ch[x][1],y);
ch[x][0]=ch[x][1]=0;
return insert(y,x);
}
inline void getans(int x)
{
if(!x)return;pushdown(x);
getans(ch[x][0]),getans(ch[x][1]);
}
int main()
{
srand(114514);
n=getint();
for(int i=1;i<=n;i++)a[i].c=getint(),a[i].q=getint();
sort(a+1,a+n+1,cmp);
m=getint();
for(int i=1;i<=m;i++)num[i]=getint(),rd[i]=rand(),rt=insert(rt,i);
for(int i=1;i<=n;i++)
{
int x,y,z,w;
split(rt,a[i].c,x,y);
num[y]-=a[i].c,lznum[y]-=a[i].c;
ans[y]++,lzans[y]++;
split(y,a[i].c-1,z,w);
x=dfs(z,x);
rt=merge(x,w);
}
getans(rt);
for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
}
