[CSP-S模拟测试]:小P的单调数列（树状数组+DP）

题目描述

　　小$P$最近喜欢上了单调数列，他觉得单调的数列具有非常多优美的性质。经过小$P$复杂的数学推导，他计算出了一个单调增数列的艺术价值等于该数列中所有书的总和。并且以这个为基础，小$P$还可以求出任意一个数列的艺术价值，它等于将这个数列顺次划分若干个极长单调区间（相邻两个单调区间的单调性必须不相同）后，每个单调区间中元素总和的平均值。比如对于数列$3\ 7\ 9\ 2\ 4\ 5$，它将被划分为$[3\ 7\ 9]\ [2]\ [4\ 5]$，其艺术价值为$\frac{19+2+9}{3}=10$。　　由于小$P$的审美观，他还要求划分出的第一个单调区间必须为单调增区间，也就是说，对于数列$10\ 9\ 8$，它将被划分为$[10]\ [9\ 8]$，而不是$[10\ 9\ 8]$。
　　现在小$P$手里有一个长度为$n$的序列$\{a_i\}$，他想问你，这个序列的所有子序列中，艺术价值最大的是哪个子序列，输出其艺术价值。
　　注意：本体单调数列为严格单调，也就是说数列中的数必须严格上升或严格下降。

输入格式

输入的第一行为一个正整数$n$，表示序列的长度。
接下来的一行为$n$个正整数$a_1,a_2,...,a_n$，代表序列中的$n$个数。

输出格式

输出仅有一个实数，表示子序列的最大艺术价值。
实数四舍五入，保留三位小数。

样例

样例输入1：

4
1 2 5 4

样例输出1：

8.000

样例输入2：

6
3 1 7 2 6 5

样例输出2：

10.500

数据范围与提示

对于第一个样例，最优的子序列为$1\ 2\ 5$，其价值为$8$。如果选择$5\ 4$的话，虽然和为$9$，但单调区间数为$2$，因为第一个单调区间必须为递增区间。
对于第二个样例，最优的子序列为$3\ 7\ 6\ 5$，其价值为$\frac{3+7+6+5}{2}=10.5$。

题解

首先，来看一条性质：一定存在一个最优子序列，它的单调区间长度不超过$2$。

有了这个性质，这道题就简单多了，维护三个树状数组就好了。

下面是某大神总结的树状数组的用途：

$1$：快速简洁求解前缀最值
$2$：快速简洁求解前缀和，单点修改区间和，区间修改单点值。
$3$：并不简洁的求解区间修改区间求和（但也比线段树简洁）
$4$：快速维护树上每个点到根的路径权值和
$5$：快速维护树上每个点的子树和（与$4$不兼容）
$6$：用来轻松愉快的套主席树，$Splay$等各类动态数据结构
$7$：维护带删除\插入操作的排名，不过需要二分，两个$log$不推荐，推荐线段树一个$log$

时间复杂度：$\Theta(n\log n)$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

int n;

int a[100001],b[100001];

long long tr1[100001],tr2[100001],tr3[100001];

double ans;

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

void add1(int x,long long w){for(int i=x;i;i-=lowbit(i))tr1[i]=max(tr1[i],w);}

void add2(int x,long long w){for(int i=x;i<=b[0];i+=lowbit(i))tr2[i]=max(tr2[i],w);}

void add3(int x,long long w){for(int i=x;i;i-=lowbit(i))tr3[i]=max(tr3[i],w);}

long long ask1(int x)

{

	long long res=0;

	for(int i=x;i<=b[0];i+=lowbit(i))res=max(res,tr1[i]);

	return res;

}

long long ask2(int x)

{

	long long res=0;

	for(int i=x;i;i-=lowbit(i))res=max(res,tr2[i]);

	return res;

}

long long ask3(int x)

{

	long long res=0;

	for(int i=x;i<=b[0];i+=lowbit(i))res=max(res,tr3[i]);

	return res;

}

int main()

{

	scanf("%d",&n);

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

	{

		scanf("%d",&a[i]);

		b[i]=a[i];

	}

	b[0]=n;

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

	b[0]=unique(b+1,b+b[0]+1)-b-1;

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

		a[i]=lower_bound(b+1,b+b[0]+1,a[i])-b+1;

	b[0]++;

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

	{

		long long w1=ask1(a[i]+1),w2=ask2(a[i]-1),w3=ask3(a[i]+1);

		ans=max(ans,(1.0*w3+b[a[i]-1])/2.0);

		ans=max(ans,(1.0*b[a[i]-1]+w2)/2.0);

		ans=max(ans,1.0*w1+b[a[i]-1]);

		add1(a[i],b[a[i]-1]+w1);

		add2(a[i],b[a[i]-1]+w2);

		add3(a[i],b[a[i]-1]+max(w2,w3));

	}

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

	return 0;

}

rp++

巴特西