CF573E Bear and Bowling 做题记录

给定一个长 $n$ 的序列 $a$，从 $a$ 中选择一个子序列 $b$，使得 $\sum ib_i$ 最大，输出这个最大值。

$1\le n\le 10^5$，$0\le |a_i|\le 10^7$。

考虑一个显然的 dp，设 $f_{i,j}$ 表示 $a_{[1,i]}$ 中选了 $j$ 个的最大 $\sum ib_i$，则有转移：

$f_{i,j}=\max(f_{i-1,j},f_{i-1,j-1}+ja_i)$

有一个神奇的结论，存在 $k$ 满足：

$f_{i,j}=\begin{cases} f_{i-1,j}&j<k\\ f_{i-1,j-1}+ja_i&j\ge k \end{cases}$

具体证明有点复杂，大概就是这个东西的本质是一个贪心的优化。
那么用平衡树动态维护 $f_{i,*}$ 的差分数组即可，时间复杂度 $O(n\log n)$。

代码如下：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>

using namespace std;

const int S=100005;

struct node
{
	int ls,rs,w;
	int siz;
	long long val,tag;
};

node tr[S];
int trcnt;

int nnde(long long x)
{
	tr[++trcnt]=(node){0,0,rand(),1,x,0};
	return trcnt;
}

void upd(int u)
{
	int ls=tr[u].ls,rs=tr[u].rs;
	tr[u].siz=tr[ls].siz+tr[rs].siz+1;
}

void dwntag(int u)
{
	int ls=tr[u].ls,rs=tr[u].rs;
	tr[ls].val+=tr[u].tag,tr[ls].tag+=tr[u].tag;
	tr[rs].val+=tr[u].tag,tr[rs].tag+=tr[u].tag;
	tr[u].tag=0;
}

void split(int u,long long val,int siz,int &x,int &y)
{
	if(u==0) return x=y=0,void();
	dwntag(u);
	int &ls=tr[u].ls,&rs=tr[u].rs;
	int sz=tr[ls].siz+siz+1;
	if(tr[u].val>val*sz) split(rs,val,sz,rs,y),x=u;
	else split(ls,val,siz,x,ls),y=u;
	upd(u);
}

void merge(int x,int y,int &u)
{
	if(x==0||y==0) return u=x+y,void();
	dwntag(x),dwntag(y);
	int &xrs=tr[x].rs,&yls=tr[y].ls;
	if(tr[x].w<tr[y].w) merge(xrs,y,xrs),u=x;
	else merge(x,yls,yls),u=y;
	upd(u);
}

long long getans(int u,long long &sum)
{
	if(u==0) return 0;
	dwntag(u);
	long long res=getans(tr[u].ls,sum);
	res=max(res,sum+=tr[u].val);
	res=max(res,getans(tr[u].rs,sum));
	return res;
}

int n,rt;

int main()
{
	srand(time(NULL));
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		long long x;
		scanf("%lld",&x);
		int rx,ry;
		split(rt,x,0,rx,ry);
		int k=tr[rx].siz+1;
		int pre=nnde(x*k);
		tr[ry].val+=x,tr[ry].tag+=x;
		merge(rx,pre,rt);
		merge(rt,ry,rt);
	}
	long long sum=0;
	printf("%lld\n",getans(rt,sum));
	return 0;
}