本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-26 22:09:09

Link

考虑衣服来减人的钱而非人买衣服。这样只需要衣服顺序加入即可完成对 $q$ 的限制。

问题转化为有一个集合，每次把集合分为两部分，一部分小于 $c$ ，另一部分大于等于 $c$ ，使第二部分元素的计数器增加，值减少 $c$ ，再合并两个集合。看起来很像平衡树，但中间会有重叠。

考虑重叠部分，发现其都至少减少了一半。因此对于重叠的部分直接暴力插入，每一个元素最多会被暴力插入 $\mathrm{O(\log w)}$ 次，不重叠部分直接合并即可。

实现上使用了 splay ，每次将树分为三部分，小于 $c$ ，介于 $c+1$ 与 $2c$ 之间与大于 $2c$ 。中间部分暴力修改后暴力插入到第一个集合内，后面部分直接打标记，与第一部分合并。由于这两部分没有交，所以合并是均摊 $\mathrm{O(\log n)}$ 。

中间因为在 find 时没有把找的那个点的 tag 给 pushdown 调了好久。

code

const int N=2e5+5;

struct shirts{
	int c,p;
	bool operator<(shirts ano)const{
		return p==ano.p?c<ano.c:p>ano.p;
	}
}a[N];

int ans[N];

struct Splay{
	struct node{
		int fa,s[2];
		int val;
		int cnt,id;
		int tag1,tag2;
	}t[N<<5];
	int rt,idx;
	Splay(){
		rt=idx=0;
	}
	void pushdown(int x){
		if(t[x].tag1==0&&t[x].tag2==0)
			return;
		if(t[x].s[0]){
			t[t[x].s[0]].tag1+=t[x].tag1;
			t[t[x].s[0]].tag2+=t[x].tag2;
			t[t[x].s[0]].val+=t[x].tag1;
			t[t[x].s[0]].cnt+=t[x].tag2;
		}
		if(t[x].s[1]){
			t[t[x].s[1]].tag1+=t[x].tag1;
			t[t[x].s[1]].tag2+=t[x].tag2;
			t[t[x].s[1]].val+=t[x].tag1;
			t[t[x].s[1]].cnt+=t[x].tag2;
		}
		t[x].tag1=t[x].tag2=0;
	}
	void rotate(int x){
		int y=t[x].fa,z=t[y].fa;
		pushdown(z),pushdown(y);pushdown(x);
		bool w=x==t[y].s[1];
		if(z)
			t[z].s[y==t[z].s[1]]=x;
		t[x].fa=z;
		t[y].s[w]=t[x].s[w^1];
		t[t[x].s[w^1]].fa=y;
		t[x].s[w^1]=y;
		t[y].fa=x;
	}
	void splay(int x,int k){
		if(x==0||x==k)
			return;
		while(t[x].fa!=k){
			int y=t[x].fa;
			if(t[y].fa!=k){
				int z=t[y].fa;
				if((x==t[y].s[1])^(y==t[z].s[1]))
					rotate(x);
				else
					rotate(y);
			}rotate(x);
		}
		if(k==0)
			rt=x;
	}
	int fd(int x,int num){
		while(t[x].s[num>t[x].val])
			pushdown(x),x=t[x].s[num>t[x].val];
		pushdown(x);
		return x;
	}
	void insert(int num,int id,int cnt){
		int y=fd(rt,num);
		int x=++idx;
		t[x].cnt=cnt,t[x].id=id;
		t[y].s[num>t[y].val]=x;
		t[x].fa=y;
		t[x].s[0]=t[x].s[1]=t[x].tag1=t[x].tag2=0;
		t[x].val=num;
		splay(x,0);
	}
	void clr(int x){
		if(x==0)
			return;
		pushdown(x);
\/\/		cout<<"clr"<<x<<" "<<t[x].id<<" "<<t[x].val<<" "<<t[x].cnt<<endl;
		insert(t[x].val,t[x].id,t[x].cnt);
		clr(t[x].s[0]);
		clr(t[x].s[1]);
	}
	void update(int num){
		splay(fd(rt,num),0);
		if(t[rt].val>=num)
			splay(fd(t[rt].s[0],inf),0);
\/\/		cout<<t[rt].val<<endl;
		splay(fd(t[rt].s[1],num*2),rt);
		int tmp=t[rt].s[1];
		if(t[tmp].val<num*2)
			splay(fd(t[tmp].s[1],-inf),rt);\/\/可能会存在不存在这一部分的情况
		tmp=t[rt].s[1];
\/\/		cout<<"rt:"<<t[tmp].id<<" "<<t[tmp].val<<" "<<t[tmp].cnt<<" "<<t[tmp].tag1<<" "<<t[tmp].tag2<<endl;
\/\/		cout<<"ls:"<<t[t[tmp].s[0]].id<<" "<<t[t[tmp].s[0]].val<<" "<<t[t[tmp].s[0]].cnt<<" "<<t[t[tmp].s[0]].tag1<<" "<<t[t[tmp].s[0]].tag2<<endl;
\/\/		cout<<"rs:"<<t[t[tmp].s[1]].id<<" "<<t[t[tmp].s[1]].val<<" "<<t[t[tmp].s[1]].cnt<<" "<<t[t[tmp].s[1]].tag1<<" "<<t[t[tmp].s[1]].tag2<<endl;
		t[tmp].tag1+=-num;
		t[tmp].tag2++;
		t[tmp].val+=-num;
		t[tmp].cnt++;
		pushdown(tmp);
		int tmpp=t[tmp].s[0];
		t[tmp].s[0]=0;
		clr(tmpp);
	}
	void output(int x){
		int tmp=x;
		cout<<"x:"<<t[tmp].id<<" "<<t[tmp].val<<" "<<t[tmp].cnt<<" "<<t[tmp].tag1<<" "<<t[tmp].tag2<<endl;
		cout<<"ls:"<<t[t[tmp].s[0]].id<<" "<<t[t[tmp].s[0]].val<<" "<<t[t[tmp].s[0]].cnt<<" "<<t[t[tmp].s[0]].tag1<<" "<<t[t[tmp].s[0]].tag2<<endl;
		cout<<"rs:"<<t[t[tmp].s[1]].id<<" "<<t[t[tmp].s[1]].val<<" "<<t[t[tmp].s[1]].cnt<<" "<<t[t[tmp].s[1]].tag1<<" "<<t[t[tmp].s[1]].tag2<<endl;
		if(t[tmp].s[0])
			output(t[tmp].s[0]);
		if(t[tmp].s[1])
			output(t[tmp].s[1]);
	}
	void dfs(int x){
		pushdown(x);
\/\/		print(x),pc(' '),print(t[x].id),pc(' '),print(t[x].val),pc(' '),print(t[x].cnt),pc('\n');
		ans[t[x].id]=t[x].cnt;
		if(t[x].s[0])
			dfs(t[x].s[0]);
		if(t[x].s[1])
			dfs(t[x].s[1]);
	}
}T;

signed main(){
	signed n=read();
	for(int i=1;i<=n;i++)
		a[i]={read(),read()};
	sort(a+1,a+1+n);
	int m=read();
	T.insert(inf,0,0);
\/\/		T.dfs(T.rt),pc('\n'),
	T.insert(-inf,0,0);
\/\/		T.dfs(T.rt),pc('\n');
	for(int i=1;i<=m;i++)
\/\/		T.dfs(T.rt),pc('\n'),
		T.insert(read(),i,0);
\/\/	T.dfs(T.rt),pc('\n');
	for(int i=1;i<=n;i++){
\/\/		T.dfs(T.rt);
\/\/		cout<<endl;
\/\/		cout<<a[i].c<<endl;
\/\/		cout<<endl;
		T.update(a[i].c);
\/\/		T.output(T.rt);
	}
	T.dfs(T.rt);
	for(int i=1;i<=m;i++)
		print(ans[i]),pc(' ');
	pc('\n');
	return 0;
}