2018.07.29~30 uoj#170. Picks loves segment tree VIII（线段树）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

flowchart 箭头图标勿删

传送门

线段树好题。

维护区间取两种最值，区间加，求区间两种历史最值，区间最小值。

自己的写法调了一个晚上+一个上午+一个下午+一个晚上并没有调出来，90" role="presentation" style="position: relative;">9090分弃疗。

于是我开始学习新的写法。

也就是封装再封装。

然后发现自己的方法的确有不严谨的地方，但并不好改，于是写了一个凌晨参考了xuyixuan" role="presentation" style="position: relative;">xuyixuanxuyixuan神犇的写法调过了这题。

实际上就是我们对区间标记，区间最大值，区间最小值分别用三类结构体表示（顺便来个重载运算符）。然后就到了本蒟蒻出锅的地方：区间标记需要维护三类数的（我只维护了两类），最大值的，最小值的，既不是最大值也不是最小值的（这一项我并没有维护然后gg" role="presentation" style="position: relative;">gggg），然后分个类什么的再结合下面几道经典线段树应该就能做出来这道题了。

uoj#169. 【UR #11】元旦老人与数列

uoj#164. 【清华集训2015】V

bzoj3064: Tyvj 1518 CPU监控

bzoj4695: 最假女选手

hdu5306Gorgeous Sequence

代码：

