东莞品牌网站建设,中国建设银行官方网站纪念币,上海网站制作电话,织梦仿Wordpress分页题目链接#xff1a;戳我 比较神仙的一个题#xff08;至少对于我这个小蒟蒻来说。。。#xff09;下面尽可能详细地解释一下吧。。。学习来源#xff1a;这位神仙的题解 其实就是对于操作的转换。我们设(x,y)为操作的参数#xff0c;设当前数为a#xff0c;操作为max(ax… 题目链接戳我 比较神仙的一个题至少对于我这个小蒟蒻来说。。。下面尽可能详细地解释一下吧。。。学习来源这位神仙的题解 其实就是对于操作的转换。我们设(x,y)为操作的参数设当前数为a操作为max(ax,y)——赋值即(-inf,b)增加为(a,-inf)。(是不是感觉很妙啊qwqwq 如果标记(x2,y2)合并到(x1,y1)之后应该是这个样子——(x1x2,max(y1x2,y2))。根据合并顺序应该不难理解 代码如下 Node2 operator (struct Node2 a,struct Node2 b){return (Node2){max(-inf,a.xb.x),max(a.yb.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_maxmax(t[x].pre_max,max(t[x].now_maxb.x,b.y));t[x].now_maxmax(t[x].now_maxa.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].xtag2[x].x0;tag[x].ytag2[x].y-inf;//注意push_down之后对两个标记的还原(因为什么都没有加所以x0。//因为也不需要取最大所以y-inf
} 完整代码如下 #includeiostream
#includecstring
#includecstdio
#includealgorithm
#includecmath
#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[MAXN2];struct Node2{int x,y;}tag[MAXN2],tag2[MAXN2];Node2 operator (struct Node2 a,struct Node2 b){return (Node2){max(-inf,a.xb.x),max(a.yb.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 x1;}inline int rs(int x){return x1|1;}inline void push_up(int x)
{t[x].now_maxmax(t[ls(x)].now_max,t[rs(x)].now_max);t[x].pre_maxmax(t[ls(x)].pre_max,t[rs(x)].pre_max);
}inline void solve(int x,Node2 a,Node2 b)
{t[x].pre_maxmax(t[x].pre_max,max(t[x].now_maxb.x,b.y));t[x].now_maxmax(t[x].now_maxa.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].xtag2[x].x0;tag[x].ytag2[x].y-inf;
}inline void build(int x,int l,int r)
{t[x].ll,t[x].rr;tag[x].xtag2[x].x0;tag[x].ytag2[x].y-inf;if(lr){t[x].now_maxt[x].pre_maxa[l];return;}int mid(lr)1;build(ls(x),l,mid);build(rs(x),mid1,r);push_up(x);
}inline void update(int x,int ll,int rr,Node2 k)
{int lt[x].l,rt[x].r;if(lllrrr){solve(x,k,k);return;}int mid(lr)1;push_down(x);if(llmid) update(ls(x),ll,rr,k);if(midrr) update(rs(x),ll,rr,k);push_up(x);
}inline int query(int x,int ll,int rr,int op)
{int lt[x].l,rt[x].r;if(lllrrr){if(op0) return t[x].now_max;else return t[x].pre_max;}int mid(lr)1,cur_ans-inf;push_down(x);if(llmid) cur_ansmax(cur_ans,query(ls(x),ll,rr,op));if(midrr) cur_ansmax(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 i1;in;i) scanf(%d,a[i]);scanf(%d,m);build(1,1,n);for(int i1;im;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.xk,cur.y-inf;update(1,l,r,cur);}else if(s[0]C){scanf(%d,k);cur.x-inf,cur.yk;update(1,l,r,cur);}}return 0;
} 转载于:https://www.cnblogs.com/fengxunling/p/10508486.html
