Problem Link

题目大意

给定 $w_1\sim w_n$，定义一个序列的权值 $p$ 为所有前缀最大值 $x$ 处的 $\sum w_{p_x}$。

已知排列 $a$ 中的若干元素，对于每个前缀求其权值的最大值。

数据范围：$n\le 4\times 10^5$。

思路分析

朴素 dp 就是 $f_{i,j}$ 表示 $[1,i]$ 最大值为 $j$ 的方案数，但此时 $f$ 中有很多零散的 $-\infty$，难以维护。

我们把已经在 $a$ 中出现的 $j$ 从状态中删掉，然后对于 $a_i\ne -1$ 的点特殊维护 $f_{i,a_i}$ 并删除 $f_i$ 中的一段前缀。

此时 $f_{i,j}$ 是单调递增的（$f_{i,j}$ 的解把 $j$ 换成 $j+1$ 就得到 $f_{i,j+1}$ 的解）。

那么对于一个 $a_i=-1$ 的点，转移就是 $f_{i,j}\gets\max(f_{i-1,j-1}+v_j,f_{i-1,j})$，其中 $v_j$ 是第 $j$ 个 $\not\in A$ 的数的权值。

直接使用数据结构维护这个过程是不可能的。

但我们发现 $f_{i,j}-v_j\le f_{i,j-1}$，在最优解处把 $j$ 换成 $j-1$ 就能证明。

因此这个操作直接就变成 $f_{i,j}\gets f_{i-1,j-1}+v_j$。

设 $k=\max f_{i,a_i}$，那么还有一个操作是 $f_{i,j}\gets k+v_j$，这个操作不好维护，但是我们可以转而维护 $f_{i,j}-v_j$。

很显然这个式子也有单调性，相当于不考虑最大值的贡献，此时 $j$ 越大对前面的限制依然越宽松，这样这个转移就变成了全局 chkmax，也就是前缀赋值操作，前一个转移变成 $f_{i,j}\gets f_{i-1,j-1}+v_{j-1}$。

现在我们只要用数据结构维护这个简单 dp 即可。

首先操作二先把所有数循环移位一下，然后打一个懒标记 $k$ 表示 $f_{i,j}$ 要加上 $v_{j-k}\sim v_{j-1}$。

前缀赋值操作可以用颜色段均摊，动态维护 $f$ 初值相同的连续段，暴力弹出开头的若干 $<k$ 的连续段，并且在最后一段上二分分界点即可。

时间复杂度 $\mathcal O(n\log n)$。

代码呈现

#include<bits/stdc++.h>
#define ll long long
#define LF dp.front()
#define RF dp.back()
using namespace std;
const int MAXN=4e5+5;
const ll inf=1e18;
int n,a[MAXN],st[MAXN],v[MAXN],w[MAXN];
ll sv[MAXN];
bool vs[MAXN];
int hd=1,tl=0,tg=0;
struct info {
	int len,tg; ll val;
};
deque <info> dp;
ll qryL(int p=hd) {
	if(dp.empty()) return -inf;
	return LF.val+sv[p-(tg-LF.tg)]-sv[p];
}
ll qryR() {
	if(dp.empty()) return -inf;
	return RF.val+sv[tl-(tg-RF.tg)]-sv[tl];
}
void popL() { if(!--LF.len) dp.pop_front(); }
void popR() { if(!--RF.len) dp.pop_back(); }
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i) {
		cin>>a[i];
		if(~a[i]) vs[a[i]]=true;
	}
	for(int i=1;i<=n;++i) {
		cin>>w[i];
		if(!vs[i]) st[++tl]=i,v[tl]=w[i];
	}
	for(int i=tl;i>=0;--i) sv[i]=sv[i+1]+v[i];
	ll pr=0; dp.push_back({tl,tg,-inf});
	for(int i=1,pmx=0;i<=n;++i) {
		if(a[i]==-1) {
			ll z=qryL(); ++tg;
			if(dp.size()) popR(),dp.push_front({1,tg,z});
			int sz=0;
			while(dp.size()&&qryL(hd+LF.len-1)<pr) hd+=LF.len,sz+=LF.len,dp.pop_front();
			if(dp.size()) {
				int l=1,r=LF.len,d=0;
				while(l<=r) {
					int mid=(l+r)>>1;
					if(qryL(hd+mid-1)<pr) d=mid,l=mid+1;
					else r=mid-1;
				}
				sz+=d,hd+=d,LF.len-=d;
			}
			if(sz) dp.push_front({sz,tg,pr}),hd-=sz;
			if(hd<tg) popL(),++hd;
		} else if(a[i]>pmx) {
			ll mx=pr; pmx=a[i];
			for(;hd<=tl&&st[hd]<a[i];++hd) mx=max(mx,qryL()+v[hd]),popL();
			pr=(hd>tg?mx+w[a[i]]:-inf);
		}
		cout<<max(pr,qryR()+v[tl])<<" \n"[i==n];
	}
	return 0;
}