蓝桥杯备考：一维差分算法之海底高铁

P3406 海底高铁 - 洛谷 | 计算机科学教育新生态

如图，从3到1就是把1这段铁路和2这段铁路+1，区间实际上就是[l,r-1]

所以当我们修改的时候实际上就是 差分数组L[l]++,R[r]-- 就完成区间的修改了

又因为3到1是倒着来的，我们只需要交换一下就行了，最后我们再把消费最少的方案都加和就完成了

#include <iostream>
using namespace std;
const int N = 1e5+10;
int L[N],a[N],s[N];
int main()
{int n,m; cin >> n >> m;int x;cin >> x;for(int i = 2;i<=m;i++){int y; cin >> y;if(x>y){L[y]++;L[x]--;}elseL[x]++,L[y]--;x = y;}for(int i = 1;i<n;i++){L[i]+=L[i-1];}long long ret = 0;for(int i = 1;i<n;i++){long long a,b,c; cin >> a >> b >> c;ret+=min(L[i]*a,c+L[i]*b);}cout << ret << endl;	return 0;
}