Description：

给一个长度为 $n$ 的数组，选一个子序列划分为若干极长单调区间且第一个区间单调上升，子序列的价值为总和 $/$ 单调区间数，求价值最大的子序列。

$1\le n \le 100000$

Solution：

有一个结论：最终选出的子序列单调区间数不超过二。

如果有一个单调区间数更多的子序列，设其价值为 $S/m$ ，若其单调区间数为奇数，那么最后一个区间单调上升设其价值为 $T$ ，那么 $\frac S m$ 一定在 $\frac {S-T}{m-1}$ 和 $T$ 之间，所以可以保留一个，若单调区间数为偶数，同理最后两个单调区间一定是一个上升一个下降，设其和为 $T$ ，那么 $\frac S m$ 一定在 $\frac{S-T}{m-2}$ 和 $\frac T 2$ 之间，也可以去掉一段。

所以最终一定是一个单调上升区间或一个单调上升，一个单调下降，用树状数组优化 $LIS$ ，再枚举分界点即可。

关于上面那个性质怎么证，如果 $T$ 高于平均数，那么去掉 $T$ 后平均值会降低，而 $T$ 又高于原来的平均数，如果 $T$ 低于原来的平均数，那去掉 $T$ 后平均值会升高，所以一定是一个高一个低。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

int a[MAXN];

int b[MAXN];

bool cmp(int x,int y){return a[x] < a[y];}

int s[MAXN],w = 0;

int lowbit(int x){return x&(-x);}

typedef long long ll;

ll c_inc[MAXN];

void add_inc(int p,ll x)

{

	for(int i = p;i <= w;i += lowbit(i))c_inc[i] = max(c_inc[i],x);

	return;

}

ll query_inc(int p)

{

	ll res = 0;

	for(int i = p;i >= 1;i -= lowbit(i))res = max(res,c_inc[i]);

	return res;

}

ll f1[MAXN],f2[MAXN];

int main()

{

    freopen("seq.in","r",stdin);

    freopen("seq.out","w",stdout);

    scanf("%d",&n);

    for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

    for(int i = 1;i <= n;++i)b[i] = i;

    sort(b + 1,b + 1 + n,cmp);

    for(int i = 1;i <= n;++i)

    {

        if(i == 1 || a[b[i]] != a[b[i - 1]])s[b[i]] = ++w;

        else s[b[i]] = w;

    }

    for(int i = 1;i <= n;++i)

    {

		f1[i] = query_inc(s[i] - 1) + a[i];

		add_inc(s[i],f1[i]);

	}

	memset(c_inc,0,sizeof(c_inc));

	for(int i = n;i >= 1;--i)

	{

		f2[i] = query_inc(s[i] - 1) + a[i];

		add_inc(s[i],f2[i]);

	}

	for(int i = 2;i <= n;++i)f1[i] = max(f1[i],f1[i - 1]);

	for(int i = n - 1;i >= 1;--i)f2[i] = max(f2[i],f2[i + 1]);

	double ans = 0;

	for(int i = 1;i < n;++i)ans = max(ans,(double)(f1[i] + f2[i + 1]) / 2.0);

	for(int i = 1;i <= n;++i)ans = max(ans,(double)f1[i]);

	printf("%.3lf\n",ans);

    fclose(stdin);

    fclose(stdout);

    return 0;

}