题解
将所有物品分成四类,分别为两人共同喜欢的,只有一人喜欢的,没人喜欢的。
首先,先从两人共同喜欢的物品里找出 \(k\) 个,这时,就要从剩余的找出 \(\rm m-k\) 个,而且是最小的。
用一棵权值线段树维护,因为值域太大,所以离散化或动态开点。
之后,指向共同喜欢的物品数量的指针递减,直至 \(0\) 同时增加选取其它物品的量,删除选了的,加上没选的。
因为指针单调递减,所以复杂度为 \(\mathcal O\rm (nlogn)\)
Code
#include<bits/stdc++.h>
#define ri register signed
#define p(i) ++i
using namespace std;
namespace IO{
char buf[1<<21],*p1=buf,*p2=buf;
#define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++
template<typename T>inline void read(T &x) {
ri f=1;x=0;register char ch=gc();
while(ch<'0'||ch>'9') {if (ch=='-') f=0;ch=gc();}
while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
x=f?x:-x;
}
}
using IO::read;
namespace nanfeng{
#define pb(x) push_back(x)
#define FI FILE *IN
#define FO FILE *OUT
template<typename T>inline T cmax(T x,T y) {return x>y?x:y;}
template<typename T>inline T cmin(T x,T y) {return x>y?y:x;}
typedef long long ll;
static const int N=2e5+7,INF=1e9;
int v[N],vis1[N],vis2[N],a,b,n,m,k,nm;
ll sum,ans=1e18;
vector<int> lv[3];
inline int cmp(int x,int y) {return v[x]<v[y];}
struct Seg{
#define ls(x) T[x].l
#define rs(x) T[x].r
struct segmenttree{int nm,l,r;ll sum;}T[N<<6];
int st[N<<6],cnt,tot,rt;
inline void up(int x) {
T[x].nm=T[ls(x)].nm+T[rs(x)].nm;
T[x].sum=T[ls(x)].sum+T[rs(x)].sum;
}
inline int New() {return cnt?st[cnt--]:p(tot);}
inline void Del(int &x) {st[p(cnt)]=x;x=0;}
void update(int &x,int p,int l,int r) {
if (!x) x=New();
if (l==r) return (void)(T[x].sum+=p,p(T[x].nm));
int mid(l+r>>1);
if (p<=mid) update(ls(x),p,l,mid);
else update(rs(x),p,mid+1,r);
up(x);
}
void del(int &x,int p,int l,int r) {
if (l==r) {
--T[x].nm,T[x].sum-=p;
if (!T[x].nm) Del(x);
return;
}
int mid(l+r>>1);
if (p<=mid) del(ls(x),p,l,mid);
else del(rs(x),p,mid+1,r);
up(x);
}
ll query(int x,int siz,int l,int r) {
if (!x) return 0;
if (l==r) return (ll)l*(ll)siz;
int mid(l+r>>1);
ll res(0);
if (T[ls(x)].nm>=siz) res+=query(ls(x),siz,l,mid);
else res+=T[ls(x)].sum+query(rs(x),siz-T[ls(x)].nm,mid+1,r);
return res;
}
}T;
inline int main() {
// FI=freopen("nanfeng.in","r",stdin);
// FO=freopen("nanfeng.out","w",stdout);
read(n),read(m),read(k);
if (m<k) {puts("-1");return 0;}
for (ri i(1);i<=n;p(i)) read(v[i]);
read(a);
for (ri i(1),id;i<=a;p(i)) read(id),vis1[id]=1;
read(b);
for (ri i(1),id;i<=b;p(i)) read(id),vis2[id]=1;
for (ri i(1);i<=n;p(i)) {
if (vis1[i]&&vis2[i]) lv[0].pb(i);
else if (vis1[i]) lv[1].pb(i);
else if (vis2[i]) lv[2].pb(i);
else T.update(T.rt,v[i],1,INF);
}
sort(lv[0].begin(),lv[0].end(),cmp);
sort(lv[1].begin(),lv[1].end(),cmp);
sort(lv[2].begin(),lv[2].end(),cmp);
ri bc=cmin((int)lv[0].size(),k),fr=1;
ri siz1=lv[1].size(),siz2=lv[2].size();
if (bc+siz1<k) {puts("-1");return 0;}
if (bc+siz2<k) {puts("-1");return 0;}
for (ri i(0);i<bc;p(i)) sum+=v[lv[0][i]],p(nm);
while(fr+bc<=k) sum+=v[lv[1][fr-1]],sum+=v[lv[2][fr-1]],nm+=2,p(fr);
for (ri i(fr);i<=siz1;p(i)) T.update(T.rt,v[lv[1][i-1]],1,INF);
for (ri i(fr);i<=siz2;p(i)) T.update(T.rt,v[lv[2][i-1]],1,INF);
if (nm>m) {puts("-1");return 0;}
ans=cmin(ans,sum+T.query(T.rt,m-nm,1,INF));
bc-=1,nm-=1;
if (bc>=0) T.update(T.rt,v[lv[0][bc]],1,INF),sum-=v[lv[0][bc]];
while(bc>=0&&bc+siz1>=k&&bc+siz2>=k) {
while(fr+bc<=k) {
sum+=(ll)v[lv[1][fr-1]]+(ll)v[lv[2][fr-1]];
T.del(T.rt,v[lv[1][fr-1]],1,INF);
T.del(T.rt,v[lv[2][fr-1]],1,INF);
nm+=2;
p(fr);
}
if (nm>m) break;
ans=cmin(ans,sum+T.query(T.rt,m-nm,1,INF));
--bc,--nm;
if (bc>=0) T.update(T.rt,v[lv[0][bc]],1,INF),sum-=v[lv[0][bc]];
}
printf("%lld\n",ans);
return 0;
}
}
int main() {return nanfeng::main();}