宝和网站建设,做项目的编程网站,做网站后端的是什么部门,资源网站平台建设方案解析
本题说明了样例的重要性 完全可以通过仔细观察样例得出一些结论
首先最大值显然就是max(b1,cn)\max(b_1,c_n)max(b1,cn) 考虑最优策略 如果a上升了#xff0c;就让b上升 因为假设前面都拼的严丝合缝了#xff0c;让c上升前面全得上升#xff0c;肯定会对答案有…解析
本题说明了样例的重要性 完全可以通过仔细观察样例得出一些结论
首先最大值显然就是max(b1,cn)\max(b_1,c_n)max(b1,cn) 考虑最优策略 如果a上升了就让b上升 因为假设前面都拼的严丝合缝了让c上升前面全得上升肯定会对答案有影响而修改b则不一定
如果a下降了就让c下降 类似的原因如果让b下降就会影响到b1那么b1小了c1就会大对答案产生影响
想到这些后面维护差分就较为简单了
代码
#includebits/stdc.h
using namespace std;
const int N3e5100;
const int mod1e97;
double eps1e-10;
#define ll long long
ll read(){ll x0,f1;char cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();};while(isdigit(c)){xx*10c-0;cgetchar();};return x*f;
}int n,m;ll d[N],a[N];
ll res;
int main(){#ifndef ONLINE_JUDGE//freopen(a.in,r,stdin);//freopen(a.out,w,stdout);#endifnread();for(int i1;in;i){a[i]read();d[i]a[i]-a[i-1];if(i1) resmax(0ll,d[i]);//printf(i%d res%lld\n,i,res);}resa[1];printf(%lld\n,(res(res0))/2);mread();for(int i1;im;i){int lread(),rread(),xread();if(l1) res-d[l];else res-max(0ll,d[l]);d[l]x;if(l1) resd[l];else resmax(0ll,d[l]);//printf(d%lld res%lld\n,d[l],res);if(rn){res-max(0ll,d[r1]);d[r1]-x;resmax(0ll,d[r1]);}printf(%lld\n,(res(res0))/2);}return 0;
}
/*
2 3
7 4 9 9
1 2 8
3 1
4 2 4
*/
