P3406 海底高铁

题目链接https://www.luogu.com.cn/problem/P3406

【解题思路】前缀和、查分

对于其中一小段，我们要么全部买纸票，要么全部刷卡。

所以我们只需要统计每一小段经过的总次数。

如果你暴力模拟统计的话，估计会tle。

怎么快速知道每一段次数呢？

我们回忆一下“借教室”这道题。

如果你高兴的话，可以上线段树或者树装数组——但是没必要。

假设有5段，我们把1到3加上1，可以像图2一样，开头+1，结尾-1。然后2到4加1，如图3.

                  +1      -1          +1 +1   -1 -1
 - - - - -        --  - - -- -        -- -- - -- --
 1 2 3 4 5        1   2 3 4  5        1  2  3 4  5
 图1              图2                 图3

然后呢，我们求出每一项前缀和（就是从前往后加）：

1 2 2 1 0
- - - - -
1 2 3 4 5
图4

然后每一段直接贪心比较，然后就有如下代码了。

#include<bits/stdc++.h>
using namespace std;
int n, m;
int p[100005];
int cf[100005];
int a, b, c;
long long ans, sum;
int main()
{
    cin>>n>>m;
    for(int i=0; i<m; i++)
        cin>>p[i];
    for(int i=1; i<m; i++){
        int l=p[i-1], r=p[i];
        if(l>r)swap(l, r);
        //cout<<l<<"-"<<r<<endl;
        cf[l]+=1; cf[r]-=1;
    }
    for(int i=1; i<n; i++){
        sum+=cf[i];
        cin>>a>>b>>c;
        ans+=min(b*sum+c, a*sum);
    }
    cout<<ans;
    return 0;
}