[学习笔记]Segment Tree Beats!九老师线段树

对于这样一类问题：

区间取min，区间求和。

N<=100000

要求O(nlogn)级别的算法

直观体会一下，区间取min，还要维护区间和

增加的长度很不好求。。。。

然鹅，

从前有一个来自杭州天水幼儿园的julao叫九条可怜

他发明了一个线段树的写法，

攻克了这个难题。

说起来很简单：

线段树维护区间最大值，区间严格次大值，和区间最大值出现次数

修改的时候，如果c大于mx，直接return

如果c小于mx而大于cmx，根据最大值的出现次数可以直接修改sum（注意必须是严格大于cmx，否则不能维护好严格次大值）

如果c小于等于cmx，那么暴力递归左右儿子，最终会用前两个更新，回溯来pushup一下

复杂度？

前两个O(1)就回溯了，不管。

第三个操作貌似有些暴力？

由于只有取max，所以

假如开始有O(N)个不同的值，那么每进行一次第三次操作，至少mx，和cmx要变得一样。值域减少1

那么，第三次操作最多进行O(n)次，每次均摊O(logn)

所以复杂度O(nlogn)

例题（以及一些具体操作）：

bzoj4695. 最假女选手

【bzoj4695】最假女选手

区间还要加？值域会改变，，，可以证明（就是说我不会证）复杂度是O(nlog^2n)

维护区间最大值，次大值，最大值出现次数，最小值同理。以及区间和，区间加标记

下放：

先下放区间加标记，现在儿子的情况大致和父亲一样了

区别在于，之前区间取min可能把最大值砍掉一些，但是没有在儿子中更新。

由于仅最大值小了一些，所以如果父亲的最大值在儿子的最大值和次大值之间，那么暴力再让儿子对父亲的最大值取个min（直接返回的，这个也是O(1)的）

第二种情况的更新时候：

可能造成最大值和最小值相同的情况，那么必然就是全部都相等了。特判一下，把次大值-inf，最大值inf（其实这个没有必要）

或者可能只有值域只有两个，那么次大值或者次小值也要尝试更新一下。其他值域的时候不影响。（这个必须有）

#include<bits/stdc++.h>
#define reg register int
#define il inline
#define mid ((l+r)>>1)
#define ls t[x].lson
#define rs t[x].rson
#define numb (ch^'0')
using namespace std;
typedef long long ll;
il void rd(int &x){
    char ch;x=0;bool fl=false;
    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
    for(x=numb;isdigit(ch=getchar());x=x*10+numb);
    (fl==true)&&(x=-x);
}
namespace Miracle{
const int N=6e5+5;
const int inf=0x3f3f3f3f;
int n,m;
int a[N];
struct node{