#include<bits/stdc++.h>
#define lc (p<<1)
#define rc (p<<1|1)
#define mid (T[p].l+T[p].r>>1)
#define N 500005
#define inf 2e9
using namespace std;
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
inline int read(){
    int ans=0,w=1;
    char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
    while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
    return ans*w;
}
int n,m,a[N];
struct tag{int add,addmx,addmn;};
struct Max{int his,mx,sx;}mxtmp;
struct Min{int his,mn,sn;}mntmp;
struct Node{int l,r;Max mx;Min mn;tag Amax,Bmid,Cmin;}T[N<<2];
inline tag operator+(tag a,tag b){return (tag){a.add+b.add,max(a.addmx,b.addmx+a.add),min(a.addmn,b.addmn+a.add)};}
inline tag operator+(tag a,int b){return (tag){a.add+b,max(a.addmx,a.add+b),min(a.addmn,a.add+b)};}
inline Max operator+(Max a,Max b){return (Max){max(a.his,b.his),max(a.mx,b.mx),a.mx==b.mx?max(a.sx,b.sx):(a.mx<b.mx?max(a.mx,b.sx):max(a.sx,b.mx))};}
inline Min operator+(Min a,Min b){return (Min){min(a.his,b.his),min(a.mn,b.mn),a.mn==b.mn?min(a.sn,b.sn):(a.mn>b.mn?min(a.mn,b.sn):min(a.sn,b.mn))};}
inline void pushup(int p){T[p].mn=T[lc].mn+T[rc].mn,T[p].mx=T[lc].mx+T[rc].mx;}
inline void build(int p,int l,int r){
    T[p].l=l,T[p].r=r,T[p].Amax=T[p].Bmid=T[p].Cmin=(tag){0,0,0};
    if(l==r){T[p].mn=(Min){a[l],a[l],inf},T[p].mx=(Max){a[l],a[l],-inf};return;}
    build(lc,l,mid),build(rc,mid+1,r),pushup(p);
}
inline void pushadd(int p,int v){
    T[p].mx.mx+=v,T[p].mn.mn+=v;
    if(T[p].mx.sx!=-inf)T[p].mx.sx+=v;
    if(T[p].mn.sn!=inf)T[p].mn.sn+=v;
    T[p].mx.his=max(T[p].mx.his,T[p].mx.mx),T[p].mn.his=min(T[p].mn.his,T[p].mn.mn);
    T[p].Amax=T[p].Amax+v,T[p].Bmid=T[p].Bmid+v,T[p].Cmin=T[p].Cmin+v;
}
inline void pushAmax(int p,tag v){
    T[p].mx.his=max(T[p].mx.his,v.addmx+T[p].mx.mx);
    if(mxtmp.mx==mntmp.sn)T[p].mn.sn+=v.add;
    T[p].mx.mx+=v.add;
    T[p].Amax=T[p].Amax+v;
}
inline void pushBmid(int p,tag v){
    if(mxtmp.mx!=mntmp.sn&&mntmp.sn!=inf)T[p].mn.sn+=v.add;
    if(mntmp.mn!=mxtmp.sx&&mxtmp.sx!=-inf)T[p].mx.sx+=v.add;
    T[p].Bmid=T[p].Bmid+v;
}
inline void pushCmin(int p,tag v){
    T[p].mn.his=min(T[p].mn.his,v.addmn+T[p].mn.mn);
    if(mntmp.mn==mxtmp.sx)T[p].mx.sx+=v.add;
    T[p].mn.mn+=v.add;
    T[p].Cmin=T[p].Cmin+v;
}
inline void pushdown(int p){
    int chemn=min(T[lc].mn.mn,T[rc].mn.mn),chemx=max(T[lc].mx.mx,T[rc].mx.mx);
    mxtmp=T[lc].mx,mntmp=T[lc].mn;
    if(T[lc].mx.mx==chemx)pushAmax(lc,T[p].Amax);
    else if(T[lc].mx.mx==chemn)pushAmax(lc,T[p].Cmin);
    else pushAmax(lc,T[p].Bmid);
    pushBmid(lc,T[p].Bmid);
    if(T[lc].mn.mn==chemn)pushCmin(lc,T[p].Cmin);
    else if(T[lc].mn.mn==chemx)pushCmin(lc,T[p].Amax);
    else pushCmin(lc,T[p].Bmid);
    mxtmp=T[rc].mx,mntmp=T[rc].mn;
    if(T[rc].mx.mx==chemx)pushAmax(rc,T[p].Amax);
    else if(T[rc].mx.mx==chemn)pushAmax(rc,T[p].Cmin);
    else pushAmax(rc,T[p].Bmid);
    pushBmid(rc,T[p].Bmid);
    if(T[rc].mn.mn==chemn)pushCmin(rc,T[p].Cmin);
    else if(T[rc].mn.mn==chemx)pushCmin(rc,T[p].Amax);
    else pushCmin(rc,T[p].Bmid);
    T[p].Amax=T[p].Bmid=T[p].Cmin=(tag){0,0,0};
}
inline void update(int p,int ql,int qr,int v){
    if(ql>T[p].r||qr<T[p].l)return;
    if(ql<=T[p].l&&T[p].r<=qr)return pushadd(p,v);
    pushdown(p);
    if(qr<=mid)update(lc,ql,qr,v);
    else if(ql>mid)update(rc,ql,qr,v);
    else update(lc,ql,mid,v),update(rc,mid+1,qr,v);
    pushup(p);
}
inline void updmax(int p,int ql,int qr,int v){
    if(ql>T[p].r||qr<T[p].l||T[p].mx.mx<=v)return;
    if(ql<=T[p].l&&T[p].r<=qr&&T[p].mx.sx<v){
        mxtmp=T[p].mx,mntmp=T[p].mn;
        if(T[p].mx.mx==T[p].mn.mn)pushCmin(p,(tag){v-T[p].mx.mx,v-T[p].mx.mx,0});
        return pushAmax(p,(tag){v-T[p].mx.mx,v-T[p].mx.mx,0});
    }
    pushdown(p);
    if(qr<=mid)updmax(lc,ql,qr,v);
    else if(ql>mid)updmax(rc,ql,qr,v);
    else updmax(lc,ql,mid,v),updmax(rc,mid+1,qr,v);
    pushup(p);
}
inline void updmin(int p,int ql,int qr,int v){
    if(ql>T[p].r||qr<T[p].l||T[p].mn.mn>=v)return;
    if(ql<=T[p].l&&T[p].r<=qr&&T[p].mn.sn>v){
        mxtmp=T[p].mx,mntmp=T[p].mn;
        if(T[p].mx.mx==T[p].mn.mn)pushAmax(p,(tag){v-T[p].mn.mn,0,v-T[p].mn.mn});
        return pushCmin(p,(tag){v-T[p].mn.mn,0,v-T[p].mn.mn});
    }
    pushdown(p);
    if(qr<=mid)updmin(lc,ql,qr,v);
    else if(ql>mid)updmin(rc,ql,qr,v);
    else updmin(lc,ql,mid,v),updmin(rc,mid+1,qr,v);
    pushup(p);
}
inline int query(int p,int ql,int qr){
    if(ql>T[p].r||qr<T[p].l)return inf;
    if(ql<=T[p].l&&T[p].r<=qr)return T[p].mn.mn;
    pushdown(p);
    if(qr<=mid)return query(lc,ql,qr);
    if(ql>mid)return query(rc,ql,qr);
    return min(query(lc,ql,mid),query(rc,mid+1,qr));
}
inline int querymn(int p,int ql,int qr){
    if(ql>T[p].r||qr<T[p].l)return inf;
    if(ql<=T[p].l&&T[p].r<=qr)return T[p].mn.his;
    pushdown(p);
    if(qr<=mid)return querymn(lc,ql,qr);
    if(ql>mid)return querymn(rc,ql,qr);
    return min(querymn(lc,ql,mid),querymn(rc,mid+1,qr));
}
inline int querymx(int p,int ql,int qr){
    if(ql>T[p].r||qr<T[p].l)return -inf;
    if(ql<=T[p].l&&T[p].r<=qr)return T[p].mx.his;
    pushdown(p);
    if(qr<=mid)return querymx(lc,ql,qr);
    if(ql>mid)return querymx(rc,ql,qr);
    return max(querymx(lc,ql,mid),querymx(rc,mid+1,qr));
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;++i)a[i]=read();
    build(1,1,n);
    while(m--){
        int op=read(),l=read(),r=read();
        if(op==1){int v=read();update(1,l,r,v);}
        if(op==2){int v=read();updmin(1,l,r,v);}
        if(op==3)printf("%d\n",query(1,l,r));
        if(op==4)printf("%d\n",querymn(1,l,r));
        if(op==5){int v=read();updmax(1,l,r,v);}
        if(op==6)printf("%d\n",querymx(1,l,r));
    }
    return 0;
}