CF EDU ROUND 172

C

枚举断点贪心

一个01串，1表示归b，0表示归b。可以把这个串分成m个区间，从左往右第i个区间里的每个元素权值都是$i-1$，问至少划分成几个区间，$b$的分数-$a$的分数不少于
$k$

这种直接想怎么划分，化成几段不好想，可以从每次操作的变化入手。具体来说，可以考虑再一个位置划分后，$b-a$会怎么变化，左边的显然不变右侧的所有元素，所在区间编号都+1了，其中1对答案的贡献本来就是$id$，现在变成$id+1$了，贡献增加右侧1的个数，0对答案的贡献原本是$-id$，现在是$-(id+1)$，贡献减少右侧0的个数。

因此在一个地方划分，对答案的影响就是右侧1的个数-0的个数。我们可以对这个影响降序排序，然后找前缀，直到贡献加起来大于k。如果全加起来都不到k，那么无解

void solve(){
	cin>>n>>k;
	vi b;
	string s;
	cin>>s;
	s=' '+s;
	
	int sum=0;
	rep1(i,n,2){
		if(s[i]=='1')sum++;
		else sum--;
		b.pb(sum);
	}
	sort(b.begin(),b.end(),[&](int x,int y){
		return x>y;
	});
	int ans=0;
	for(int x:b){
		if(k>x){
			k-=x;
			ans++;
		}
		else{
			ans++;
			k=0;
			break;
		}
	}
	if(k)cout<<-1<<'\n';
	else cout<<ans+1<<'\n';
}

D

给一堆区间，对于一个区间，所有包含这个区间的其他区间的交集大小，减去这个区间的大小，就是这个区间的推荐集合的大小，我们要求这个值。

转化一下，包含一个区间的所有区间，实际上就是$l_1<=l,r_1>=r$，这是个二位偏序，我们可以排序+线段树，遍历每个区间和包含它的所有区间。然后我们要求包含一个区间的所有区间的交集实际上就是求$max(l_1),min(r_1)$，然后做差就是交集大小。

先说求$min(r1)$，我们前面说了，可以排序+线段树维护$r_1>r$的所有$r$，然后线段树查$[r,mx]$这个区间里的最小值就行了，这可以用一个权值线段树，存所有$r$的出现次数，然后在$[r,mx]$里找最小的非零位置就行了，这实际上是一个线段树二分。

当然后来我意识到，查询不小于某个值的最小值，实际上可以直接用set.lower_bound，这里做麻烦了

然后求$l_1<=l$里的最大值，同理。

最后对于每个$[l,r]$我们都可以求出$max(l_1),min(r_1)$，$max(l_1)-min(r_1)-(r-l)$即为答案

struct Tree{
	struct Node{
		int l,r,mx;
	}tr[N<<2];
	
	void pushup(int u){
		tr[u].mx=tr[ls].mx+tr[rs].mx;
	}
	
	void build(int u,int l,int r){
		tr[u]={l,r,0};
		if(l==r)	return;
		int mid=(l+r)>>1;
		build(ls,l,mid);	build(rs,mid+1,r);
		pushup(u);
	}
	
	void modify(int u,int idx,int val){
		if(tr[u].l==tr[u].r)	tr[u].mx+=val;
		else{
			int mid=(tr[u].l+tr[u].r)>>1;
			if(mid>=idx)	modify(ls,idx,val);
			else modify(rs,idx,val);
			pushup(u);	
		}
	}
	
	int query(int u,int l,int r){
		if(r<tr[u].l||tr[u].r<l)	return 0;
		if(l<=tr[u].l&&tr[u].r<=r)	return  tr[u].mx;
		return query(ls,l,r)+query(rs,l,r);	
	}
	int ask(int u,int l,int r){
		if(tr[u].l==tr[u].r)	return tr[u].l;
		else{
			int mid=(tr[u].l+tr[u].r)>>1;
			if(r<=mid)return ask(ls,l,r);
			if(l>mid)return ask(rs,l,r);
			int res=query(ls,l,r);
			if(res) return ask(ls,l,r);
			else return ask(rs,l,r);
		}
	}
	int ask1(int u,int l,int r){
		if(tr[u].l==tr[u].r)	return tr[u].l;
		else{
			int mid=(tr[u].l+tr[u].r)>>1;
			if(r<=mid)return ask1(ls,l,r);
			if(l>mid)return ask1(rs,l,r);
			int res=query(rs,l,r);
			if(res) return ask1(rs,l,r);
			else return ask1(ls,l,r);
		}
	}
}t;
void solve(){
	cin>>n;
	vi l(n+1),r(n+1),l1(n+1),r1(n+1);
	rep(i,1,n)cin>>l[i]>>r[i];
	
	vi all;
	rep(i,1,n){
		all.pb(l[i]);
		all.pb(r[i]);
	}
	sort(all.begin(),all.end());
	all.erase(unique(all.begin(),all.end()),all.end());
	
	unordered_map<int,int>lisan;
	rep(i,1,n){
		lisan[l[i]]=lower_bound(all.begin(),all.end(),l[i])-all.begin()+1;
		lisan[r[i]]=lower_bound(all.begin(),all.end(),r[i])-all.begin()+1;
	}
	
	map<int,vi>mp,mp1;
	rep(i,1,n){
		mp[l[i]].pb(i);
		mp1[r[i]].pb(i);
	}
	
	m=all.size();
	t.build(1,1,m);
	
	for(auto &[k,v]:mp){
		for(int id:v){
			t.modify(1,lisan[r[id]],1);
		}
		for(int id:v){
			t.modify(1,lisan[r[id]],-1);
			int sum=t.query(1,lisan[r[id]],m);
			if(!sum){
				t.modify(1,lisan[r[id]],1);
				continue;
			}
			int pos=t.ask(1,lisan[r[id]],m);
			r1[id]=all[pos-1];
			t.modify(1,lisan[r[id]],1);
		}
	}
	
	t.build(1,1,m);
	for(auto it=mp1.rbegin();it!=mp1.rend();++it){
		for(int id:it->second){
			t.modify(1,lisan[l[id]],1);
		}
		for(int id:it->second){
			t.modify(1,lisan[l[id]],-1);
			int sum=t.query(1,1,lisan[l[id]]);
			if(!sum){
				t.modify(1,lisan[l[id]],1);
				continue;
			}
			int pos=t.ask1(1,1,lisan[l[id]]);
			l1[id]=all[pos-1];
			t.modify(1,lisan[l[id]],1);
		}
	}
	rep(i,1,n){
		if(l1[i]&&r1[i]){
			cout<<r1[i]-l1[i]-(r[i]-l[i])<<'\n';
		}
		else{
			cout<<0<<'\n';
		}
	}
}