题解：CF2150C Limited Edition Shop
炸鸡块君
·
·
题解
阅读下面的内容前，读者应通过手玩样例和初步思考理解本题发生的是什么样的事情——两个人都在取同一个物品池里的物品，因此当前状态可以由 Alice 取了哪些物品和 Bob 取了哪些物品来决定。
考虑 $dp_j$ 如何由 $dp_{j-1}$ 转移过来，也就是 $a_j$ 如何被选，计 $pos=bpos[a_j]$ 表示 $a_j$ 在 $b$ 中下标，则 $a_j$ 有如下几种选法的情况：
1. $a_j$ 在此前已经被 Bob 选择：$i>pos,dp_{j,i}=dp_{j-1,i}$；
2. $a_j$ 在这一轮被 Bob 选择，此时 Bob 选的上一个东西有多种可能、需要枚举 Bob 上一个选的是 $b_k$ 物品的情况们：$dp_{j,pos}=\max_{k<pos} dp_{j-1,k}$；
3. $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}$ 即可。
```c++
#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;
}
```