欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

UOJ 164 清华集训2015 V

程序员文章站 2022-06-12 16:23:21
...

Problem

UOJ
要求你支持五个操作

  • 1.区间加x
  • 2.区间减x,然后对区间做ai=max(ai,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;
}
相关标签: 吉司机线段树