看到这题，第一反应是用线段树。但本题数据 \(1 \le a_i \le b_i \le 10^9\)，时间、空间复杂度均无法接受，于是改变思考方向。
维护区间修改的另一种方法是差分。但是由于区间长度很长，就不能对整个差分数组进行计算。取而代之的有一种方法，即将所有的有差分值的点记录下来，按其时间先后顺序进行排序，最后再依次枚举每一个点，计算当前每天应交的钱，再计算当前区间的长度，即可求出每一个区间的应交的钱。
注意，计算区间值时应当用当前每天应交的钱与 \(C\) 的较小值来乘（\(C\) 为题目中所述含义），但不能更新每天应交的钱。
代码如下：
#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;
int a,b,c,len,now,money,t,n,k,ans;
struct atc
{
int p;
int q;
}d[1000001];
bool cmp(atc x,atc y)
{
return x.p<y.p;
}
signed main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a>>b>>c;
len++;
d[len].p=a;
d[len].q=c;
len++;
d[len].p=b+1;
d[len].q=-c;
}
sort(d+1,d+len+1,cmp);
money=d[1].q;
now=d[1].p;
for(int i=2;i<=len;i++)
{
t=d[i].p;
if(t!=now) ans+=(t-now)*min(money,k);
now=t;
money+=d[i].q;
}
cout<<ans;
return 0;
}