1 solutions
-
1
本人洛谷原题解:> https://www.luogu.com.cn/article/b463xc3v
部分分:
对于 Subtask :直接暴力即可。
对于 Subtask : 即为答案。
正解思路:
本题频繁性对区间操作,很自然地我们会想到差分。
不过这题用不用差分都差不多,只是用差分代码更简洁。由于最多有 天,所以计算每天的时间复杂度必须为 。我们可以想到:必须每次操作维护 ,而不是完全依赖于差分数组。
对于每次操作的区间起点和终点:
- 减去风改变的值。
- 修改差分数组。
- 加上现在风改变的值。
(如果终点小于 可以不用处理终点)
所以其实这里差分数组唯一作用就是用更简洁的语言代替 。
代码:
#include<iostream> #include<cstdio> using namespace std; const int NR=200010; int a[NR]; long long b[NR]; int main() { int n,q,s,t,i; cin>>n>>q>>s>>t; long long ans=0; for(i=0;i<=n;i++) { cin>>a[i]; if(i!=0) b[i]=a[i]-a[i-1]; if(i!=0 && a[i]>a[i-1]) ans+=b[i]*(-s); else if(i!=0 && a[i]<a[i-1]) ans+=-b[i]*t; } while(q--) { int l,r,x; cin>>l>>r>>x; if(b[l]>0) ans-=b[l]*(-s); else ans-=-b[l]*t; b[l]+=x; if(b[l]>0) ans+=b[l]*(-s); else ans+=-b[l]*t; if(r<n) { if(b[r+1]>0) ans-=b[r+1]*(-s); else ans-=-b[r+1]*t; b[r+1]-=x; if(b[r+1]>0) ans+=b[r+1]*(-s); else ans+=-b[r+1]*t; } cout<<ans<<endl; } return 0; }
注意事项:
在这里:
if(b[l]>0) ans-=b[l]*(-s); else ans-=-b[l]*t; b[l]+=x;
可能一开始为正(即 ),但后面可能让 变为负,所以 必须先减后加。
- 1
Information
- ID
- 11621
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 4
- Tags
- # Submissions
- 2
- Accepted
- 1
- Uploaded By