历史最值问题入门
链接
题解
注意,一定要把INF设够,要不然会调一个世纪都调不出来。
- 用线段树。
- 考虑没有历史最值,显然两个tag足矣。(P1,P2)表示先加P1,再对P2取max。
- 我们发现tag表示出了一个分段函数f(x),表示初值为x的情况下经过这一系列变换终值为f(x)。
- 考虑历史最值。我们发现这个tag也可以用上面的函数表示(因为每次相当于把以前的分段函数和现在的分段函数取个max,而上述的分段函数取max之后可以证明仍可以表现成该形式。)
代码
#include<bits/stdc++.h>
#define LL long long
#define MAXN 501000
#define INF 1000000000000000ll
using namespace std;
template<typename T> void Read(T &cn)
{
char c; int sig = 1;
while(!isdigit(c = getchar())) if(c == '-') sig = 0;
if(sig) {cn = c-48; while(isdigit(c = getchar())) cn = cn*10+c-48; }
else {cn = 48-c; while(isdigit(c = getchar())) cn = cn*10+48-c; }
}
template<typename T> void Write(T cn)
{
int wei = 0; T cm = 0; int cx = cn%10; cn/=10;
if(cn < 0 || cx < 0) {putchar('-'); cn = 0-cn; cx = 0-cx; }
while(cn)cm = cm*10+cn%10,cn/=10,wei++;
while(wei--)putchar(cm%10+48),cm/=10;
putchar(cx+48);
}
template<typename T> void WriteL(T cn) {Write(cn); puts(""); }
template<typename T> void WriteS(T cn) {Write(cn); putchar(' '); }
template<typename T> void Max(T &cn, T cm) {cn = cn < cm ? cm : cn; }
template<typename T> void Min(T &cn, T cm) {cn = cn < cm ? cn : cm; }
struct Seg{
struct tag{
LL jia, da;
void mk(LL cn, LL cm) {jia = cn; da = cm; }
void bing_hst(tag cn) {Max(jia, cn.jia); Max(da, cn.da); Max(jia,-INF);Max(da,-INF); Min(jia,INF);Min(da,INF); }
void bing(tag cn) {jia = jia+cn.jia; da = max(da+cn.jia, cn.da); Max(jia,-INF);Max(da,-INF); Min(jia,INF);Min(da,INF); }
void qing() {jia = 0; da = -INF; }
};
tag mk(LL cn, LL cm) {tag guo; guo.mk(cn,cm); return guo; }
struct node{
tag p[2];
void zeng(tag cn) {p[0].bing(cn); p[1].bing_hst(p[0]); }
void qing() {p[0].qing(); p[1].qing(); }
};
node t[MAXN*4+1];
int n;
LL a[MAXN+1];
void tui(int cn)
{
int ls = cn<<1, rs = ls+1;
tag lin;
lin = t[ls].p[0]; lin.bing(t[cn].p[1]);
t[ls].zeng(t[cn].p[0]); t[ls].p[1].bing_hst(lin);
lin = t[rs].p[0]; lin.bing(t[cn].p[1]);
t[rs].zeng(t[cn].p[0]); t[rs].p[1].bing_hst(lin);
t[cn].p[0].qing(); t[cn].p[1].qing();
}
void build(int cn, int l, int r)
{
t[cn].qing(); if(l == r) return;
int zh = (l+r)>>1; build(cn<<1,l,zh); build((cn<<1)|1,zh+1,r);
}
void gai(int cn, int cl, int cr, tag cx, int l, int r)
{
if(cl <= l && r <= cr) {t[cn].zeng(cx); return; }
int zh = (l+r)>>1; tui(cn);
if(cl <= zh) gai(cn<<1,cl,cr,cx,l,zh);
if(cr > zh) gai((cn<<1)|1,cl,cr,cx,zh+1,r);
}
tag qiu(int cn, int cm, int cx, int l, int r)
{
if(l == r) return t[cn].p[cx];
int zh = (l+r)>>1; tui(cn);
if(cm <= zh) return qiu(cn<<1,cm,cx,l,zh);
else return qiu((cn<<1)|1,cm,cx,zh+1,r);
}
void build(int cn, int ca[]) {n = cn; for(int i = 1;i<=n;i++) a[i] = ca[i]; build(1,1,n); }
void gai(int cl, int cr, LL cjia, LL cda) {gai(1,cl,cr,mk(cjia,cda),1,n); }
LL qiu(int cn, int cm) {tag ans = qiu(1,cn,cm,1,n); return max(a[cn]+ans.jia, ans.da); }
}T;
int n, q;
int a[MAXN+1];
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
Read(n); Read(q);
for(int i = 1;i<=n;i++) Read(a[i]);
T.build(n, a);
for(int i = 1;i<=q;i++)
{
int btyp, bl, br, bx;
Read(btyp);
if(btyp == 1) Read(bl), Read(br), Read(bx), T.gai(bl,br,bx,-INF);
if(btyp == 2) Read(bl), Read(br), Read(bx), T.gai(bl,br,-bx,0);
if(btyp == 3) Read(bl), Read(br), Read(bx), T.gai(bl,br,-INF,bx);
if(btyp == 4) Read(bx), WriteL(T.qiu(bx, 0));
if(btyp == 5) Read(bx), WriteL(T.qiu(bx, 1));
}
return 0;
}