可以发现，所选物品的优先级是固定的，因此考虑先对物品排序。
发现难以优化对单个人的处理，由于询问不相互影响，因此考虑离线处理所有询问。
每加入一件物品，所有剩余钱数 \(\geq c_i\) 的人都会购买。
因此我们的操作是：对权值在 \(\left[c_i,+\infty\right)\) 的节点权值减 \(c_i\),答案加 \(1\)。
考虑使用平衡树维护。注意到平衡树的结构可能被破坏，考虑对于所有在 \([c_i,2c_i-1]\) 之间的节点暴力插入原树，以维护 BST 的结构。
分析复杂度：每个节点暴力插入一次，权值至少减半，故复杂度 \(\mathcal O(n\log V\log n)\)
#include <cstdio>
#include <cctype>
#include <random>
#include <algorithm>
using namespace std;
char buf[1<<14],*p1=buf,*p2=buf;
#define GetC() ((p1==p2)&&(p2=(p1=buf)+fread(buf,1,1<<14,stdin),p1==p2)?EOF:*p1++)
struct Ios{}io;
template <typename _tp>
Ios &operator >>(Ios &in,_tp &x){
x=0;int w=0;char c=GetC();
for(;!isdigit(c);w|=c=='-',c=GetC());
for(;isdigit(c);x=x*10+(c^'0'),c=GetC());
if(w) x=-x;
return in;
}
const int N=2e5+5;
mt19937 rnd(19260817);
struct qwq{int c,q;}a[N];
bool operator <(qwq x,qwq y){
if(x.q!=y.q) return x.q>y.q;
return x.c<y.c;
}
int sz[N],ch[N][2],key[N];
int val[N],id[N],ans[N],tag1[N],tag2[N];
int rt;
int cnt;
int new_node(int v,int id_){
int p=++cnt;
key[p]=rnd();
val[p]=v;
id[p]=id_;
ans[p]=0;
return p;
}
void maintain(int x){
sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;
}
void push_down(int x){
int &l=ch[x][0],&r=ch[x][1];
if(tag1[x]){
val[l]-=tag1[x];
val[r]-=tag1[x];
tag1[l]+=tag1[x];
tag1[r]+=tag1[x];
}
if(tag2[x]){
ans[l]+=tag2[x];
ans[r]+=tag2[x];
tag2[l]+=tag2[x];
tag2[r]+=tag2[x];
}
tag1[x]=tag2[x]=0;
}
int merge(int x,int y){
if(!x||!y) return x^y;
if(key[x]>key[y]){
push_down(x);
ch[x][1]=merge(ch[x][1],y);
maintain(x);
return x;
}
else{
push_down(y);
ch[y][0]=merge(x,ch[y][0]);
maintain(y);
return y;
}
}
void split(int p,int v,int &x,int &y){
if(!p){x=y=0;return ;}
push_down(p);
if(val[p]<=v)
x=p,split(ch[p][1],v,ch[x][1],y);
else
y=p,split(ch[p][0],v,x,ch[y][0]);
maintain(p);
}
void split_rk(int p,int k,int &x,int &y){
if(!p){x=y=0;return ;}
push_down(p);
if(sz[ch[p][0]]+1<=k) x=p,split_rk(ch[p][1],k-sz[ch[p][0]]-1,ch[x][1],y);
else y=p,split_rk(ch[p][0],k,x,ch[y][0]);
maintain(p);
}
void ins(int v,int id_){
int x,y;split(rt,v,x,y);
rt=merge(merge(x,new_node(v,id_)),y);
}
int res[N];
void dfs(int p){
if(!p) return ;
push_down(p);
dfs(ch[p][0]);
dfs(ch[p][1]);
maintain(p);
res[id[p]]=ans[p];
}
int main(){
int n,m;io>>n;
for(int i=1;i<=n;++i) io>>a[i].c>>a[i].q;
sort(a+1,a+n+1);
io>>m;
for(int i=1;i<=m;++i){
int x;io>>x;ins(x,i);
}
for(int i=1;i<=n;++i){
int x,y,z;split(rt,a[i].c-1,x,y);
if(y) tag1[y]+=a[i].c,++tag2[y],val[y]-=a[i].c,++ans[y];
split(y,a[i].c-1,y,z);
while(y){
int tmp;split_rk(y,1,tmp,y);
int p,q;
split(x,val[tmp],p,q);
x=merge(merge(p,tmp),q);
}
rt=merge(x,z);
}
dfs(rt);
for(int i=1;i<=m;++i) printf("%d ",res[i]);
return 0;
}