题解：CF2150C Limited Edition Shop

liuzimomo · 2025-10-14 19:56:02 · 题解

CF2150C 题解

题面简述：你有 n 种商品，每种都有自己的价值且都只有一个，Alice和Bob对这些商品都有各自的偏好排序。接下来每次会来Alice或Bob中的一个人，买下在售的他/她最喜欢的商品，直到所有商品被卖出。求Alice买的所有商品的价值之和最大值。

将每个商品映射为一个点，横坐标为这个商品在Alice心中的排名（第几喜欢），纵坐标为这个商品在Bob心中的排名，按照这种方式把这些商品映射到平面直角坐标系上。则Alice买下一件商品的必要条件是把对应点的左上角所有店对应的商品全买下来，因为显然Alice买下某件商品和右侧点（即Alice排名靠后的商品）没有任何关系，而左下角的点可以让Bob买掉，但如果让Bob买左上角的点对应的商品则一定会先把当前商品买下来。也即：

由于选了蓝色三角点，其左上角（红色区域）包含的两个黄色三角点也必须选上。可以通过构造证明满足上述条件的购买方案都是可行的。

此时我们把这个问题转化为了选点问题。

开始设计DP状态。先将所有的点按照横坐标排序，记 dp_{i,j} 表示考虑前 i 个点，所有前 i 个点当中纵坐标大于等于 j 的点都被选了，且 j 是满足上述条件的最小值，在这种情况下选点点权的最大值。初始时 dp_{0,1}=0,dp_{0,i}=-\infty。

设第 i+1 个点纵坐标为 y，价值为 v，思考会有哪些情况：

当前 j\gt y，则说明该点左上角的点没选完（在本题中不会出现两点横坐标或纵坐标相等，但我们认为这块区域的横坐标和纵坐标可以和该点相同），此时不能选这个点且 j 也不会有任何变化，有 dp_{i+1,j}\leftarrow dp_{i,j}(j\gt y)。
当前 j\leq y，此时又有两种情况：
- 选择该点：则权值要加上 v，j 不会有变化，有 dp_{i+1,j}\leftarrow dp_{i,j}+v(j\leq y)。
- 不选：则权值不会有变化，但 j 会变成 y+1，有 dp_{i+1,y+1}\leftarrow dp_{i,j}(j\leq y)

注意到这三条转移都可以用线段树维护：取 1 到 y 区间最大值更新到 y+1 上，然后给 1 到 y 区间加 v。最终答案即为线段树全局最大值，涉及到区间加、单点更新、区间查询，时间复杂度 O(n\log{n})。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll tr[800005],laz[800005];
void add(int k,ll v){tr[k]+=v,laz[k]+=v;}
void pushdown(int k){
    int nex=k*2;
    add(nex,laz[k]),add(nex+1,laz[k]),laz[k]=0;
}
void build(int k,int l,int r){
    tr[k]=0xdfdfdfdfdfdfdfdf,laz[k]=0;
    if(l==r) return;
    int nex=k*2,mid=(l+r)/2;
    build(nex,l,mid),build(nex+1,mid+1,r);
}
void update1(int k,int l,int r,int x,ll v){
    if(l==r){tr[k]=max(tr[k],v);return;}
    pushdown(k);
    int nex=k*2,mid=(l+r)/2;
    if(x<=mid) update1(nex,l,mid,x,v);
    else update1(nex+1,mid+1,r,x,v);
    tr[k]=max(tr[nex],tr[nex+1]);
}
void update2(int k,int l,int r,int x,int y,ll v){
    if(x<=l&&r<=y){add(k,v);return;}
    pushdown(k);
    int nex=k*2,mid=(l+r)/2;
    if(x<=mid) update2(nex,l,mid,x,y,v);
    if(y>mid) update2(nex+1,mid+1,r,x,y,v);
    tr[k]=max(tr[nex],tr[nex+1]);
}
ll query(int k,int l,int r,int x,int y){
    if(x<=l&&r<=y) return tr[k];
    pushdown(k);
    int nex=k*2,mid=(l+r)/2;
    if(x<=mid&&y>mid) return max(query(nex,l,mid,x,y),query(nex+1,mid+1,r,x,y));
    if(x<=mid) return query(nex,l,mid,x,y);
    return query(nex+1,mid+1,r,x,y);
}
int n,a[200005],b[200005],v[200005],rk[200005];
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&v[i]);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        for(int i=1;i<=n;i++) scanf("%d",&b[i]),rk[b[i]]=i;
        build(1,1,n+1),update1(1,1,n+1,1,0);
        for(int i=1;i<=n;i++){
            int h=rk[a[i]];
            ll x=query(1,1,n+1,1,h);
            update1(1,1,n+1,h+1,x);
            update2(1,1,n+1,1,h,v[a[i]]);
        }
        printf("%lld\n",tr[1]);
    }
    return 0;
}