思路:

首先我们考虑序列中最大的元素,如果它是当前区间的头或者尾,当然是只合并一次最优了,否则当然是至少要合并两次了.

将这个元素的影响去掉,然后将区间分裂开,递归处理就行了.容易发现总处理区间数是\(O(n)\)的.

那么现在我们的问题是,给出\(O(n)\)个询问,每次询问一段区间的最大值的标号.

那么我们有两种策略:

[1]RMQ ST算法 \(O(nlogn)-O(1) 空间O(nlogn)\)

[2]直接线段树 \(O(n)-O(logn) 空间O(n)\)

事实上[2]的常数很小,而[1]会TLE!再兼具空间,可以说,在这种询问次数下,[2]完爆[1]!

所以这样就水过去了.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define INF 0x3f3f3f3f
 
namespace Fio{
    inline int getc(){
        static const int L=1<<15;static char buf[L],*S=buf,*T=buf;
        if(S==T){T=(S=buf)+fread(buf,1,L,stdin);if(S==T)return EOF;}
        return*S++;
    }
    template<typename T>inline void Get(T&x){
        int c;while(!isdigit(c=getc()));x=c-'0';while(isdigit(c=getc()))x=(x<<1)+(x<<3)+c-'0';
    }
}
 
#define N 1000010
int a[N];
 
struct SegmentTree{
    int ins[262144*8],M;
    inline void Init(int _siz){
        for(M=1;M<(_siz+2);M<<=1);
        for(int i=1;i<=_siz;++i)ins[M+i]=i;
        a[0]=-INF;for(int i=M-1;i>=1;--i)ins[i]=a[ins[i<<1]]>a[ins[i<<1^1]]?ins[i<<1]:ins[i<<1^1];
    }
    inline int ask(int tl,int tr){
        int res=0;
        for(tl+=M-1,tr+=M+1;tl^tr^1;tl>>=1,tr>>=1){
            if((~tl&1)&&(a[res]<a[ins[tl^1]]))res=ins[tl^1];
            if((tr&1)&&(a[res]<a[ins[tr^1]]))res=ins[tr^1];
        }return res;
    }
}Seg;
 
struct Intv{
    int l,r;Intv(){}Intv(int _l,int _r):l(_l),r(_r){}
}q[N];int fr,ta;
 
int main(){
    int n;Fio::Get(n);register int i,j;for(i=1;i<=n;++i)Fio::Get(a[i]);Seg.Init(n);
    long long ans=0;
    q[ta++]=Intv(1,n);Intv tmp;int ins;
    while(fr^ta){
        tmp=q[fr++];if(tmp.l==tmp.r)continue;ins=Seg.ask(tmp.l,tmp.r);
        if(ins==tmp.l)ans+=a[ins],q[ta++]=Intv(tmp.l+1,tmp.r);else if(ins==tmp.r)ans+=a[ins],q[ta++]=Intv(tmp.l,tmp.r-1);
        else ans+=2LL*a[ins],q[ta++]=Intv(tmp.l,ins-1),q[ta++]=Intv(ins+1,tmp.r);
    }
    printf("%lld\n",ans);
    return 0;
}

思路:发现若\(S_1\)不同,则整个序列就不同.因此我们的任务就是找出有多少种\(S_1\)的方案.

我们把\(S_2...S_{n+1}\)都用关于\(S_1\)的一次函数表示,则我们有\(n\)个线性约束条件,对于第\(i\)个条件,我们有\(S_{i}\leq{S_{i+1}}\).

直接接出\(S_1\)的上下界即可.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef long long LL;
 
#define N 5000010
int k[N];LL b[N];
 
int main(){
    int n;scanf("%d",&n);register int i;LL a;
    k[1]=1,b[1]=0;
    for(i=2;i<=n+1;++i)scanf("%lld",&a),k[i]=-k[i-1],b[i]=2LL*a-b[i-1];
    LL up=1LL<<60,down=-1LL<<60;
    for(i=1;i<=n;++i){
        if(k[i]==1)up=min(up,b[i+1]-b[i]);
        else down=max(down,b[i]-b[i+1]);
    }
    if(up>0)up/=2;else{if(up&1)up=(up-1)/2;else up/=2;}
    if(down>0){if(down&1)down=(down+1)/2;else down/=2;}else down/=2;
    if(up<down){puts("0");return 0;}else printf("%lld",up-down+1);
    return 0;
}