欢迎访问 如意编程网!

如意编程网

当前位置: 首页 > 编程资源 > 编程问答 >内容正文

编程问答

BZOJ3064 CPU监控

发布时间:2024/7/5 编程问答 2 豆豆
如意编程网 收集整理的这篇文章主要介绍了 BZOJ3064 CPU监控 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

题目链接:戳我

比较神仙的一个题(至少对于我这个小蒟蒻来说。。。)下面尽可能详细地解释一下吧。。。学习来源:这位神仙的题解

其实就是对于操作的转换。我们设(x,y)为操作的参数,设当前数为a,操作为max(a+x,y)——赋值即(-inf,b),增加为(a,-inf)。(是不是感觉很妙啊qwqwq)

如果标记(x2,y2)合并到(x1,y1)之后,应该是这个样子——(x1+x2,max(y1+x2,y2))。(根据合并顺序,应该不难理解)

代码如下:

Node2 operator + (struct Node2 a,struct Node2 b){return (Node2){max(-inf,a.x+b.x),max(a.y+b.x,b.y)};} Node2 max (struct Node2 a,struct Node2 b){return (Node2){max(a.x,b.x),max(a.y,b.y)};}

然后我们维护两个标记——一个叫tag,和普通线段树里面的lazy标记一样,正常维护现在的更改。一个叫tag2,维护历史操作。

先看核心的维护操作:
(本来solve是给push_down用的,但是其实update里面也是可以调用的。我们把a,b传参数的时候传一样的即可。)

inline void solve(int x,Node2 a,Node2 b) {//注意更新顺序不要反了,因为每次update的时候已经给tag和tag2都修改过了相一致的值//所以这里如果先更新now再更新历史值,显然会累加,重复计算。t[x].pre_max=max(t[x].pre_max,max(t[x].now_max+b.x,b.y));t[x].now_max=max(t[x].now_max+a.x,a.y);tag2[x]=max(tag2[x],tag[x]+b);//将b合并给tag,之后用这个去更新历史最大的标记tag[x]=tag[x]+a;//将a合并给tag }

然后我们来看push_down操作:

inline void push_down(int x) {solve(ls(x),tag[x],tag2[x]);solve(rs(x),tag[x],tag2[x]);//给做右区间分别下方当前标记,和历史标记tag[x].x=tag2[x].x=0;tag[x].y=tag2[x].y=-inf;//注意push_down之后对两个标记的还原(因为什么都没有加,所以x=0。//因为也不需要取最大,所以y=-inf }

完整代码如下:

#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #define inf 0x3f3f3f3f #define MAXN 100010 using namespace std; int n,m; int a[MAXN];struct Node{int l,r,now_max,pre_max;}t[MAXN<<2];struct Node2{int x,y;}tag[MAXN<<2],tag2[MAXN<<2];Node2 operator + (struct Node2 a,struct Node2 b){return (Node2){max(-inf,a.x+b.x),max(a.y+b.x,b.y)};}Node2 max (struct Node2 a,struct Node2 b){return (Node2){max(a.x,b.x),max(a.y,b.y)};}inline int ls(int x){return x<<1;}inline int rs(int x){return x<<1|1;}inline void push_up(int x) {t[x].now_max=max(t[ls(x)].now_max,t[rs(x)].now_max);t[x].pre_max=max(t[ls(x)].pre_max,t[rs(x)].pre_max); }inline void solve(int x,Node2 a,Node2 b) {t[x].pre_max=max(t[x].pre_max,max(t[x].now_max+b.x,b.y));t[x].now_max=max(t[x].now_max+a.x,a.y);tag2[x]=max(tag2[x],tag[x]+b);tag[x]=tag[x]+a; }inline void push_down(int x) {solve(ls(x),tag[x],tag2[x]);solve(rs(x),tag[x],tag2[x]);tag[x].x=tag2[x].x=0;tag[x].y=tag2[x].y=-inf; }inline void build(int x,int l,int r) {t[x].l=l,t[x].r=r;tag[x].x=tag2[x].x=0;tag[x].y=tag2[x].y=-inf;if(l==r){t[x].now_max=t[x].pre_max=a[l];return;}int mid=(l+r)>>1;build(ls(x),l,mid);build(rs(x),mid+1,r);push_up(x); }inline void update(int x,int ll,int rr,Node2 k) {int l=t[x].l,r=t[x].r;if(ll<=l&&r<=rr){solve(x,k,k);return;}int mid=(l+r)>>1;push_down(x);if(ll<=mid) update(ls(x),ll,rr,k);if(mid<rr) update(rs(x),ll,rr,k);push_up(x); }inline int query(int x,int ll,int rr,int op) {int l=t[x].l,r=t[x].r;if(ll<=l&&r<=rr){if(op==0) return t[x].now_max;else return t[x].pre_max;}int mid=(l+r)>>1,cur_ans=-inf;push_down(x);if(ll<=mid) cur_ans=max(cur_ans,query(ls(x),ll,rr,op));if(mid<rr) cur_ans=max(cur_ans,query(rs(x),ll,rr,op));return cur_ans; }int main() {#ifndef ONLINE_JUDGEfreopen("ce.in","r",stdin);freopen("ce.out","w",stdout);#endifscanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);scanf("%d",&m);build(1,1,n);for(int i=1;i<=m;i++){char s[10];int l,r,k;Node2 cur; scanf("%s%d%d",s,&l,&r);if(s[0]=='Q') printf("%d\n",query(1,l,r,0));else if(s[0]=='A') printf("%d\n",query(1,l,r,1));else if(s[0]=='P') {scanf("%d",&k);cur.x=k,cur.y=-inf;update(1,l,r,cur);}else if(s[0]=='C'){scanf("%d",&k);cur.x=-inf,cur.y=k;update(1,l,r,cur);}}return 0; }

转载于:https://www.cnblogs.com/fengxunling/p/10508486.html

创作挑战赛新人创作奖励来咯,坚持创作打卡瓜分现金大奖

总结

以上是如意编程网为你收集整理的BZOJ3064 CPU监控的全部内容,希望文章能够帮你解决所遇到的问题。

如果觉得如意编程网网站内容还不错,欢迎将如意编程网推荐给好友。