题意:你需要订阅一些服务,每个服务每天需要花费\(c_i\),要从第\(a_i\)用到第\(b_i\)天,你可以购买会员,会员每天需要花费\(C\),但是这天的服务不用再另花钱了,问你订阅这些服务的最小花费是多少.

题解:对于这种某一段区间的加加减减的问题,我们首先应该考虑的是用差分,我们可以用map来做差分数组,然后遍历map累加差分数组的前缀和,再和\(C\)比较,贡献给答案就可以了.

代码:

#include
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
#define rep(a,b,c) for(int a=b;a<=c;++a) #define per(a,b,c) for(int a=b;a>=c;--a)
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair PII;
typedef pair PLL;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}

int n,c;
map mp;

int main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

cin>>n>>c;

rep(i,1,n){
    int a,b,w;
    cin>>a>>b>>w;
    mp[a]+=w;
    mp[b+1]-=w;
}

ll ans=0,cur=0,last=0;

for(auto [x,y]:mp){
    ll mi=min(cur,1ll*c);
    ans+=mi*(x-last);
    cur+=y;
    last=x;
}

cout<<ans<<'\n';

return 0;

}