UOJ 164 清华集训2015 V

Problem

UOJ
要求你支持五个操作

• 1.区间加x
• 2.区间减x，然后对区间做ai=max(ai,0)$a_i=max(a_i,0)$的操作
• 3.区间修改成x
• 4.单点询问当前值
• 5.单点询问历史最大值

Solution

吉司机线段树的一道题，可以参见2016年吉如一的论文

我们用线段树维护两个东西，一个是当前，一个是历史，每个用结构体来描述，(x,y)表示值x对y取max。加号的意思表示合并两个操作，也就是当前的值与修改的参数，显然当前值就会变为x+t.x，但要注意的是当前的取最大操作也要修改为y+t.x再与t.y合并。这样方便我们对修改操作进行合并，就不需要zz地写3个update了。。

Code

#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn=500010;
const ll INF=1e18;
int n,m;
inline ll max(ll x,ll y){return x>y?x:y;}
template <typename Tp> inline void read(Tp &x)
{
    x=0;int f=0;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-') f=1,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    if(f) x=-x;
}
struct data{
    ll x,y;
    data(){}
    data(ll _x,ll _y){x=_x;y=_y;}
    data operator + (const data t)const
    {
        return data(max(x+t.x,-INF),max(y+t.x,t.y));
    }
}now[maxn<<2],his[maxn<<2];
data max(data a,data b){return data(max(a.x,b.x),max(a.y,b.y));}
void pushdown(int rt)
{
    his[rt<<1]=max(now[rt<<1]+his[rt],his[rt<<1]);
    now[rt<<1]=now[rt<<1]+now[rt];
    his[rt<<1|1]=max(now[rt<<1|1]+his[rt],his[rt<<1|1]);
    now[rt<<1|1]=now[rt<<1|1]+now[rt];
    now[rt]=his[rt]=data(0,0);
}
void build(int l,int r,int rt)
{
    if(l==r){read(now[rt].x);return ;}
    int m=(l+r)>>1;
    build(l,m,rt<<1);
    build(m+1,r,rt<<1|1);
}
void update(int l,int r,int L,int R,data v,int rt)
{
    if(L<=l&&r<=R){now[rt]=now[rt]+v;his[rt]=max(his[rt],now[rt]);return ;}
    pushdown(rt);
    int m=(l+r)>>1;
    if(L<=m) update(l,m,L,R,v,rt<<1);
    if(m<R) update(m+1,r,L,R,v,rt<<1|1);
}
ll query(int l,int r,int pos,int op,int rt)
{
    if(l==r) return op?max(now[rt].x,now[rt].y):max(his[rt].x,his[rt].y);
    pushdown(rt);
    int m=(l+r)>>1;
    if(pos<=m) return query(l,m,pos,op,rt<<1);
    else return query(m+1,r,pos,op,rt<<1|1);
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif
    int op,l,r,x;
    read(n);read(m);
    build(1,n,1);
    while(m--)
    {
        read(op);
        if(op<=3) read(l),read(r),read(x);
        else read(l);
        if(op==1) update(1,n,l,r,data(x,-INF),1);
        else if(op==2) update(1,n,l,r,data(-x,0),1);
        else if(op==3) update(1,n,l,r,data(-INF,x),1);
        else printf("%lld\n",query(1,n,l,op==4,1));
    }
    return 0;
}