CF702F – T-shirts - 小白菜博客

结构稳，01 分，枉划层，谁想锦衣自选人？不过贪婪座下臣。

\(\text{Treap}\)

我们的第一个想法是用衣服贡献人。把衣服按照 \(\{-p_i,c_i\}\) 为关键字排序，然后依次遍历衣服，看当前哪些人会买当前的衣服。

我们可以用 \(fhqTreap\) 这样的数据结构维护所有的人的 \(\{b_i,ans_i,id_i\}\)，按照 \(b_i\) 为关键字排序。然后遍历衣服的过程中，我们把所有 \(b_j\ge c_i\) 的点 \(split\) 出来，打上标记再 \(merge\) 回去。

但是存在一个问题，两个 \(fhqTreap\) 合并必须保证两边是不相交的，也就是 \(left\) 中的最大数要小于等于 \(right\) 中的最小树。在我们刚分裂出来的时候很明显是有这个性质的，但是我们打上标记，\(merge\) 的时候 \(pushdown\) 一下，就破坏了这个性质。所以我们需要单独把 \(c_i\le b_j\lt 2c_i\) 的点拿出来暴力更改 \(b_j,ans_j\)，并暴力插入左边的子树。

仔细想想，这样其实是正确的，因为如果一个点被暴力插入了，那么 \(c_i\le b_j\lt 2c_i\)，所以 \(b_j-c_i\le b_j-\dfrac{b_j}{2}=\dfrac{b_j}{2}\)。也就是每次被暴力插入，\(b_j\) 最多为原来的一半，而没有价值为 \(0\) 的货物，则 \(b_j\) 必须是正数才能买东西。所以每个 \(j\) 只会被暴力插入 \(\log _2 b_j\) 次。我们就可以按照 \(c_i\) 和 \(2c_i\) 分裂出三棵子树 \(l,mid,r\)，然后遍历 \(mid\) 插入 \(l\)，给 \(r\) 打上标记，合并 \(l\) 和 \(r\) 即可。

每个人被插入 \(\log\) 次，每次插入 \(O(\log q)\)，总复杂度 \(O(n\log q\log b)\)


class FHQTreap{
	struct Treap{
		int val,key,ans,id;
		int left,right,tgv,tga;
	}tr[10000005];
	int idx=0;
	int newnode(int _val,int _ans,int _id){
		int x=++idx;
		tr[x].val=_val;
		tr[x].left=0,tr[x].right=0;
		tr[x].key=rand()%1919810+1;
		tr[x].ans=_ans,tr[x].id=_id;
		return x;
	}
	void pushdown(int x){
		if(!x)return;
		if(!tr[x].tgv&&!tr[x].tga)return;
		tr[x].val-=tr[x].tgv,tr[x].ans+=tr[x].tga;
		if(tr[x].left)tr[tr[x].left].tgv+=tr[x].tgv,tr[tr[x].left].tga+=tr[x].tga;
		if(tr[x].right)tr[tr[x].right].tgv+=tr[x].tgv,tr[tr[x].right].tga+=tr[x].tga;
		tr[x].tgv=tr[x].tga=0;
	}
	void split(int x,int val,int &l,int &r){
		if(!x)return (void)(l=r=0);
		pushdown(x);
		if(tr[x].val<=val){
			l=x;
			split(tr[x].right,val,tr[x].right,r);
		}
		else {
			r=x;
			split(tr[x].left,val,l,tr[x].left);
		}
	}
	int merge(int l,int r){
		pushdown(l);
		pushdown(r);
		if(!l||!r)return l+r;
		if(tr[l].key<tr[r].key){
			tr[l].right=merge(tr[l].right,r);
			return l;
		}else{
			tr[r].left=merge(l,tr[r].left);
			return r;
		}
	}
	struct node{
		int val,ans,id;
		node(int _val,int _ans,int _id){
			val=_val,ans=_ans,id=_id;
		}
	};
	void tree(int x,vt<node>&v){
		if(!x)return;
		pushdown(x);
		tree(tr[x].left,v);
		v.pb({tr[x].val,tr[x].ans,tr[x].id});
		tree(tr[x].right,v);
	}
public:
	int root;
	void insert(int &x,int val,int ans,int id){
		int l,r,tmp;
		split(x,val,l,r);
		tmp=newnode(val,ans,id);
		x=merge(merge(l,tmp),r);
	}
	void opt(int val){
		int l=0,r=0,mid=0;
		split(root,val-1,l,r);
		split(r,2*val-1,mid,r);
		vt<node>nv;
		tree(mid,nv);
		for(auto i:nv)insert(l,i.val-val,i.ans+1,i.id);
		if(r!=0)tr[r].tgv+=val,tr[r].tga++;
		root=merge(l,r);
	}
	vt<node>output(){
		vt<node>res;
		tree(root,res);
		return res;
	}
}Treap;
vt<pii>v;
int n,m,p[200005],c[200005],b[200005],ans[200005];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	rp(i,n){
		cin>>c[i]>>p[i];
		v.pb({-p[i],c[i]});
	}sort(v.begin(),v.end());
	cin>>m;
	rp(i,m)cin>>b[i];
	rp(i,m)Treap.insert(Treap.root,b[i],0,i);
	for(auto i:v)Treap.opt(i.second);
	auto res=Treap.output();
	for(auto i:res)ans[i.id]=i.ans;
	rp(i,m)cout<<ans[i]<<" ";
	cout<<endl;
	return 0;
}
//Crayan_r

