传送门

题意:维护一个数列$a_1...a_n$,有以下5种操作:

  1. $a_l..a_r=a_l..a_r +x$
  2. $a_l..a_r=max(a_l..a_r-x,0)$
  3. $a_l..a_r=x$
  4. 查询$a_x$
  5. 查询$a_x$的历史最大值

题解:
初看时很容易想到线段树。但是有三个操作$+x$,$-x$并对0取$max$,和赋值,好像不是很好维护标记。

我们可以用一个二元组$(a,b)$表示一个标记,意思是将x变为$\max(x+a,b)$。
那么前三个操作就变成了分别给$l..r$打上$(x,0)$,$(-x,0)$,$(-\infty,x)$的标记,开始的赋初值也可以转化为一个标记。
下传标记时要注意先后次序。

标记下传形如:

$$(a,b)+(c,d)=(a+c,\max(b+c,d))$$

注意$(a,b)$是原来的标记。

事实上真正代码中应该是$(a,b)+(c,d)=(\max(a+c,-\infty),\max(b+c,d))$

因为有可能两个甚至三个tag都是形如$(-\infty,x)$,或者是在$(-\infty,x)$的基础上再上一些$(-x,0)$的tag,所以为了避免得到的$a+c < -\infty$甚至爆long long 变为大正数,再代码中应该这么写。

最后查询的时候一路下传标记。最后叶子节点上的tag设为$(a,b)$,则答案为$\max(a,b)$

这样就可以维护1,2,3,4操作了。

对于操作5,要求维护历史最大值。

那么我们就在放标记、下传标记的时候维护一下$a$的最大值和$b$的最大值(同样记作$(a,b)$)。

对于下传时维护最大值,因为可能一个节点上存了多个标记合并以后的标记,所以不能单纯下传后维护最大值。设双亲节点中存的最大值为$(a,b)$,孩子节点中当前的标记为$(c,d)$,则孩子节点中的最大值变为$(c+a,\max(d+a,b))$

每次下传以后需要把标记和维护的最大值清空。

代码:

/*
Author: CNYALI_LK
LANG: C++
PROG: uoj164.cpp
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define all(x) x.begin(),x.end()
#define end(...) {printf(__VA_ARGS__);exit(0);}
using namespace std;
const double eps=1e-8;
const double PI=acos(-1.0);
typedef long long ll;
template<class T>void chkmin(T &a,T b){a=a<b?a:b;}
template<class T>void chkmax(T &a,T b){a=a>b?a:b;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
typedef pair<ll,ll> pii;
#define x first
#define y second
#define mp make_pair
const ll ind=-0x3f3f3f3f3f3f3f3f;
namespace seg{
    pii tag[2333333],lmt[2333333];  
    void cmx(pii &a,pii b){
        chkmax(a.x,b.x);
        chkmax(a.y,b.y);
    }
    void at(pii &a,pii b){
        a.x=max(a.x+b.x,ind);
        a.y=max(a.y+b.x,b.y);
    }
    void push_down(ll x){
        pii s=tag[x<<1];
        at(s,lmt[x]);
        cmx(lmt[x<<1],s);
        s=tag[x<<1|1];
        at(s,lmt[x]);
        cmx(lmt[x<<1|1],s);
        at(tag[x<<1],tag[x]);
        at(tag[x<<1|1],tag[x]);
        tag[x]=lmt[x]=mp(0,0);
    }
#define mid ((l+r)>>1)
    void atg(ll x,ll l,ll r,ll lx,ll rx,pii tg){
        if(l!=r)push_down(x);
        if(lx<=l&&r<=rx){
            at(tag[x],tg);
            cmx(lmt[x],tag[x]);
            return;
        }
        if(lx<=mid)atg(x<<1,l,mid,lx,rx,tg);
        if(mid<rx)atg(x<<1|1,mid+1,r,lx,rx,tg);
    }
    ll query(ll x,ll l,ll r,ll t){
        while(l<r){
            push_down(x);
            if(t<=mid){r=mid;x<<=1;}
            else {l=mid+1;x=x<<1|1;}
        }
        return max(tag[x].x,tag[x].y);
    }
    ll lquery(ll x,ll l,ll r,ll t){
        while(l<r){
            push_down(x);
            if(t<=mid){r=mid;x<<=1;}
            else {l=mid+1;x=x<<1|1;}
        }
        return max(lmt[x].x,lmt[x].y);
    }
}
int main(){
#ifdef cnyali_lk
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    ll n,m,t,l,r,x;
    scanf("%lld%lld",&n,&m);
    for(ll i=1;i<=n;++i){
        scanf("%lld",&x);
        seg::atg(1,1,n,i,i,mp(x,0));

    }

    while(m){
        --m;
        scanf("%lld",&t);
        if(t==1){
            scanf("%lld%lld%lld",&l,&r,&x);
            seg::atg(1,1,n,l,r,mp(x,0));
        }
        else if(t==2){
            scanf("%lld%lld%lld",&l,&r,&x);
            seg::atg(1,1,n,l,r,mp(-x,0));
        }
        else if(t==3){
            scanf("%lld%lld%lld",&l,&r,&x);
            seg::atg(1,1,n,l,r,mp(ind,x));
        }
        else if(t==4){
            scanf("%lld",&x);
            printf("%lld\n",seg::query(1,1,n,x));
        }
        else{
            scanf("%lld",&x);
            printf("%lld\n",seg::lquery(1,1,n,x));
        }
    }
    return 0;
}

标签: 线段树

添加新评论