CF1070C Cloud Computing 题解

分析

思路不难想，我们对于第 \(i\) 个计划的时间，可以分成 \(l\) 和 \(r+1\) 两部分。用权值线段树维护，在第 \(l\) 天的时候就将该计划的内容加入权值线段树中，直到过了该计划的时间，也就是第 \(r+1\) 天，再将这个计划的内容删除。把每一天需要修改的内容存进 vector 中，修改完查询权值线段树中前 \(k\) 个数的值即可。

比较难想的是查询。如果当前区间中的 CPU 数量不超过 \(k\)，则表示这个区间能够凑出的 CPU 数量是无法达到 \(k\) 的。为了使答案尽量趋近于 \(k\)，这个区间的贡献就是区间的代价和。如果区间中 CPU 数量比 \(k\) 大，则优先考虑左子区间，右子区间只需要补上左区间差的那些数量。这里要特判一下边界，在左右端点相同且数量大于 \(k\) 的时候，直接返回 \(k \times val\)。\(val\) 是这个点的点权，也就是端点下标。

复杂度是 \(O((n+m) \log V)\) 的，\(V\) 是值域。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
#define x first
#define y second
#define re register
#define il inline

const int N=1e6+10;
int n,k,m,ans;
struct node{
	int l,r,cnt,val;
}tr[N<<2];
vector<PII> add[N];

il void up(int now){
	tr[now].cnt=tr[now<<1].cnt+tr[now<<1|1].cnt;
	tr[now].val=tr[now<<1].val+tr[now<<1|1].val;
	return ;
}
il void build(int now,int l,int r){
	tr[now].l=l,tr[now].r=r;
	if(l!=r){
		int mid=l+r>>1;
		build(now<<1,l,mid),build(now<<1|1,mid+1,r);
	}
	return ;
}
il void insert(int now,int k,int c){
	if(tr[now].l==tr[now].r) tr[now].cnt+=c,tr[now].val+=k*c;
	else{
		int mid=tr[now].l+tr[now].r>>1;
		if(k<=mid) insert(now<<1,k,c);
		else insert(now<<1|1,k,c);
		up(now);
	}
	return ;
}
il int query(int u,int k){
	if(tr[u].cnt<=k) return tr[u].val;
	else{
		if(tr[u].l==tr[u].r) return k*tr[u].l;
		if(tr[u<<1].cnt>=k) return query(u<<1,k);
		else return tr[u<<1].val+query(u<<1|1,k-tr[u<<1].cnt); 
	}
}

il void solve(){
	cin>>n>>k>>m;
	build(1,1,N-9);
	for(re int i=1,l,r,c,p;i<=m;++i)
		cin>>l>>r>>c>>p,
		add[l].push_back({c,p}),add[r+1].push_back({-c,p});
	for(re int i=1;i<=n;++i){
		for(auto j:add[i]) insert(1,j.y,j.x);
		ans+=query(1,k);
	}
	cout<<ans;
	return ;
}

signed main(){
	solve();
	return 0;
}