因为可以多次交换 所以一个物品是可以换到一定范围内的任何物品的
这个范围就是通过k来定的 只要两个数之间的差不超过k他们就属于同一个区间
因为当k单调不减的时候区间与区间之间是只会合并不会分割的
所以将k从小到大排序 然后每次k更新的时候 把那些小于k的间隔的两端的两个区间合并
然后更新答案 最后统一输出
#include<bits/stdc++.h>
using namespace std;#define int long long
#define endl '\n'const int N=4e5+10;
const int INF=0x3f3f3f3f3f3f3f;int n,m,q;
struct No{int val,type;
};
bool No_cmp(No a,No b){return a.val<b.val;
}
No a[N];struct Ask{int k,id;
}ask[N];
bool cmp_ask(Ask a,Ask b){return a.k<b.k;
}
int ans_ask[N];struct node{//间隙 int pre,nxt,siz;//前后的区间 当前断开的长度
};
bool operator < (const node a,const node b){return a.siz>b.siz;
}
priority_queue<node> qu;int fa[N];
int lt[N];//每个数最开始属于哪个块
int lt_cnt;
int add_cnt[N];
int en[N];//连通块结尾
int lcnt[N];//每个连通块里面有几个a
int ans=0;
int ck;int find(int k){if(fa[k]==k)return k;return fa[k]=find(fa[k]);
}signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>m>>q;for(int i=1;i<=n+m;i++)cin>>a[i].val,a[i].type=(i>n);sort(a+1,a+n+m+1,No_cmp);for(int i=1;i<=q;i++){cin>>ck;ask[i]={ck,i};}sort(ask+1,ask+q+1,cmp_ask);int pr=1;lt_cnt=1;fa[1]=1;lt[1]=1;for(int i=2;i<=n+m;i++){lt[i]=lt_cnt;if(a[i].val-a[i-1].val>ask[1].k){en[lt_cnt]=i-1;lt_cnt++;fa[lt_cnt]=lt_cnt;lt[i]=lt_cnt;qu.push({lt_cnt-1,lt_cnt,a[i].val-a[i-1].val});}}en[lt_cnt]=n+m;for(int i=1;i<=n+m;i++){add_cnt[i]=add_cnt[i-1]+a[i].val;if(a[i].type==0){lcnt[lt[i]]++;}}for(int i=1;i<=lt_cnt;i++){ans+=add_cnt[en[i]]-add_cnt[en[i]-lcnt[i]+1-1];}for(int i=1;i<=q;i++){int k=ask[i].k;int id=ask[i].id;while(!qu.empty()){node top=qu.top();int pre=top.pre;int nxt=top.nxt;int siz=top.siz;if(siz>k)break;int fn=find(nxt);int fp=find(pre);ans-=(add_cnt[en[fp]]-add_cnt[en[fp]-lcnt[fp]+1-1]);ans-=(add_cnt[en[fn]]-add_cnt[en[fn]-lcnt[fn]+1-1]);fa[fp]=fn;lcnt[fn]+=lcnt[fp];ans+=(add_cnt[en[fn]]-add_cnt[en[fn]-lcnt[fn]+1-1]);qu.pop();}ans_ask[id]=ans;}for(int i=1;i<=q;i++){cout<<ans_ask[i]<<endl; }return 0;
}