【CF799E】Aquarium decoration

题意：有n个物品，小A和小B各自喜欢其中的某些物品，一件物品可能既被小A喜欢又被小B喜欢，也可能既不被小A喜欢又不被小B喜欢。每个物品都有一个价格$c_i$，让你选出其中的m件物品，满足小A和小B都至少喜欢其中的k件，且总价格最小。

$n\le 2\times 10^5,c_i\le 10^9$

题解：我们把物品分成四部分：0,A,B,AB，并分别排序，然后我们枚举AB中选了i个。接着我们可以二分：在A,B,0中选择的价格最大的物品的价格mid，假设A中有a个数小于等于mid，则我们要从中选max(a,k)个，同理B中选max(b,k)个，C中选m-i-max(a,k)-max(b,k)个。发现这个显然是可以二分的。如果把二分放到线段树上的话，则时间复杂度是$O(n\log n)$。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #define lson x<<1#define rson x<<1|1using namespace std;typedef long long ll;const int maxn=200010;ll ans;int n,m,k,na,nb,nc,nd,N;int A[maxn],B[maxn],C[maxn],D[maxn],v[maxn],tag[maxn],p[maxn];int ca[maxn<<2],cb[maxn<<2],cd[maxn<<2],ta[maxn],tb[maxn],td[maxn];ll sa[maxn],sb[maxn],sd[maxn],ref[maxn];bool cmp(const int &a,const int &b){	return v[a]
         
          >1;	if(a<=mid)	insert(l,mid,lson,a,b,c);	else	insert(mid+1,r,rson,a,b,c);}ll query(int l,int r,int x,int a){	if(l==r)		return sa[max(ca[x],a)]+sb[max(cb[x],a)]+sd[cd[x]]-ref[l]*(max(ca[x],a)+max(cb[x],a)+cd[x]+k-a-m);	int mid=(l+r)>>1,t=max(ca[lson],a)+max(cb[lson],a)+cd[lson]+k-a;	if(t>=m)	return query(l,mid,lson,a);	return query(mid+1,r,rson,a);}void build(int l,int r,int x){	if(l==r)	{		ca[x]=ta[l],cb[x]=tb[l],cd[x]=td[l];		return ;	}	int mid=(l+r)>>1;	build(l,mid,lson),build(mid+1,r,rson);	ca[x]=ca[rson],cb[x]=cb[rson],cd[x]=cd[rson];}inline int rd(){	int ret=0,f=1;	char gc=getchar();	while(gc<'0'||gc>'9')	{if(gc=='-')	f=-f;	gc=getchar();}	while(gc>='0'&&gc<='9')	ret=ret*10+(gc^'0'),gc=getchar();	return ret*f;}int main(){	n=rd(),m=rd(),k=rd();	int i,a,b;	for(i=1;i<=n;i++)	v[i]=rd(),p[i]=i;	sort(p+1,p+n+1,cmp);	for(i=1;i<=n;i++)	{		if(i==1||v[p[i]]>ref[N])	ref[++N]=v[p[i]];		v[p[i]]=N;	}	a=rd();	for(i=1;i<=a;i++)	b=rd(),tag[b]|=1;	a=rd();	for(i=1;i<=a;i++)	b=rd(),tag[b]|=2;	for(i=1;i<=n;i++)	{		if(tag[i]==0)	D[++nd]=ref[v[i]],td[v[i]]++;		if(tag[i]==1)	A[++na]=ref[v[i]],ta[v[i]]++;		if(tag[i]==2)	B[++nb]=ref[v[i]],tb[v[i]]++;		if(tag[i]==3)	C[++nc]=ref[v[i]];	}	sort(A+1,A+na+1),sort(B+1,B+nb+1),sort(C+1,C+nc+1),sort(D+1,D+nd+1);	for(i=1;i<=N;i++)	ta[i]+=ta[i-1],tb[i]+=tb[i-1],td[i]+=td[i-1];	for(i=1;i<=na;i++)	sa[i]=sa[i-1]+A[i];	for(i=1;i<=nb;i++)	sb[i]=sb[i-1]+B[i];	for(i=1;i<=nd;i++)	sd[i]=sd[i-1]+D[i];	ll sum=0;	ans=1ll<<60;	build(0,N,1);	for(i=0;i<=min(nc,m);i++)	{		sum+=C[i];		if(min(na,nb)>=k-i&&2*k-i<=m&&i+na+nb+nd>=m)			ans=min(ans,sum+query(0,N,1,k-i));	}	if(ans==1ll<<60)	puts("-1");	else	printf("%lld",ans);	return 0;}