BZOJ4695 최가짜 여자 선수(세능선 트리)

BZOJ 제목 전송문
마침내 세력을 초보적으로 파악하여 사상을 분석하는 중요성을 체득하였다.
처음에 문제를 보니 틀이 여전히 보통인 것 같다.라인 트리에서 최대치와 최소치를 직접 유지합니다. 매번 갱신될 때마다 완전히 덮어쓰지 못하면 폭력적으로 귀속됩니다.잘 썼네.
지난번에 모험 상수를 너무 많이 썼던 경험을 감안하여 이번에는 기이한 바늘 라인 트리를

#include
#define RG register
#define R RG int
#define G if(++ip==ie)fread(ip=buf,1,N,stdin)
#define pushup                                  \
    s=lc->s+rc->s;                              \
    mn=min(lc->mn,rc->mn);                      \
    mx=max(lc->mx,rc->mx)
#define pushdn                                  \
    if(ls!=INF)lc->lset(ls),rc->lset(ls),ls=INF;\
    if(la)lc->ladd(la),rc->ladd(la),la=0
using namespace std;
typedef long long LL;
const int N=1<<20,INF=1e9;
char buf[N],*ie=buf+N,*ip=ie-1;
int op,x;
inline int in(){
    G;while(*ip'-'){x*=10;x+=*ip&15;G;}
    return f?-x:x;
}
struct Node{
    Node*lc,*rc;
    int l,r,m,mn,mx,ls;LL s,la;
    void build(R b,R e){// 
        m=((l=b)+(r=e))>>1;ls=INF;la=0;
        if(b==e){
            s=mn=mx=in();return;
        }
        (lc=new Node)->build(l,m);
        (rc=new Node)->build(m+1,r);
        pushup;
    }
    inline void lset(R x){// 
        s=(LL)x*(r-l+1);mn=mx=ls=x;la=0;
    }
    inline void ladd(R x){// 
        s+=(LL)x*(r-l+1);mn+=x;mx+=x;la+=x;
    }
    void add(R b,R e){// 1
        if(l==b&&r==e)return this->ladd(x);
        pushdn;
        if(e<=m)lc->add(b,e);
        else if(b>m)rc->add(b,e);
        else lc->add(b,m),rc->add(m+1,e);
        pushup;
    }
    void upd(R b,R e){// 2/3
        if(op&1?mx<=x:mn>=x)return;
        if(l==b&&r==e&&(op&1?mn>=x:mx<=x))return this->lset(x);
        pushdn;
        if(e<=m)lc->upd(b,e);
        else if(b>m)rc->upd(b,e);
        else lc->upd(b,m),rc->upd(m+1,e);
        pushup;
    }
    LL qrys(R b,R e){// 4
        if(l==b&&r==e)return s;
        pushdn;
        if(e<=m)return lc->qrys(b,e);
        if(b> m)return rc->qrys(b,e);
        return lc->qrys(b,m)+rc->qrys(m+1,e);
    }
    int qrym(R b,R e){// 5/6
        if(l==b&&r==e)return op&1?mx:mn;
        pushdn;
        if(e<=m)return lc->qrym(b,e);
        if(b> m)return rc->qrym(b,e);
        if(op&1)return max(lc->qrym(b,m),rc->qrym(m+1,e));
        return min(lc->qrym(b,m),rc->qrym(m+1,e));
    }
};
int main(){
    RG Node rt;rt.build(1,in());
    for(R m=in(),l,r;m;--m){
        op=in();l=in();r=in();
        if(op<=3)x=in(),op==1?rt.add(l,r):rt.upd(l,r);
        else if(op==4)printf("%lld
",rt.qrys(l,r));
        else printf("%d
",rt.qrym(l,r));
    }
    return 0;
}

그리고 지나갔어?!그리고 BZOJ rank 1?!
그리고 이건 폭력이야.
분명히 우리는 세력 분석에 착안해야 한다.다음은 맥스를 취하는 것이 하나의 일이기 때문에 마구잡이로 강요하기 시작한다.
라인 트리 노드의 세 함수를 관할 구간 내의 다른 수의 개수로 마음대로 정의합니다.이렇게 초기세 함수 합계는\(n\log n)\레벨입니다.
구간의 최소값만 기록한다면, 분명히 한 번 수정하면, 그것은 최소값일 수도 있고, 세 함수는 줄어들지 않을 것이다.
그럼 어떻게 하지?다음 값을 적어라!만약\(x\)가 최소값보다 크고 차소값보다 작다면, 우리는 한 구간에서 최소값을 수정하는 표시를 합니다.만약\(x\)가 차소치보다 크면 틀림없이 다른 수의 개수가 줄어들 것이다. 여기에 추가로 전개될 때마다 폭력 귀속세 함수는 적어도\(1\) 줄어든다. 복잡도가 맞다.
여기서 유지보수를 해야 한다는 것을 알았기 때문에 우리는 최소값을 기록할 때 구간 내 최소값의 개수를 유지보수합니다.
만약 구간min/max만 있다면, 복잡도는 하나의\(\log\)입니다.
그러나 이곳의 조작은 min도 있고 max도 있고 구간도 있으니 이때 별도로 분석해야 한다.길 선생은 논문에서 비교적 느슨한\(m\log^2\) 상계가 있다고 말한 것 같지만, 그 이론을 분석할 수 있는 세력을 아직 잘 모르면 계속 강요할 수 없다는 것을 발견했다.
cz_xuyixuan 팀의 블로그
이런 말

 ， 。

그러나, 이것이 몇 십 번 찍어도 WA를 하고, 세 번 코드를 재구성할 수 있는 라인 트리입니까?
자세한 질문:
구간 플러스, 구간 플러스 최소값, 구간 플러스 최대값은 이치상 독립적인 것 같지만 蒻蒻는 양쪽 마지막에 구간 표시를 넣는 코드를 재구성하여 조정할 수 없다. 어쩔 수 없이 가장 먼저 구간 플러스를 넣었다가 현학 문제로 int를 터뜨렸다.
cz_xuyixuan 팀이 쓴 것은 먼저 min/max를 넣고 구간을 넣는 것이다.
구간에min을 가할 때 구간의 최대치/차대치에 대한 영향을 고려해야 할 수도 있다(구간이 하나 또는 두 개의 다른 수일 경우).구간 가max동리.
구간에 min/max를 추가할 때 가장 값어치가 있는 트리의 출처를 판단한 후에 놓는다.
코드 따위는 너를 아프게 할 거야...억지로 define 쓰기 함수로 사람들이 4KB+를 써야 하는 코드를 3KB로 줄였다...이 구덩이는 조심해서 들어가라!
부득이하게 롱롱비를 켜서.

#include
#define RG register
#define R RG int
#define I inline void
#define G if(++ip==ie)fread(ip=buf,1,N,stdin)
using namespace std;
typedef long long LL;
const int N=1<<19,INF=1e9;
char buf[N],*ie=buf+N,*ip=ie-1;
int x;
inline int in(){
    G;while(*ip'-'){x*=10;x+=*ip&15;G;}
    return f?-x:x;
}
#define int LL// 
struct Node{
    Node*lc,*rc;
    int l,r,m,mn1,mn2,mnc,mx1,mx2,mxc,lmn,lmx,lad,s;
    I up(){// ， 
        s=lc->s+rc->s;
        if(lc->mn1mn1)
            mn1=lc->mn1,mnc=lc->mnc,mn2=min(lc->mn2,rc->mn1);
        else if(lc->mn1>rc->mn1)
            mn1=rc->mn1,mnc=rc->mnc,mn2=min(rc->mn2,lc->mn1);
        else mn1=lc->mn1,mnc=lc->mnc+rc->mnc,mn2=min(lc->mn2,rc->mn2);
        if(lc->mx1>rc->mx1)
            mx1=lc->mx1,mxc=lc->mxc,mx2=max(lc->mx2,rc->mx1);
        else if(lc->mx1mx1)
            mx1=rc->mx1,mxc=rc->mxc,mx2=max(rc->mx2,lc->mx1);
        else mx1=lc->mx1,mxc=lc->mxc+rc->mxc,mx2=max(lc->mx2,rc->mx2);
    }
    I dnlad(R x){// 
        mn1+=x;if(mn2!= INF)mn2+=x;
        mx1+=x;if(mx2!=-INF)mx2+=x;
        s+=x*(r-l+1);lad+=x;
    }
    I dnlmn(R x){// 
        if(mn1==mx1)mx1+=x;if(mn1==mx2)mx2+=x;// 
        s+=x*mnc;mn1+=x;lmn+=x;
    }
    I dnlmx(R x){// 
        if(mx1==mn1)mn1+=x;if(mx1==mn2)mn2+=x;
        s+=x*mxc;mx1+=x;lmx+=x;
    }
    I dn(){// 
        if(lad)lc->dnlad(lad),rc->dnlad(lad),lad=0;
        if(lmn){
            if(lc->mn1<=rc->mn1)lc->dnlmn(lmn);
            if(lc->mn1>=rc->mn1)rc->dnlmn(lmn);
            lmn=0;
        }
        if(lmx){
            if(lc->mx1>=rc->mx1)lc->dnlmx(lmx);
            if(lc->mx1<=rc->mx1)rc->dnlmx(lmx);
            lmx=0;
        }
    }
    I build(R b,R e){// 
        m=((l=b)+(r=e))>>1;lmn=lmx=lad=0;
        if(l==r){
            s=mn1=mx1=in();mnc=mxc=1;
            mn2=INF;mx2=-INF;
            return;
        }
        (lc=new Node)->build(l,m);
        (rc=new Node)->build(m+1,r);
        this->up();
    }
#define sum(x,y) x+y// 
#define upd(Fun,Lim,Req,Tag)                    \
    I Fun(R b,R e){                             \
        if(Lim)return;                          \
        if(l==b&&r==e Req)return this->Tag;     \
        this->dn();                             \
        if(e<=m)lc->Fun(b,e);                   \
        else if(b>m)rc->Fun(b,e);               \
        else lc->Fun(b,m),rc->Fun(m+1,e);       \
        this->up();                             \
    }// 
#define qry(Fun,Typ,Ret,Opt)                    \
    inline Typ Fun(R b,R e){                    \
        if(l==b&&r==e)return Ret;               \
        this->dn();                             \
        if(e<=m)return lc->Fun(b,e);            \
        if(b>m)return rc->Fun(b,e);             \
        return Opt(lc->Fun(b,m),rc->Fun(m+1,e));\
    }
    upd(us,0,,dnlad(x));
    upd(umn,mn1>=x,&&mn2>x,dnlmn(x-mn1));
    upd(umx,mx1<=x,&&mx2