题解：CF2150C Limited Edition Shop

阅读下面的内容前，读者应通过手玩样例和初步思考理解本题发生的是什么样的事情——两个人都在取同一个物品池里的物品，因此当前状态可以由 Alice 取了哪些物品和 Bob 取了哪些物品来决定。

dp_{j,i}

表示考虑到了 Alice 的第

j

件（第 $j$ 件不一定是 Alice 选）且 Bob 已选的最靠后物品是

b_i

的最大价值。

考虑

dp_j

如何由

dp_{j-1}

转移过来，也就是

a_j

如何被选，计

pos=bpos[a_j]

表示

a_j

在

b

中下标，则

a_j

有如下几种选法的情况：

$a_j$ 在此前已经被 Bob 选择： $i>pos,dp_{j,i}=dp_{j-1,i}$ ；
$a_j$ 在这一轮被 Bob 选择，此时 Bob 选的上一个东西有多种可能、需要枚举 Bob 上一个选的是 $b_k$ 物品的情况们： $dp_{j,pos}=\max_{k<pos} dp_{j-1,k}$ ；
$a_j$ 在这一轮被 Alice 选择： $i<pos,dp_{j,i}=dp_{j-1,i}+v_{a_j}$ 。

我们顺便发现了一个非常好的事情，上面三种情况所修改的

i

分别是

i>pos,i=pos,i<pos

，完全不交，于是考虑用线段树直接维护这一整行（即

dp_{j-1}

这行转移到

dp_j

这行，线段树下标为

i

处存的是

dp_{j,i}

）。

具体线段树的做法是：

情况 1 不用做，原样保留就行；
情况 2 先区间查 $[0,pos]$ （我的线段树里存了 $0$ ，即用了 build(1,0,n); 建树）的最大值，如果比当前 $pos$ 位置值更大就赋值给 $pos$ 位置；
情况 3 直接对 $[0,pos-1]$ 区间加 $v_{a_j}$ 即可。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<=(n);i++)
#define per(i,a,n) for(int i=(n);i>=(a);i--)
#define pb push_back
#define SZ(v) ((int)v.size())
#define fs first
#define sc second
#define all(x) (x.begin()),(x.end())
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
const ll B=1e16;
struct node{
	ll mx,lzy;
}tr[200010*4];
ll t,n,v[200010],a[200010],b[200010],bpos[200010];
void pushup(int p){
	tr[p].mx=max(tr[2*p].mx,tr[2*p+1].mx);
}
void addtag(int p,ll val){
	tr[p].mx+=val;
	tr[p].lzy+=val;
}
void build(int p,int l,int r){
	tr[p].lzy=0;
	if(l==r){
		tr[p].mx=(l?-B:0);
		return ;
	}
	int m=(l+r)>>1;
	build(2*p,l,m);
	build(2*p+1,m+1,r);
	pushup(p);
}
void pushdown(int p){
	if(tr[p].lzy){
		addtag(p*2,tr[p].lzy);
		addtag(p*2+1,tr[p].lzy);
		tr[p].lzy=0;
	}
}
void upd_add(int p,int l,int r,int L,int R,ll val){
	if(L<=l&&r<=R){
		addtag(p,val);
		return;
	}
	pushdown(p);
	int m=(l+r)>>1;
	if(L<=m) upd_add(p*2,l,m,L,R,val);
	if(R>m) upd_add(p*2+1,m+1,r,L,R,val);
	pushup(p);
}
void upd_mx(int p,int l,int r,int pos,ll val){
	if(l==r){
		tr[p].mx=val;
		return ;
	}
	pushdown(p);
	int m=(l+r)>>1;
	if(pos<=m) upd_mx(p*2,l,m,pos,val);
	else upd_mx(p*2+1,m+1,r,pos,val);
	pushup(p);
}
ll query(int p,int l,int r,int L,int R){
	if(L<=l&&r<=R){
		return tr[p].mx;
	}
	pushdown(p);
	int m=(l+r)>>1;
	ll ret=-1e16;
	if(L<=m) ret=max(ret,query(p*2,l,m,L,R));
	if(R>m) ret=max(ret,query(p*2+1,m+1,r,L,R));
	return ret;
}
int main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>t;
	while(t--){
		cin>>n;
		rep(i,1,n) cin>>v[i];
		rep(i,1,n) cin>>a[i];
		rep(i,1,n){
			cin>>b[i];
			bpos[b[i]]=i;
		}
		build(1,0,n);
		rep(i,1,n){
			ll pos=bpos[a[i]],val=v[a[i]];
			ll lst=query(1,0,n,0,pos);
			upd_add(1,0,n,0,pos-1,val);
			ll now=query(1,0,n,pos,pos);
			if(lst>now) upd_mx(1,0,n,pos,lst);
		}
		cout<<query(1,0,n,0,n)<<"\n";
	}
	return 0;
}

题解：CF2150C Limited Edition Shop

文章操作

相关推荐

评论

题解：CF2150C Limited Edition Shop