企业网站策划大纲模板,网站设计ppt案例,网站制作网站价格,徐州专业做网站BZOJ #3064. Tyvj 1518 CPU监控(线段树#xff0c;历史最值)
Solution
我们考虑用线段树维护此题。
先不考虑历史最值。
大概需要维护一种特殊的懒标记(x,y)(x,y)(x,y)表示让区间内所有数ppp#xff0c;pmax(px,y)pmax(px,y)pmax(px,y)。
对于区间加zzz#xff0c;打一…BZOJ #3064. Tyvj 1518 CPU监控(线段树历史最值)
Solution
我们考虑用线段树维护此题。
先不考虑历史最值。
大概需要维护一种特殊的懒标记(x,y)(x,y)(x,y)表示让区间内所有数ppppmax(px,y)pmax(px,y)pmax(px,y)。
对于区间加zzz打一个(z,−∞)(z,-\infty)(z,−∞)的标记即可。 对于区间覆盖zzz打一个(−∞,z)(-\infty,z)(−∞,z)的标记即可。
把标记(a,b)(a,b)(a,b)合并到(c,d)(c,d)(c,d)时只需要让c′ac,d′max(da,b)cac,dmax(da,b)c′ac,d′max(da,b)即可。 剩下的就是一个线段树维护区间最大值。
现在加上了历史最值我们要多记录一个区间历史最大值和历史最大值的标记该标记表示从上一次下传到当前时刻的所有修改中标记的最大贡献注意这里的标记是有序合并的。这相当于一个分段函数最值对于标记(a,b)(a,b)(a,b)(c,d)(c,d)(c,d)不难发现其最大可以取到(max(a,c),max(b,d))(max(a,c),max(b,d))(max(a,c),max(b,d))。
于是按上面的方法维护即可。
时间复杂度O(nlgn)O(nlgn)O(nlgn)。
需要注意infinfinf的取值很多标记合并可能会爆intintint太小可能减不完。
Code
#include vector
#include list
#include map
#include set
#include deque
#include queue
#include stack
#include bitset
#include algorithm
#include functional
#include numeric
#include utility
#include sstream
#include iostream
#include iomanip
#include cstdio
#include cmath
#include cstdlib
#include cctype
#include string
#include cstring
#include ctime
#include cassert
#include string.h
//#include unordered_set
//#include unordered_map
//#include bits/stdc.h#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i(a);i(b);i)
#define fi first
#define se secondusing namespace std;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods998244353;
const int MAXN100005;
const int INF0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }return x*f;
}
struct Node
{ll x,y;Node(){}Node(ll x,ll y):x(x),y(y){}friend Node operator (Node a,Node b) { return Node(a.xb.x,max(b.xa.y,b.y)); }friend Node operator * (Node a,Node b) { return Node(max(a.x,b.x),max(a.y,b.y)); }
} ntag[MAXN2],ptag[MAXN2];
ll nmx[MAXN2],pmx[MAXN2],a[MAXN];void up(int x)
{nmx[x]max(nmx[x1],nmx[x1|1]);pmx[x]max(pmx[x1],pmx[x1|1]);
}
void build(int x,int l,int r)
{ntag[x]ptag[x]Node(0,-INF);if (lr) { nmx[x]pmx[x]a[l]; return; }int mid(lr)1;build(x1,l,mid);build(x1|1,mid1,r);up(x);
}
void down(int x)
{int lsx1,rsx1|1;ptag[ls]ptag[ls]*(ntag[ls]ptag[x]);ptag[rs]ptag[rs]*(ntag[rs]ptag[x]);ntag[ls]ntag[ls]ntag[x];ntag[rs]ntag[rs]ntag[x];pmx[ls]max(pmx[ls],max(nmx[ls]ptag[x].x,ptag[x].y));pmx[rs]max(pmx[rs],max(nmx[rs]ptag[x].x,ptag[x].y));nmx[ls]max(nmx[ls]ntag[x].x,ntag[x].y);nmx[rs]max(nmx[rs]ntag[x].x,ntag[x].y);ntag[x]ptag[x]Node(0,-INF);
}
void update(int x,int l,int r,int L,int R,Node y)
{if (lLrR){ntag[x]ntag[x]y;ptag[x]ptag[x]*ntag[x];nmx[x]max(nmx[x]y.x,y.y);pmx[x]max(pmx[x],nmx[x]);return;}down(x);int mid(lr)1;if (Rmid) update(x1,l,mid,L,R,y);else if (Lmid) update(x1|1,mid1,r,L,R,y);else update(x1,l,mid,L,mid,y),update(x1|1,mid1,r,mid1,R,y);up(x);
}
ll query(int x,int l,int r,int L,int R,int opt)
{if (lLrR) return opt?pmx[x]:nmx[x];down(x);int mid(lr)1;if (Rmid) return query(x1,l,mid,L,R,opt);else if (Lmid) return query(x1|1,mid1,r,L,R,opt);else return max(query(x1,l,mid,L,mid,opt),query(x1|1,mid1,r,mid1,R,opt));
}
signed main()
{int nread();for (int i1;in;i) a[i]read();build(1,1,n);int Caseread();while (Case--){char st[5]; scanf(%s,st);int xread(),yread(),z;if (st[0]Q) printf(%lld\n,query(1,1,n,x,y,0));if (st[0]A) printf(%lld\n,query(1,1,n,x,y,1));if (st[0]P) zread(),update(1,1,n,x,y,Node(z,-INF));if (st[0]C) zread(),update(1,1,n,x,y,Node(-INF,z)); }return 0;
}
