海底高铁--差分

显着用差分·来统计坐每一段的次数

然后忘开ll喜提70，（；′д｀）ゞ

1. #include<bits/stdc++.h>
2. using namespace std;
3. typedef long long ll;
4. typedef pair<ll,int> PII;
5. int n,m;
6. ll an;
7. ll p[100011];
8. ll a[100011];
9. ll b[100011];
10. ll c[100011];
11. ll df[100011];
12. ll s[100011];
13. int main()
14. {
15. cin>>n>>m;
16. for(int i=0;i<m;i++)
17. {
18.         cin>>p[i];
19. }
20. for(int i=1;i<=n-1;i++) cin>>a[i]>>b[i]>>c[i];
21. for(int i=0;i<m-1;i++)
22. {
23.         int l=min(p[i],p[i+1]);
24.         int r=max(p[i],p[i+1]);
25.         df[r]--;
26.         df[l]++;
27. }
28. for(int i=1;i<=n-1;i++)
29. {
30.         s[i]=s[i-1]+df[i];
31.         //cout<<s[i]<<" ";
32. }
33. for(int i=1;i<=n-1;i++)
34. {
35.         if(a[i]*s[i]<c[i]+b[i]*s[i])
36.         {
37.                 an+=a[i]*s[i];
38.          }else an+=c[i]+b[i]*s[i];
39. }
40. cout<<an;
41. return 0;
42. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。