Codeforces 1053 E

原题链接：Codeforces 1053 E

一道线段树优化dp，想了好久，感觉很有代表性。

可以用$ pos[i]$表示$ i$在$ b$中的位置

用$ dp[i][j]$表示枚举到数组a的第i位，数组b的第j位时，此时的最大价值。

当由b选时，不需要管pos[a[i]]和j的相对位置，因为即使b已经选过了，也可以进行dp，此时b需要从$ [dp[i][1]，dp[i][pos[a[i]+1]]]$中选最大的赋给$ dp[i+1][pos[a[i]+1]$，代表此时i++，同时b选完了pos[a[i]]之前的所有值，面对pos[a[i]+1]。

$$
dp[i+1][pos[a[i]+1]=max(range(dp[i][1],dp[i][pos[a[i]+1]))
$$

为什么是pos[a[i]+1]而不是pos[a[i]]？因为b可以不选$ [dp[i][1],dp[i][pos[a[i]]]$中的任何值，然后选a[i]，故需要比较。

当由a选时，需要$ pos[a[i]]>=j$，此时a可以选a[i]。若a选，则有

$$
if(pos[a[i]>=j)dp[i+1][j]=dp[i][j]+v[a[i]]
$$

为什么不取max？因为枚举到 j 时，b不可能取a[i] ，故不取max，而是直接加。

这是一个n方的dp，显然我们需要优化。

优化也很好想，因为第一维的i可以滚动掉，当b选的时候，我们需要从$ [dp[1],dp[pos[a[i]+1]]$中选一个最大值赋给$ dp[pos[a[i]+1]$，当a选的时候，需要对$[dp[1],dp[pos[a[i]]]$区间加v[a[i]]。

操作为区间加和区间查询，使用线段树。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define endl "\n"
#define fr(i,n) for(int i=1;i<=n;i++)
#define vec vector<long long>
#define lowbit(x) ((x)&(-x))
#define vecp vector<pair<int,int>>
const int N=1e6+5;
const int MOD=998244353;
const int INF=1e18;
int n;
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
struct segment{
    struct seg{
        int l,r,mx,tag;
    }tr[4*N];
    void build(int pos,int l,int r){
        tr[pos]={l,r,0,0};
        if(l==r)return;
        int mid=l+r>>1;
        build(pos<<1,l,mid);
        build(pos<<1|1,mid+1,r);
    }
    void pushup(int pos){
        tr[pos].mx=max(tr[pos<<1].mx,tr[pos<<1|1].mx);
    }
    void pushdown(int x){//将懒标记下放到子节点
        if(tr[x].tag){
            tr[x<<1].tag+=tr[x].tag;
            tr[x<<1|1].tag+=tr[x].tag;
            tr[x<<1].mx+=tr[x].tag;
            tr[x<<1|1].mx+=tr[x].tag;
            tr[x].tag=0;
        }
    }
    void update(int l,int r,int x,int k){//区间修改
        if(l<=tr[x].l&&r>=tr[x].r){
            tr[x].mx+=k;
            tr[x].tag+=k;
        }
        else {
            pushdown(x);
            int mid=(tr[x].l+tr[x].r)>>1;
            if(l<=mid){
                update(l,r,x<<1,k);
            }
            if(r>mid){
                update(l,r,x<<1|1,k);
            }
            pushup(x);
        }
    }
    int query(int x,int l,int r){//区间查询
        if(l<=tr[x].l&&r>=tr[x].r)return tr[x].mx;
        pushdown(x);
        int mid=(tr[x].l+tr[x].r)>>1;
        int sum=-INF;
        if(l<=mid){
            sum=max(query(x<<1,l,r),sum);
        }
        if(r>mid){
            sum=max(query(x<<1|1,l,r),sum);
        }
        return sum;
    }
    void change(int now,int x,int val){// 单点修改
        if(tr[now].l==tr[now].r){
            tr[now].mx=val;
            return;
        }   
        int mid=(tr[now].l+tr[now].r)>>1;
        if(x<=mid){
            change(now<<1,x,val);
        }
        else {
            change(now<<1|1,x,val);
        }
        pushup(now);
    }
    void print(){
        fr(i,4*n){
            cout<<tr[i].l<<' '<<tr[i].r<<' '<<tr[i].mx<<endl;
        }
        cout<<endl;
    }
}segtree;
long long ksm(long long a, long long b) {
    long long res = 1;
    while(b) {
        if(b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}
inline void Add(int &x,int y){((x+=y)>=MOD)?(x-=MOD):0;}
int Mul(int x,int y){return (x*y+MOD)%MOD;}
void init(){
}
void solve(){
    cin>>n;
    vec v(n+2),a(n+2),b(n+2),pos(n+2);
    fr(i,n)cin>>v[i];
    fr(i,n)cin>>a[i];
    segtree.build(1,1,n+2);
    fr(i,n){
        cin>>b[i];
        pos[b[i]]=i;
    }
    fr(i,n){
        int idx=pos[a[i]];
        int cnt1=segtree.query(1,1,pos[a[i]]);
        int cnt2=segtree.query(1,pos[a[i]]+1,pos[a[i]]+1);
        int vi=v[a[i]];
        segtree.change(1,pos[a[i]]+1,max(cnt1,cnt2));
        segtree.update(1,pos[a[i]],1,v[a[i]]);
        // segtree.print();
    }
    cout<<segtree.query(1,1,n+2)<<endl;
    // segtree.print();
}
signed main(){ 
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}