题解 P3406 【海底高铁】
NKU_AI_HMX · · 题解
题目很好理解，就是按照我们的方法会爆，大家看了那么多题解应该也知道为什么了，笔者在这里推荐一道题，大家可以去试试，二维差分——地毯。
我们步入正文：
先来个故事：
我们在一遍遍覆盖的方法肯定是行不通的，那么有什么办法能不用经过一段铁路就把每个城市都加一遍1吗？当然是有的。
大家不妨想一想，我们在马路上会有警示牌啥的，告诉你前面是弯路，前面容易发生交通事故，前方容易遇见自己的未来女友......
但是警示牌不会在那一整段路上都插满（每毫米插一个？），他也只是在你将要进入那个路段，给你一个警示，然后我们自己就会在那一整段路上都注意（有没有未来女友），然后我们开过那段路之后，你就能差不多知道那段路已经过了（到了基友家）。
比如路牌说前方急转弯，好，当接着100m都是直路这时候我们就知道开过了，我们就不会受刚才的路牌影响，而是被下一个路牌影响，比如直路上有个路牌说“前方直路，小心开车过快，导致翻车” 接下来你就会在那一整段直路上注意，而不需要那一整段路上都给你插满“前方直路，小心开车过快，导致翻车”这个标语（老司机从不翻车）。
而这道题也是一样的。为什么我们要给经过的每个城市都加1呢？我们就不能也设置一个路牌吗？告诉计算机，接下来的一段铁路被经过了几次，然后在结束的时候再告诉他，结束了，你等待下一个路牌的指示，让下一个路牌告诉你下一段经过了几次。
我想这就是这题的思想
由于我们是正着遍历的，所以当你从数字较大的城市到小的城市，数字大的减一，小的加1，这样我们经过小的城市的时候我们就知道接下来的那段铁路是被经过了多少次，而到了减一的城市之后接下来经过的铁路就不受刚才路牌的影响，因为原来加的被减了呀。
所以关键在于如何构建路牌，这是一维的构建方法，二维也有他的构建方法，而且对于二维而言，路牌的作用就更加显著了。
好！说了那么多，接下来给大家代码吧，相信大家听懂这个故事以后，代码完全可以自己敲一下了，建议大家自己敲，这样可以发现一些问题（记得统计最后结果的时候开long long）谢谢大家阅读。
#include<iostream>
using namespace std;
char ch;
template<class T>
inline void rd(T& x) {//快读不解释了哈
x = 0; int w = 1;
ch = getchar();
while (ch < '0' || ch>'9') {
if (ch == '-')w = -1; ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + ch - '0';
ch = getchar();
}
x = x * w;
}
int a[100001]; unsigned long long t ,sum;
int main()
{
int n, m,x,y,z;
rd(n), rd(m);
rd(x);
for (int i = 2; i <= m; i++)
{
rd(y);//这个循环是安装路牌的过程
if (x < y)
{
a[x]++;
a[y]--;
}
else
{
a[x]--;
a[y]++;
}
x = y;
}
for (int i = 1; i < n; i++)
{
t += a[i];
rd(x),rd(y),rd(z);
sum += t * y + z < t * x ? t * y + z : t * x; //这一块决定是不是买卡
}
cout << sum;
return 0;
}