CF702F-T-Shirts【FhqTreap】(CF702F-T-Shirts【FhqTreap】)

正题

题目链接:https://www.luogu.com.cn/problem/CF702F

题目大意

有\(n\)个物品,第\(i\)个价格为\(c_i\),质量为\(q_i\)。

然后有\(m\)个询问,假设一个人有\(v_i\)块,他每次会买他能买得起的\(q_i\)最大的(如果相同就\(c_i\)最小的)物品购买,直到买不起为止,一个物品只能买一次,求他最后能买多少个物品。

\(1\leq n,m\leq 2\times 10^5,1\leq c_i,q_i,v_i\leq 10^9\)

解题思路

考虑最暴力的做法,我们可以把所有物品按照\(q_i\)从大到小排序,然后对于每个人枚举所有物品,如果买得起就买,这样就是\(O(nm)\)的了。

考虑如何优化这个做法,在线显然难搞,我们考虑把所有人放在一起维护。

对于物品价格为\(c\),那么所有\(v_i\geq c\)的都有\(ans_i+1,v_i-c\)。

也就是对于一个值域进行操作,考虑到这个值域是动态的,尝试用平衡树维护

那么考虑对于钱数为\([0,c-1]\)的人不操作。

对于钱数为\([c,2\times c-1]\)的人,\(ans_i+1,v_i-c\),并且\(v_i-c<c\)。也就是说此时减去后范围都在\([0,c-1]\),会和原来\([0,c-1]\)范围内的人有重复。

对于钱数为\([2\times c,\infty)\)的人,\(ans_i+1,v_i-c\),并且\(v_i-c\geq c\),也就是说这一部分整体往前移动\(c\)位之后不会和其它部分的人有交叉。那么这一部分的人我们可以打一个标记然后插回平衡树中。

那么现在问题是\([c,2\times c-1]\)部分的人如何操作,注意到此时有\(v_i-c\leq \frac{v_i}{2}\),也就是一个\(v_i\)最多操作\(\log\)次,所以我们可以直接暴力把这一部分提出来然后一个一个插回去。

用\(\text{FhqTreap}\)很轻易实现以上功能

时间复杂度:\(O(n\log n\log v)\)

code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e5+10;
int n,m,root;
struct node{
	int q,v;
}q[N];
struct FHQ_Treap{
	int cnt,siz[N],rnk[N],t[N][2];
	int w[N],ans[N],lazy1[N],lazy2[N];
	int NewNode(int val){
		++cnt;w[cnt]=val;siz[cnt]=1;
		rnk[cnt]=rand();return cnt;
	}
	void PushUp(int x)
	{siz[x]=siz[t[x][0]]+siz[t[x][1]]+1;return;}
	void PushDown(int x){
		for(int i=0;i<2;i++){
			if(!t[x][i])continue;
			lazy1[t[x][i]]+=lazy1[x];
			lazy2[t[x][i]]+=lazy2[x];
			w[t[x][i]]+=lazy1[x];
			ans[t[x][i]]+=lazy2[x];
		}
		lazy1[x]=lazy2[x]=0;
		return;
	}
	void Split(int &x,int &y,int p,int k){
		if(!p){x=y=0;return;}PushDown(p);
		if(w[p]<=k)x=p,Split(t[x][1],y,t[p][1],k);
		else y=p,Split(x,t[y][0],t[p][0],k);
		PushUp(p);return;
	}
	int Merge(int x,int y){
		PushDown(x);PushDown(y);
		if(!x||!y)return x|y;
		if(rnk[x]<rnk[y]){
			t[x][1]=Merge(t[x][1],y);
			PushUp(x);return x;
		}
		else{
			t[y][0]=Merge(x,t[y][0]);
			PushUp(y);return y;
		}
	}
	void Ins(int p,int &root){
		int x,y;
		Split(x,y,root,w[p]);
		root=Merge(Merge(x,p),y);
		return;
	}
	void Deal(int p,int c,int &root){
		if(!p)return;
		PushDown(p);
		Deal(t[p][0],c,root);
		Deal(t[p][1],c,root);
		t[p][0]=t[p][1]=0;
		ans[p]++;lazy2[p]++;
		w[p]-=c;lazy1[p]-=c;
		Ins(p,root);
	}
	void Solve(int c){
		int x,y,z;
		Split(x,y,root,c-1);
		Split(y,z,y,2*c-1);
		if(z){
			ans[z]++;lazy2[z]++;
			w[z]-=c;lazy1[z]-=c;
		}
		root=Merge(x,z);
		Deal(y,c,root);
		return;
	}
	void Fors(int p){
		if(!p)return;PushDown(p);
		Fors(t[p][0]);Fors(t[p][1]);
		return;
	}
}T;
bool cmp(node x,node y)
{return (x.q==y.q)?(x.v<y.v):(x.q>y.q);}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&q[i].v,&q[i].q);
	sort(q+1,q+1+n,cmp);
	scanf("%d",&m);
	for(int i=1,x;i<=m;i++){
		scanf("%d",&x);
		T.Ins(T.NewNode(x),root);
	}
	for(int i=1;i<=n;i++)
		T.Solve(q[i].v);
	T.Fors(root);
	for(int i=1;i<=m;i++)
		printf("%d ",T.ans[i]);
	return 0;
}
————————