二进制分组

我们考虑将所有的衣服按照二进制最高位分组，每次处理一个组内的答案。

我们发现二进制分组之后，对于组内的 \(i,j,k\) 满足 \(p_i>p_j>p_k\)，一定有 \(c_j+c_k\ge c_i\)。那么我们组内排序之后，不可能跳过某个衣服而在后面选两个衣服。因为只选前一件一定更优。所以我们在当前组中选择的一定是一段前缀加上后面的某个数。

我们对每个人记录他当前选择的最差的品质 \(cur_i\)，则下一次选择一定是选择 \(new\ge cur_i\) 的衣服。然后我们每处理完一组之后就删掉这一组，使得我们当前的所有衣服中只剩下当前组和更小组的衣服。

然后我们先对所有剩下的衣服的价值和件数做前缀和 \(sum_i\) 和 \(cnt_i\)。每次在剩下的衣服中二分出一个位置 \(new\)。这就是我们要在当前组中选的一段前缀。当然，我们选前缀的同时还要把所有更小组的、品质在此区间内的衣服选进来，所以我们是给剩下的所有衣服做前缀和而不是仅当前组。

我们对每个人把前缀的贡献计算上，然后重新计算前缀和。现在我们要计算的是在前缀之外再选一个。额外的位置要满足品质比原先更劣，且在这一区间内更小组的衣服都要选上（当前组则不必要）。

我们用优先队列记录所有的人。当来到 \(p_i=cur_j\) 时，就把 \(j\) 加入优先队列。然后如果当前的点是当前组的，把所有能买的起当前点和前面的更小组的点的人都 \(pop\) 出来，删除当前点，不应也不能再 \(push\) 回去，因为每个人只会多选一次。

最后，我们把所有的人都输出答案。复杂度 \(O((q\log n+n\log q)\log b)\)。

ll n,m,cur[200005],p[200005],c[200005],b[200005],exi[200005];
ll ans[200005],cnt[200005],sum[200005],to[200005],bit[200005];
vector<pair<int,int> >vp;
vector<int>lft[200005];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	rp(i,n)cin>>c[i]>>p[i];
	rp(i,n)vp.pb({-p[i],c[i]});
	sort(vp.begin(),vp.end());
	rp(i,n)c[i]=vp[i-1].second,exi[i]=1;
	cin>>m;rp(i,m)cin>>b[i];
	rp(i,n){
		int x=c[i];bit[i]=-1;
		while(x)x>>=1,bit[i]++;
	}
	per(w,0,30){
		rp(i,n){
			sum[i]=sum[i-1]+c[i];
			cnt[i]=cnt[i-1]+exi[i];
			lft[i].clear();
		}
		rp(i,m){
			int nw=upper_bound(sum+1,sum+1+n,b[i]+sum[cur[i]])-sum-1;
			if(nw>cur[i]){
				b[i]-=(sum[nw]-sum[cur[i]]);
				ans[i]+=(cnt[nw]-cnt[cur[i]]);
				cur[i]=nw;
			}lft[cur[i]+1].pb(i);
		}
		rp(i,n){
			sum[i]=sum[i-1]+(bit[i]!=w)*c[i];
			cnt[i]=cnt[i-1]+(bit[i]!=w)*exi[i];
		}priority_queue<pair<int,int> >pq;
		rp(i,n){
			for(auto j:lft[i])pq.push({b[j]+sum[cur[j]],j});
			if(bit[i]==w){
				while(pq.size()&&pq.top().first>=sum[i]+c[i]){
					int j=pq.top().second;pq.pop();
					b[j]-=(sum[i]-sum[cur[j]]+c[i]);
					ans[j]+=(cnt[i]-cnt[cur[j]]+1),cur[j]=i;
				}
				c[i]=0,exi[i]=0;
			}
		}
	}
	rp(i,m)cout<<ans[i]<<" ";
	cout<<endl;
	return 0;
}
//Crayan_r