Description

 

Input

Output

 

Sample Input

输入： 3 1 2 3 1 2 2 3 2 1 2 100 1 3 100

Sample Output

输出： 1 1

 

Data Constraint

 

 

解法：显然的链剖。维护区间max,min，前面减后面的max,后面减前面的max即可

 

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;struct Tree{    int lr,rl,mx,mn,bz;}tr[400011];Tree Tm[111];int g[50011],next[100011],y[100011],num[50011],dep[50011],fa[50011],top[50011];int id[50011],son[50011],size[50011],pm[111],sm[111],val[50011];int tot,tt,n,i,x,z,q,ans,m;struct AA{    int l,r,k,sh;}que[111];void star(int i,int j){    tt++;    next[tt]=g[i];    g[i]=tt;    y[tt]=j;}void build_chain(int root){    int x;    x=root;    while(x){        tot++;        id[tot]=x;        num[x]=tot;        top[x]=root;        x=son[x];    }}void dfs(int x){    int j,k;    size[x]=1;    j=g[x];    while(j!=0){        k=y[j];        if(k!=fa[x]){            fa[k]=x;            dep[k]=dep[x]+1;            dfs(k);            size[x]+=size[k];            if(size[k]>size[son[x]]){                if(son[x])build_chain(son[x]);                son[x]=k;            }            else build_chain(k);        }        j=next[j];    }    }Tree Merge(Tree a,Tree b){    Tree c;    c.mx=max(a.mx,b.mx);    c.mn=min(a.mn,b.mn);    c.rl=max(a.rl,b.rl);    c.rl=max(c.rl,b.mx-a.mn);    c.lr=max(a.lr,b.lr);    c.lr=max(c.lr,a.mx-b.mn);    return c;}void up(int t){    Tree a,b;    Tree &c=tr[t];    a=tr[t+t];b=tr[t+t+1];    c.mx=max(a.mx,b.mx);    c.mn=min(a.mn,b.mn);    c.rl=max(a.rl,b.rl);    c.rl=max(c.rl,b.mx-a.mn);    c.lr=max(a.lr,b.lr);    c.lr=max(c.lr,a.mx-b.mn);}void build(int l,int r,int t){    if(l==r){        tr[t].mx=tr[t].mn=val[id[l]];        tr[t].lr=tr[t].rl=0;        tr[t].bz=0;        return;    }    int mid;    mid=(l+r)/2;    build(l,mid,t+t);    build(mid+1,r,t+t+1);    tr[t].bz=0;    up(t);}void change(int t,int x){    tr[t].bz+=x;    tr[t].mx+=x;    tr[t].mn+=x;}void down(int t,int l,int r){    if(l==r)return;    if(tr[t].bz){        change(t+t,tr[t].bz);        change(t+t+1,tr[t].bz);        tr[t].bz=0;    }}void insert(int t,int l,int r,int x,int y,int z){    down(t,l,r);    if(l==x&&r==y){        change(t,z);        return;    }    int mid;    mid=(l+r)/2;    if(y<=mid)insert(t+t,l,mid,x,y,z);    if(x>mid)insert(t+t+1,mid+1,r,x,y,z);    if(x<=mid&&y>mid){        insert(t+t,l,mid,x,mid,z);        insert(t+t+1,mid+1,r,mid+1,y,z);    }    up(t);}Tree ask(int t,int l,int r,int x,int y){    down(t,l,r);    if(l==x&&r==y)return tr[t];    Tree re;    int mid;    mid=(l+r)/2;    if(y<=mid)re=ask(t+t,l,mid,x,y);    if(x>mid)re=ask(t+t+1,mid+1,r,x,y);    if(x<=mid&&y>mid)re=Merge(ask(t+t,l,mid,x,mid),ask(t+t+1,mid+1,r,mid+1,y));    up(t);    return re;}bool cmp(AA a,AA b){    if(a.k==b.k){        if(a.k==1)return a.sh
          
           b.sh; } else return a.k
           
            =1;i--)sm[i]=max(sm[i+1],Tm[i].mx); ans=-214748364; for(i=1;i<=ts;i++){ if(que[i].k==2)ans=max(ans,Tm[i].rl); else ans=max(ans,Tm[i].lr); ans=max(ans,sm[i+1]-pm[i]); }}int main(){ scanf("%d",&n); for(i=1;i<=n;i++)scanf("%d",&val[i]); for(i=1;i