Topic

题目链接:https://www.luogu.com.cn/problem/CF702F

General idea of the topic

There are \ (n \) items. The price of \ (I \) is \ (c_i \) and the quality is \ (q_i \).

Then there are \ (m \) questions. Suppose a person has \ (v_i \) pieces, he will buy the largest \ (q_i \) items he can afford each time (if the same, the smallest \ (c_i \) items until he can’t afford them. An item can only be bought once. Ask how many items he can buy in the end.

\(1\leq n,m\leq 2\times 10^5,1\leq c_i,q_i,v_i\leq 10^9\)

Problem solving ideas

Considering the most violent approach, we can sort all items according to \ (q_i \) from large to small, and then enumerate all items for everyone. If we can afford to buy them, we can buy them, which is \ (O (nm) \).

Considering how to optimize this practice, it is obviously difficult to do online. We consider putting everyone together for maintenance.

If the item price is \ (C \), then all \ (v_i \ GEQ C \) have \ (ans_i + 1, v_i-c \).

That is, when operating on a value range, considering that the value range is dynamic, try to maintain it with a balance tree

Then consider not operating for people with \ ([0, C-1] \) money.

For people with \ ([C, 2 \ times C-1] \), \ (ans_i + 1, v_i-c \), and \ (v_i-c & lt; C \). In other words, the range after subtraction is \ ([0, C-1] \), which will be repeated with those within the original \ ([0, C-1] \).

For people with \ ([2 \ times C, \ infty) \), and \ (ans_i + 1, v_i-c \), and \ (v_i-c \ GEQ C \), that is, this part will not cross with other parts after moving forward \ (C \) as a whole. Then we can mark the people in this part and insert them back into the balance tree.

Now, the question is how to operate the \ ([C, 2 \ times C-1] \) part. Notice that there is \ (v_i-c \ Leq \ frac{v_i}{2} \), that is, a \ (v_i \) can operate \ (\ log \) times at most, so we can directly raise this part and insert it back one by one.

The above functions can be easily realized with \ (\ text {fhqtreap} \)

Time complexity: \ (O (n \ log n \ log V) \)

code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e5+10;
int n,m,root;
struct node{
	int q,v;
}q[N];
struct FHQ_Treap{
	int cnt,siz[N],rnk[N],t[N][2];
	int w[N],ans[N],lazy1[N],lazy2[N];
	int NewNode(int val){
		++cnt;w[cnt]=val;siz[cnt]=1;
		rnk[cnt]=rand();return cnt;
	}
	void PushUp(int x)
	{siz[x]=siz[t[x][0]]+siz[t[x][1]]+1;return;}
	void PushDown(int x){
		for(int i=0;i<2;i++){
			if(!t[x][i])continue;
			lazy1[t[x][i]]+=lazy1[x];
			lazy2[t[x][i]]+=lazy2[x];
			w[t[x][i]]+=lazy1[x];
			ans[t[x][i]]+=lazy2[x];
		}
		lazy1[x]=lazy2[x]=0;
		return;
	}
	void Split(int &x,int &y,int p,int k){
		if(!p){x=y=0;return;}PushDown(p);
		if(w[p]<=k)x=p,Split(t[x][1],y,t[p][1],k);
		else y=p,Split(x,t[y][0],t[p][0],k);
		PushUp(p);return;
	}
	int Merge(int x,int y){
		PushDown(x);PushDown(y);
		if(!x||!y)return x|y;
		if(rnk[x]<rnk[y]){
			t[x][1]=Merge(t[x][1],y);
			PushUp(x);return x;
		}
		else{
			t[y][0]=Merge(x,t[y][0]);
			PushUp(y);return y;
		}
	}
	void Ins(int p,int &root){
		int x,y;
		Split(x,y,root,w[p]);
		root=Merge(Merge(x,p),y);
		return;
	}
	void Deal(int p,int c,int &root){
		if(!p)return;
		PushDown(p);
		Deal(t[p][0],c,root);
		Deal(t[p][1],c,root);
		t[p][0]=t[p][1]=0;
		ans[p]++;lazy2[p]++;
		w[p]-=c;lazy1[p]-=c;
		Ins(p,root);
	}
	void Solve(int c){
		int x,y,z;
		Split(x,y,root,c-1);
		Split(y,z,y,2*c-1);
		if(z){
			ans[z]++;lazy2[z]++;
			w[z]-=c;lazy1[z]-=c;
		}
		root=Merge(x,z);
		Deal(y,c,root);
		return;
	}
	void Fors(int p){
		if(!p)return;PushDown(p);
		Fors(t[p][0]);Fors(t[p][1]);
		return;
	}
}T;
bool cmp(node x,node y)
{return (x.q==y.q)?(x.v<y.v):(x.q>y.q);}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&q[i].v,&q[i].q);
	sort(q+1,q+1+n,cmp);
	scanf("%d",&m);
	for(int i=1,x;i<=m;i++){
		scanf("%d",&x);
		T.Ins(T.NewNode(x),root);
	}
	for(int i=1;i<=n;i++)
		T.Solve(q[i].v);
	T.Fors(root);
	for(int i=1;i<=m;i++)
		printf("%d ",T.ans[i]);
	return 0;
}