【题解】[NOI2019] 序列 贪心模拟费用流 —Qiuly

#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=1e6+5;
ll ans,v1,v2,v3,maxv;
int T,n,K,L,c1,c2,res,a[N],b[N],s[N],id[N];
bool cmp_a(int x,int y) {return a[x]>a[y];}
bool cmp_b(int x,int y) {return b[x]>b[y];}
struct Node_a{int id;bool operator < (const Node_a x) const {return a[id]<a[x.id];}}tmpa;
struct Node_b{int id;bool operator < (const Node_b x) const {return b[id]<b[x.id];}}tmpb;
struct Node_c{int id;bool operator < (const Node_c x) const {return a[id]+b[id]<a[x.id]+b[x.id];}}tmpc;
priority_queue<Node_a> lora,nofa;
priority_queue<Node_b> lorb,nofb;
priority_queue<Node_c> lorc;

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x; 
}

void clear_heap() {
    v1=v2=v3=c1=c2=res=0;
    while(!lora.empty()) lora.pop();while(!lorb.empty()) lorb.pop();while(!lorc.empty()) lorc.pop();
    while(!nofa.empty()) nofa.pop();while(!nofb.empty()) nofb.pop();
}

int main() {
    freopen("sequence.in","r",stdin);
    freopen("sequence.out","w",stdout);
    IN(T);while(T--) {
        IN(n),IN(K),IN(L),ans=0;
        for(int i=1;i<=n;++i) IN(a[i]);
        for(int i=1;i<=n;++i) IN(b[i]);
        for(int i=1;i<=n;++i) s[i]=0,id[i]=i;
        sort(id+1,id+1+n,cmp_a);for(int i=1;i<=K-L;++i) s[id[i]]|=1,ans+=a[id[i]];
        sort(id+1,id+1+n,cmp_b);for(int i=1;i<=K-L;++i) s[id[i]]|=2,ans+=b[id[i]];
        clear_heap();
        for(int i=1;i<=n;++i) {
            tmpa.id=tmpb.id=tmpc.id=i;
            if(!s[i]) lora.push(tmpa),lorb.push(tmpb),lorc.push(tmpc);
            else if(s[i]==1) lorb.push(tmpb),nofb.push(tmpb);
            else if(s[i]==2) lora.push(tmpa),nofa.push(tmpa);
            else ++res;
        }
        while(L--) {
            while(!lora.empty()&&(s[lora.top().id]&1)) lora.pop();
            while(!nofa.empty()&&(s[nofa.top().id]^2)) nofa.pop();
            while(!lorb.empty()&&(s[lorb.top().id]&2)) lorb.pop();
            while(!nofb.empty()&&(s[nofb.top().id]^1)) nofb.pop();
            while(!lorc.empty()&&s[lorc.top().id]) lorc.pop();
            if(res) {
                int i=lora.top().id,j=lorb.top().id;
                ans+=a[i]+b[j],--res,s[i]|=1,s[j]|=2;
                if(s[i]^3) tmpb.id=i,nofb.push(tmpb);
                if(s[j]^3) tmpa.id=j,nofa.push(tmpa);
                if(i==j) ++res;
                else {if(s[i]==3)++res;if(s[j]==3)++res;}
                continue;
            }
            int i1,i2,i3,j1,j2;
            if(!nofb.empty()) i1=lora.top().id,j1=nofb.top().id,v1=a[i1]+b[j1],c1=(s[i1]==2)?1:0;
            if(!nofa.empty()) i2=lorb.top().id,j2=nofa.top().id,v2=b[i2]+a[j2],c2=(s[i2]==1)?1:0;
            if(!lorc.empty()) i3=lorc.top().id,v3=a[i3]+b[i3];
            maxv=max(v1,max(v2,v3)),ans+=maxv;
            if(v1==v2&&v1==maxv) {
                if(c1>c2) {s[i1]|=1,s[j1]|=2;if(s[i1]^3) nofb.push((Node_b){i1});else res++;}
                else {s[i2]|=2,s[j2]|=1;if(s[i2]^3) nofa.push((Node_a){i2});else res++;}
            } 
            else if(v1==maxv) {s[i1]|=1,s[j1]|=2;if(s[i1]^3) nofb.push((Node_b){i1});else res++;}
            else if(v2==maxv) {s[i2]|=2,s[j2]|=1;if(s[i2]^3) nofa.push((Node_a){i2});else res++;}
            else if(v3==maxv) lorc.pop(),s[i3]=3;
        }
        printf("%lld\n",ans);
    }
    return 0;
}