[线段树][区间最值操作][论文题][难] HDU5306 Gorgeous Sequence

这个题也是看了一晚上，各种题解各种论文各种ppt emmmmmmm

话说发现真的线段树这东西不能看别人的代码，怎么看怎么看不懂，非得自己写一遍才是。感觉市面上常见的线段树也就两种写法，一种是pushdown以及在update预判返回的时候把维护子节点的事情做了，维护只维护当前节点所以又叫pushup，另一种是pushdown和预判都只改变标记，而所有的维护都交给maintain来做，(⊙﹏⊙)我一直写的是后一种，但是这里写前一种貌似比较方便（🌫）因为update在这里兼具了更新和搜索的功能，所以最好是在pushdown的时候就把维护子节点的事情做了。（感觉自己对pushdown标记的理解之前还是不到位啊emmmm还是得写）

#include
#include
#include
#include
#include
#include
#include

using namespace std;

typedef long long LL;
const int maxn=1e6+5;
const int MOD=1e9+7;

const int BufferSize=1<<16;
char buffer[BufferSize],*head,*tail;
inline char Getchar()
{
    if(head==tail)
    {
        int l=fread(buffer,1,BufferSize,stdin);
        tail=(head=buffer)+l;
    }
    return *head++;
}
inline int read()
{
    int x=0,f=1;
    char c=Getchar();
    for (;!isdigit(c);c=Getchar())if(c=='-')f=-1;
    for (;isdigit(c);c=Getchar())x=x*10+c-'0';
    return x*f;
}


LL mx[maxn<<2],su[maxn<<2],se[maxn<<2];
int cv[maxn<<2];

void maintain(int o,int l,int r)
{
    su[o]=su[o<<1]+su[o<<1|1];
    mx[o]=max(mx[o<<1],mx[o<<1|1]);
    if(mx[o<<1]==mx[o<<1|1])
    {
        se[o]=max(se[o<<1],se[o<<1|1]);
        cv[o]=cv[o<<1]+cv[o<<1|1];
    }
    else
    {
        se[o]=max(se[o<<1],se[o<<1|1]);
        se[o]=max(se[o],min(mx[o<<1],mx[o<<1|1]));
        cv[o]=mx[o<<1] > mx[o<<1|1]?cv[o<<1]:cv[o<<1|1];
    }
}

void build(int o,int l ,int r)
{
    if(l==r)
    {
        //scanf("%lld",&su[o]);
        su[o]=read();
        mx[o]=su[o];
        se[o]=-1;
        cv[o]=1;
        return ;
    }
    else
    {
        build(o<<1,l,(l+r)>>1);
        build(o<<1|1,((l+r)>>1)+1,r);
        maintain(o,l,r);
    }
}

void pushdown(int o)//之前打上的标记一定是合法标记,不用考虑是否小于se
{//这个写法和我平时的不一样，我平时push和update里面只处理标记，其他的工作都在maintain里
    if(mx[o]>1;
    if(pl<=mid)update(o<<1,l,mid);
    if(pr>mid)update(o<<1|1,mid+1,r);
    maintain(o,l,r);
}

int ql,qr;
LL qSum(int o,int l,int r)
{//一开始不用maintain，因为pushdown已经做了这个工作
    if(ql<=l&&r<=qr)
        return su[o];
    pushdown(o);
    LL ans=0;
    int mid=(l+r)>>1;
    if(ql<=mid)ans+=qSum(o<<1,l,mid);
    if(mid>1);
    if(ql<=mid)ans=qMax(o<<1,l,mid);
    if(mid