    int mx,cmx,tmx;
    int mi,cmi,tmi;
    ll sum;
    ll ad;
    int lson,rson;
}t[2*N];
int tot;
void pushup(int x){
    t[x].sum=t[ls].sum+t[rs].sum;
    if(t[ls].mx>t[rs].mx){
        t[x].mx=t[ls].mx,t[x].tmx=t[ls].tmx;t[x].cmx=max(t[ls].cmx,t[rs].mx);
    }else if(t[ls].mx<t[rs].mx){
        t[x].mx=t[rs].mx,t[x].tmx=t[rs].tmx;t[x].cmx=max(t[rs].cmx,t[ls].mx);
    }else{
        t[x].mx=t[ls].mx;t[x].tmx=t[ls].tmx+t[rs].tmx;t[x].cmx=max(t[rs].cmx,t[ls].cmx);
    }
    if(t[ls].mi<t[rs].mi){
        t[x].mi=t[ls].mi,t[x].tmi=t[ls].tmi;t[x].cmi=min(t[ls].cmi,t[rs].mi);
    }else if(t[ls].mi>t[rs].mi){
        t[x].mi=t[rs].mi,t[x].tmi=t[rs].tmi;t[x].cmi=min(t[rs].cmi,t[ls].mi);
    }else{
        t[x].mi=t[ls].mi;t[x].tmi=t[ls].tmi+t[rs].tmi;t[x].cmi=min(t[rs].cmi,t[ls].cmi);
    }
}
void addmax(int x,int l,int r,int c){//qu max
    t[x].sum+=(ll)t[x].tmi*(c-t[x].mi);
    t[x].mi=c;
    t[x].mx=max(t[x].mx,c);
    if(t[x].mi==t[x].mx){
        t[x].sum=((ll)r-l+1)*c;t[x].tmi=t[x].tmx=r-l+1;t[x].cmi=inf;t[x].cmx=-inf;
    }else t[x].cmx=max(t[x].cmx,c);
}
void addmin(int x,int l,int r,int c){
    t[x].sum+=(ll)t[x].tmx*(c-t[x].mx);
    t[x].mx=c;
    t[x].mi=min(t[x].mi,c);
    if(t[x].mi==t[x].mx){
        t[x].sum=((ll)r-l+1)*c;t[x].tmi=t[x].tmx=r-l+1;t[x].cmi=inf;t[x].cmx=-inf;
    }else t[x].cmi=min(t[x].cmi,c);
}
void build(int x,int l,int r){
    if(l==r){
        t[x].mx=t[x].mi=a[l];
        t[x].cmx=-inf;t[x].cmi=inf;
        t[x].tmx=t[x].tmi=1;
        t[x].sum=a[l];return;
    }
    ls=++tot;rs=++tot;
    build(ls,l,mid);build(rs,mid+1,r);
    pushup(x);
}
void getsum(int x,int l,int r,int c){
    t[x].ad+=c;t[x].sum+=(r-l+1)*c;
    t[x].mi+=c;t[x].cmi+=c;
    t[x].mx+=c;t[x].cmx+=c;
}
void pushdown(int x,int l,int r){
    if(t[x].ad){
        getsum(ls,l,mid,t[x].ad);
        getsum(rs,mid+1,r,t[x].ad);
        t[x].ad=0;
    }
    if(t[ls].mx>t[x].mx&&t[ls].cmx<t[x].mx) addmin(ls,l,mid,t[x].mx);
    if(t[rs].mx>t[x].mx&&t[rs].cmx<t[x].mx) addmin(rs,mid+1,r,t[x].mx);
    if(t[ls].mi<t[x].mi&&t[ls].cmi>t[x].mi) addmax(ls,l,mid,t[x].mi);
    if(t[rs].mi<t[x].mi&&t[rs].cmi>t[x].mi) addmax(rs,mid+1,r,t[x].mi);
}
void chanmx(int x,int l,int r,int L,int R,int c){
    //cout<<x<<" "<<l<<" "<<r<<" "<<L<<" "<<R<<" "<<c<<" "<<t[x].cmi<<endl;
    if(L<=l&&r<=R){
        if(t[x].mi>=c) return;
        if(t[x].cmi>c) {
            addmax(x,l,r,c);return;
        }
        pushdown(x,l,r);
        chanmx(ls,l,mid,L,R,c);
        chanmx(rs,mid+1,r,L,R,c);
        pushup(x);
        return;
    }
    pushdown(x,l,r);
    if(L<=mid) chanmx(ls,l,mid,L,R,c);
    if(mid<R) chanmx(rs,mid+1,r,L,R,c);
    pushup(x);
}
void chanmi(int x,int l,int r,int L,int R,int c){
    if(L<=l&&r<=R){
        if(t[x].mx<=c) return;
        if(t[x].cmx<c) {
            addmin(x,l,r,c);return;
        }
        pushdown(x,l,r);
        chanmi(ls,l,mid,L,R,c);
        chanmi(rs,mid+1,r,L,R,c);
        pushup(x);
        return;
    }
    pushdown(x,l,r);
    if(L<=mid) chanmi(ls,l,mid,L,R,c);
    if(mid<R) chanmi(rs,mid+1,r,L,R,c);
    pushup(x);
}
void add(int x,int l,int r,int L,int R,int c){
    if(L<=l&&r<=R){
        getsum(x,l,r,c);
        return;
    }
    pushdown(x,l,r);
    if(L<=mid) add(ls,l,mid,L,R,c);
    if(mid<R) add(rs,mid+1,r,L,R,c);
    pushup(x);
}
int qmax(int x,int l,int r,int L,int R){
    if(L<=l&&r<=R){
        return t[x].mx;
    }
    pushdown(x,l,r);int ret=-inf;
    if(L<=mid) ret=max(ret,qmax(ls,l,mid,L,R));
    if(mid<R) ret=max(ret,qmax(rs,mid+1,r,L,R));
    return ret;
}
int qmin(int x,int l,int r,int L,int R){
    if(L<=l&&r<=R){
        return t[x].mi;
    }
    pushdown(x,l,r);int ret=inf;
    if(L<=mid) ret=min(ret,qmin(ls,l,mid,L,R));
    if(mid<R) ret=min(ret,qmin(rs,mid+1,r,L,R));
    return ret;
}
ll qsum(int x,int l,int r,int L,int R){
    if(L<=l&&r<=R){
        return t[x].sum;
    }
    pushdown(x,l,r);ll ret=0;
    if(L<=mid) ret+=qsum(ls,l,mid,L,R);
    if(mid<R) ret+=qsum(rs,mid+1,r,L,R);
    return ret;
}
int main(){
    rd(n);
    for(reg i=1;i<=n;++i){
        rd(a[i]);
    }
    rd(m);
    ++tot;
    build(1,1,n);
    //cout<<" tot "<<tot<<endl;
    int op,l,r,x;
    int o=0;
    while(m--){
        ++o;
    //    cout<<" oooo "<<o<<endl;
        rd(op);
        switch(op){
            case 1:rd(l);rd(r);rd(x);add(1,1,n,l,r,x);break;
            case 2:rd(l);rd(r);rd(x);chanmx(1,1,n,l,r,x);break;
            case 3:rd(l);rd(r);rd(x);chanmi(1,1,n,l,r,x);break;
            case 4:rd(l);rd(r);printf("%lld\n",qsum(1,1,n,l,r));break;
            case 5:rd(l);rd(r);printf("%d\n",qmax(1,1,n,l,r));break;
            case 6:rd(l);rd(r);printf("%d\n",qmin(1,1,n,l,r));break;
        }
    }
    return 0;
}

}
signed main(){
    Miracle::main();
    return 0;
}

/*
   Author: *Miracle*
   Date: 2018/12/27 9:57:30
*/