Trước hết bạn cần đọc về XOR basis ở blog này.

Trong bài toán này có thể thấy rằng mỗi bộ sưu tập là một cơ sở (basis) của không gian vector con của ~\mathbb{Z}_2^{64}~ chứa các vector ~c_1,c_2,\ldots,c_n~.

Một số định nghĩa:

• Một vector v được gọi là tổ hợp tuyến tính của tập ~S=\{s_1,s_2,\ldots,s_k\}~ nếu tồn tại cách biểu diễn ~v=c_1s_1\oplus c_2s_2\oplus\ldots c_ks_k~ sao cho ~c_i\in \{0,1\}~.
• Tập vector ~S~ được gọi là độc lập tuyến tính nếu vector ~0~ không phải một tổ hợp tuyến tính của ~S~.
• ~\text{span}(S)=\text{span}\{s_1,s_2,\ldots,s_k\}~ là không gian vector chứa tất cả các tổ hợp tuyến tính của tập ~S~. Nếu ~S~ độc lập tuyến tính thì ~S~ được gọi là một cơ sở của không gian vector trên.

Một số tính chất: Giả sử các tập vector trong ~\text{span}~ dưới đây độc lập tuyến tính.

1. Nếu ~\text{span}\{u_1,u_2,\ldots,u_k,x\}=\text{span}\{v_1,v_2,\ldots,v_k,x\}~ thì ~\text{span}\{u_1,u_2,\ldots,u_k\}=\text{span}\{v_1,v_2,\ldots,v_k\}~.
2. Nếu ~\text{span}\{u_1,u_2,\ldots,u_k\}=\text{span}\{v_1,v_2,\ldots,v_k\}=V~ và ~u_i\ne v_j~ với mọi ~i,j~ thì tồn tại ~i,j~ sao cho ~\text{span}\{u_1,u_2,\ldots,u_{i-1},v_j,u_{i+1},\ldots,u_k\}=V~ (thay ~u_i~ bởi ~v_j~).
3. Nếu ~\text{span}\{u_1,u_2,\ldots,u_k,x\} = \text{span}\{u_1,u_2,\ldots,u_k,y\}=V~ thì ~\text{span}\{v_1,v_2,\ldots,v_k,x\}=V\Leftrightarrow \text{span}\{v_1,v_2,\ldots,v_k,y\}=V~ với mọi tập.

Từ tính chất ~3~ ta có thể đơn giản hoá điều kiện của bài toán: Gọi ~f_i~ là giá của món đồ ~i~ sau khi thay đổi.

• Xét tập ~A~, nếu thay ~a_i~ bởi ~c_j~ mà ~A~ vẫn là một cơ sở thì ~f_{a_i}\le f_j~ sau khi thay đổi giá.
• Xét tập ~B~, nếu thay ~b_i~ bởi ~c_j~ mà ~B~ vẫn là một cơ sở thì ~f_{b_i}\ge f_j~ sau khi thay đổi giá.

Ta xây dựng một đồ thị ~G~, với mỗi ~x,y~ ta có cạnh từ ~x~ đến ~y~ nếu ~f_x\le f_y~.

Đây là bài toán "Partially Ordered Isotonic Regression". Một lời giải của bài toán này được đề cập trong blog codeforces SRM 720. Lưu ý rằng ta cần sửa công thức "đạo hàm" trong bài toán.

