[CF1618G] TraderProblem
声明：此文是从我的一篇文章上截下来的，可能会有些不对的地方，欢迎再评论区中指出
思路
这题部分正解十分好想，先升序，相邻元素差小于 \(k\) 的可以一堆一堆地分。想到同一堆的可以来回交换，只需要把每一堆的前 \(x\) 个元素（批注： \(x\) 表示那一堆中自己的物品的个数），就是前 \(x\) 大的元素，把他们加起来就是答案。但是这题是多 \(k\) 一算时间直接炸了，所以就需要我们去优化一下。
优化是优化可动的东西，输入和排序就是动不了的，就算你再优化也优化不到哪里去。看到 \(q\) 次询问里面的东西，这就是需要优化的。
在线操作似乎有点慢，如果能从前面的询问“转移”过来就快了。考虑离线操作，把 \(k\) 从小到大排 ，看可不可以从小 \(k\) 向 大 \(k\) 转移（当然你也可以尝试可不可以从 大 \(k\) 向小 \(k\) 转移，我试过，似乎也有方法）
现在想象一下，把 \(b_{i}\) 想象为数轴上的一点的位置，那么 \(b_{i}\) 到 \(b_{i+1}\) 之间就会用空隙，这个空隙的长度为\(b_{i+1}-b_{i}\) （前面部分分已经升序排了，我们是在部分分的基础上扩展的）， \(k\) 就理解为你可以在两点之间铺一条长度为 \(k\) 的的桥，当然，桥没有空隙长就铺不了。那这不就是一条条链吗？随着 \(k\) 越变越大（桥长越变越大），一些空隙就可铺桥，所以就推出来了，\(k\) 变大就扫一遍数组，桥长够空隙长就铺桥。那其实这些链就会合并得越来越少。
想到“链”和“合并”，我们就会想到并查集，那其实这题就是点并查集的合并，顺便再维护点东西了。然后就A了。
代码
超丑代码，勿学
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e6+5;
struct node
{ll x,id;
}a[N],q[N];
bool cmp(node x,node y){return x.x<y.x;}
ll ecnt=1,ans,Ans[N],cnt[N],fa[N],l[N],r[N],sum[N];
struct doubao{ll x,L,R;}kx[N];
ll find(ll x){ return (fa[x]==x)?x:fa[x]=find(fa[x]);}
void merge(ll x,ll y)
{ll fx=find(x),fy=find(y);if(fx==fy) return ;fa[fx]=fy;ans=ans-(sum[r[fx]]-sum[r[fx]-cnt[fx]])-(sum[r[fy]]-sum[r[fy]-cnt[fy]]);cnt[fy]+=cnt[fx];l[fy]=min(l[fx],l[fy]),r[fy]=max(r[fx],r[fy]);ans+=(sum[r[fy]]-sum[r[fy]-cnt[fy]]);
}
int main()
{ll n,m,Q; cin >>n>>m>>Q;for (ll i=1;i<=n+m;i++){cin >>a[i].x;if (i<=n) a[i].id=1;else a[i].id=2; }for (ll i=1;i<=Q;i++) {cin >>q[i].x;q[i].id=i;}sort(a+1,a+n+m+1,cmp); sort(q+1,q+Q+1,cmp);for (ll i=1;i<=n+m;i++) sum[i]=sum[i-1]+a[i].x;for (ll i=1;i<=n+m;i++){l[i]=r[i]=fa[i]=i;if(i!=1) kx[i-1]={a[i].x-a[i-1].x,i-1,i};if (a[i].id==1) cnt[fa[i]]++,ans+=a[i].x;}sort(kx+1,kx+n+m,[](doubao x,doubao y){return x.x<y.x;});ll j=1;for (ll i=1;i<=Q;i++){while (j<=n+m-1 && kx[j].x<=q[i].x){merge(kx[j].L,kx[j].R); j++;}Ans[q[i].id]=ans;}for (ll i=1;i<=Q;i++) cout <<Ans[i]<<endl;return 0;
}
/*
一些东西：
并查集 e[i] 父亲为i的
1.左右边界
2.每个块内的属于1元素的数量
3. 前缀和
*/