CF573E (平衡树)

CF573E

题意概要

给出一个长度为$n$的数列，从中选出一个子序列$b[1...m]$（可以为空）

使得$$ \sum_{i=1}^m{b_i*i}$$最大，输出这个最大值。

其中$n\le10^5$

题解

设$dp_{i,j}$表示前$i$个数选择$j$个数的最大值

那么，转移方程则为：

\[dp_{i,j}=max(dp_{i-1,j},dp_{i-1,j-1}+j*a_i)
\]

于是我们就得到了一个$n^2$的做法

我们考虑优化这个式子。

经$dalao$证明，发现总有存在一个分界线，这之前的取前者，这之后的取后者

大佬的证明在这里

我们二分分界线，然后用平衡树维护就好了

顺带一提，我今日方知$splay$没事多$ splay $几下还会变快

代码

#include<bits/stdc++.h>

#include<windows.h>

#define lch c[x][0]

#define rch c[x][1]

using namespace std;

typedef long long ll;

const int sz=1e5+7;

int n;

ll v,ans;

int rt,cnt;

int f[sz];

int c[sz][2];

int siz[sz];

ll val[sz],tag1[sz],tag2[sz];

inline int newnode(ll v){

	int x=++cnt;

	val[x]=v;

	siz[x]=1;

	return x;

}

inline void pushup(int x){

	siz[x]=siz[lch]+siz[rch]+1;

}

inline void add(int x,ll tg1,ll tg2){

	val[x]+=siz[lch]*tg1+tg2;

	tag1[x]+=tg1;

	tag2[x]+=tg2;

}

inline void pd(int x){

	if(tag1[x]==0&&tag2[x]==0) return;

	if(lch) add(lch,tag1[x],tag2[x]);

	if(rch) add(rch,tag1[x],tag2[x]+(siz[lch]+1)*tag1[x]);

	tag1[x]=0;

	tag2[x]=0;

}

inline void pushdn(int x){

	if(f[x]) pushdn(f[x]);

	pd(x);

}

inline int get(int x){

	return c[f[x]][1]==x;

}

inline void dfs(int x){

	ans=max(ans,val[x]);

	pd(x);

	if(lch) dfs(lch);

	if(rch) dfs(rch);

}

inline void rotate(int x){

	int y=f[x],z=f[y],k=get(x),w=c[x][!k];

	if(z) c[z][get(y)]=x;c[x][!k]=y;c[y][k]=w;

	if(w) f[w]=y;if(y) f[y]=x;f[x]=z;

	pushup(y);

}

inline void splay(int x,int t){

	pushdn(x);

	while(f[x]!=t){

		int y=f[x];

		if(f[y]!=t) rotate(get(x)^get(y)?x:y);

		rotate(x);

	}

	pushup(x);

	if(t==0) rt=x;

}

inline int find(int k){

	int x=rt;

	while(1){

		pd(x);

		if(siz[lch]+1==k) return x;

		if(k<=siz[lch]) x=lch;

		else k-=siz[lch]+1,x=rch;

	}

}

inline void insert(int k,ll v){

	int x=find(k-1);splay(x,0);

	int y=find(k);splay(y,x);

	c[y][0]=newnode(v);

	f[c[y][0]]=y;

	pushup(y);

	pushup(x);

}

inline void modify(int l,int r,ll a,ll b){

	int x=find(l-1);splay(x,0);

	int y=find(r+1);splay(y,x);

	add(c[y][0],a,b);

	pushup(y);

	pushup(x);

}

int main(){

	scanf("%d",&n);

	rt=newnode(0);

	c[rt][0]=newnode(INT_MIN);

	c[rt][1]=newnode(INT_MIN);

	f[c[rt][0]]=f[c[rt][1]]=rt;

	pushup(rt);

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

		scanf("%lld",&v);

		int l=2,r=i+1;

		while(l<r){

			int mid=(l+r)>>1;

			if(val[find(mid)]+(mid-1)*v>=val[find(mid+1)]) r=mid;

			else l=mid+1;

			splay(find(mid),0);

		}

		int x=find(l);

		ll y=val[x];

		modify(l,i+1,v,v*(l-1));

		insert(l,y);

	}

	dfs(rt);

	printf("%lld\n",ans);

}

巴特西

CF573E (平衡树)

CF573E

题意概要

题解

代码

最新文章

热门文章