Code mẫu

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define fi first
#define se second
typedef unsigned long long u64;
typedef long long ll;
const ll INF=1e16;
struct Dinic{
    struct edge{
        int to;ll cap;int rev;
        edge(int to,ll cap,int rev): to(to),cap(cap),rev(rev) {} 
    };
    vector<edge>g[1005];
    int n,lev[1005],iter[1005];
    bool vis[1005];
    void init(int N){
        n=N;for(int i=1;i<=N;i++)g[i].clear();
    }
    void addedge(int u,int v,ll w){
        g[u].push_back(edge(v,w,g[v].size()));
        g[v].push_back(edge(u,0,g[u].size()-1));
    }
    void bfs(int s){
        memset(lev,-1,(n+2)<<2);
        queue<int>que;lev[s]=0,que.push(s);
        while(!que.empty()){
            int u=que.front();que.pop();
            for(int i=0;i<g[u].size();i++){
                edge x=g[u][i];
                if(x.cap==0||lev[x.to]>=0)continue;
                lev[x.to]=lev[u]+1,que.push(x.to);
            }
        }
    }
    ll dfs(int x,int t,ll F){
        if(x==t)return F;
        for(int &i=iter[x];i<g[x].size();i++){
            edge &e=g[x][i];
            if(lev[e.to]>lev[x]&&e.cap>0){
                ll d=dfs(e.to,t,min(F,e.cap));
                if(d>0){e.cap-=d;g[e.to][e.rev].cap+=d;return d;}
            }
        }
        return 0;
    }
    ll maxflow(int s,int t){
        ll ret=0;for(;;){
            bfs(s);if(lev[t]<0)return ret;
            memset(iter,0,(n+2)<<2);ll f;
            while((f=dfs(s,t,INF))>0)ret+=f;  
        }
    }
    vector<pii>getCut(int s,int t){
        vector<pii>v;
        bfs(s);
        for(int i=1;i<=n;i++)if(lev[i]!=-1)
            for(int j=0;j<g[i].size();j++){
                edge E=g[i][j];
                if(lev[E.to]==-1&&E.cap==0&&(i==s||E.to==t))
                    v.push_back({i,E.to});
            }
        return v;
    }
}Gr;
int n,m,v[1005],A[70],B[70];
u64 c[1005];bool ina[1005],inb[1005];
vector<int>g[1005];ll ans;
int id[1005],tg[1005],cnt;
ll ta[1005],tb[1005];bool res[1005];
void sol(int l,int r,vector<int>vec){
    if(vec.empty())return;
    if(r-l==1){
        int tot=2,S=1,T=2;++cnt;
        for(int i=0;i<vec.size();i++){
            int x=vec[i];
            ta[x]=(ll)(v[x]-l)*(v[x]-l),tb[x]=(ll)(v[x]-r)*(v[x]-r);
            id[x]=++tot,tg[x]=cnt;
        }
        Gr.init(tot);
        for(int i=0;i<vec.size();i++){
            int x=vec[i];
            ll d=tb[x]-ta[x];
            if(d<0)Gr.addedge(S,id[x],-d),res[id[x]]=1;
            else Gr.addedge(id[x],T,d),res[id[x]]=0;
            for(int j=0;j<g[x].size();j++){
                int y=g[x][j];
                if(tg[y]==cnt)Gr.addedge(id[x],id[y],INF);
            }
        }
        Gr.maxflow(S,T);
        vector<pii>CUT=Gr.getCut(S,T);
        for(int i=0;i<CUT.size();i++){
            pii x=CUT[i];
            if(x.fi==S)res[x.se]=0;
            if(x.se==T)res[x.fi]=1;
        }
        for(int i=0;i<vec.size();i++){
            int x=vec[i];
            if(res[id[x]]==0)ans+=ta[x];
            if(res[id[x]]==1)ans+=tb[x];
        }
        return;
    }
    int md=(l+r)>>1,tot=2,S=1,T=2;++cnt;
    for(int i=0;i<vec.size();i++)id[vec[i]]=++tot,tg[vec[i]]=cnt;
    Gr.init(tot);
    for(int i=0;i<vec.size();i++){
        int x=vec[i];ll d=2*(md-v[x]);
        if(d<0)Gr.addedge(S,id[x],-d),res[id[x]]=1;
        else Gr.addedge(id[x],T,d),res[id[x]]=0;
        for(int j=0;j<g[x].size();j++){
            int y=g[x][j];
            if(tg[y]==cnt)Gr.addedge(id[x],id[y],INF);
        }
    }
    Gr.maxflow(S,T);
    vector<pii>CUT=Gr.getCut(S,T);
    for(int i=0;i<CUT.size();i++){
        pii x=CUT[i];
        if(x.fi==S)res[x.se]=0;
        if(x.se==T)res[x.fi]=1;
    }
    vector<int>vl,vr;
    for(int i=0;i<vec.size();i++){
        int x=vec[i];
        if(res[id[x]]==0)vl.push_back(x);
        if(res[id[x]]==1)vr.push_back(x);
    }
    sol(l,md,vl),sol(md,r,vr);
}
u64 bsa[64],bsb[64];
void ins(u64 *a,u64 x){
    for(int i=63;~i;i--)if((x>>i)&1){
        if(!a[i]){a[i]=x;break;}
        x^=a[i];
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%llu",&c[i]);
    for(int i=1;i<=n;i++)scanf("%d",&v[i]);
    for(int i=1;i<=m;i++)scanf("%d",&A[i]),ina[A[i]]=1;
    for(int i=1;i<=m;i++)scanf("%d",&B[i]),inb[B[i]]=1;
    for(int i=1;i<=m;i++){
        for(int j=0;j<64;j++)bsa[j]=bsb[j]=0;
        for(int j=1;j<=m;j++)if(i!=j)
            ins(bsa,c[A[j]]),ins(bsb,c[B[j]]);
        for(int j=1;j<=n;j++){
            u64 va=c[j],vb=c[j];
            for(int k=63;~k;k--){
                if((va^bsa[k])<va)va^=bsa[k];
                if((vb^bsb[k])<vb)vb^=bsb[k];
            }
            if(va&&!ina[j])g[A[i]].push_back(j);
            if(vb&&!inb[j])g[j].push_back(B[i]);
        }
    }
    vector<int>vec;
    for(int i=1;i<=n;i++)vec.push_back(i);
    sol(0,1e6,vec);printf("%lld",ans);
}