D - Snuke Prime (差分)

D - Snuke Prime (差分)

最后一刻看懂题目在干嘛了但是没时间做了，题意是固定权值$C$，给定$n$个区间$[a,b]$和对应的权值$c$，然后我们要填充这些区间，对于某一个有活动的一天，我们可以选择$C$或者这一天对应的活动权值之和，取最小的求和。

思路：因为是区间修改，所以考虑上差分，因为数据范围有$1e9$，所以上$map$，计算贡献就是维护一个$sum$和当前区间左端点的$l$初始为$l=0$，每次计算完贡献后更新区间$l_{next}=r_{pre}$。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define lx x<<1
#define rx x<<1|1
map<int,ll>mp;
int main(){
	int n,C;
	scanf("%d%d",&n,&C);
	for(int i=1;i<=n;i++){
		int a,b,c;scanf("%d%d%d",&a,&b,&c);
		mp[a]+=c,mp[b+1]-=c;
	}
	int l=0;ll ans=0,s=0;
	for(auto p:mp){
		ans+=1LL*min(1LL*C,s)*(p.fi-l);
		l=p.fi;
		s+=p.se;
	}printf("%lld\n",ans); 
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27