定义$L=2\cdot 10^{5}$，$g(x)=\sum_{i=1}^{n}|b_{i}-x|-|a_{i}-x|$，则合法当且仅当$\forall 0\le x\le L,g(x)\ge 0$，由此也可以得到$0\le a‘_{i}\le L$（证明略）
初始令$a‘_{i}=0$（即带来初始代价$\sum_{i=1}^{n}c_{i}a_{i}^{2}$）让$a‘_{i}$增加1的代价为$c_{i}(2(a‘_{i}-a_{i})+1)$，而这个操作的效果是让$g(x)$（$0\le x\le a‘_{i}$）减小1，让$g(x)$（$a‘_{i}<x\le L$）增加1（注意：以上$a‘_{i}$都指操作前的数）
定义$C_{i,x}$表示让$a‘_{i}=x$再增加1的代价，观察到$a‘_{i}$增加1的代价单调递增，同时效果单调递减（减小的范围增大，而增加的范围减小），因此我们不需要限制只有选择了$C_{i,x-1}$才能选择$C_{i,x}$，最优方案下自然会选择$C_{i,x-1}$
换言之，即有$o(nL)$个操作，操作之间没有限制，每一个操作有代价和效果，使得$g(x)\ge 0$
记$f_{x}$表示$x$操作使用次数，则有$g(x)=g‘(x)+\sum_{i=0}^{x-1}f(i)-\sum_{i=x}^{L}f(i)\ge 0$，令$S=\sum_{i=0}^{L}f(i)$，即$\sum_{i=x}^{L}f(i)\le \lfloor\frac{S+g‘(x)}{2}\rfloor$，记作$\lim_{x}$
$g‘(x)$很好求，然后有$S=\sum_{i=1}^{n}b_{i}$（即$\sum_{i=1}^{n}a‘_{i}=\sum_{i=1}^{n}b_{i}$），证明也比较简单，考虑$g(0)$和$g(L)$即可，因此$\lim_{x}$的值就可以确定，同时这也就是合法的充要条件
换言之，题意又简化为有$nL$个物品$C_{i,x}$，使得每一个后缀所选的物品数小于等于限制，最终选择$S$个物品，最小化费用和
不难得到一个$o(nL\log_{2}nL)$的做法，即维护一个可重集$S$，从后往前枚举$x$，将这对应的$n$个物品加入集合中，然后再从$S$中删除最大的若干个数直至集合大小小于等于$\lim_{x}$，最终剩下的$S$个元素和即为答案
但这样的复杂度仍然太大，我们需要利用$c_{i}$比较小的性质，考虑用以下方法来描述$S$：
记$mx$表示当前$S$中最大值，$sz$表示当前集合大小，$sum_{x}$表示数字$x$已经被删除的次数（特别的，对于$x>mx$的部分不保证正确性，但此时必然已经删光）
定义$calc(x,v)$表示求$\sum_{i=1}^{n}[C_{i,x}=v]$，可以通过预处理$o(5)$求出其关于$x$的后缀和和$v$的前缀和
令$sz+=\sum_{i=0}^{mx}calc(x,i)$，对$sz$与$\lim_{i}$大小关系分类讨论：
1.$sz\ge \lim_{i}$，则统计$\sum_{i=x}^{n}calc(i,mx)-sum_{mx}$，判断是否大于$sz-\lim_{i}$，若大于则直接删除$sz-\lim_{i}$个，否则全部删除并重复此过程
2.$sz<\lim_{i}$，先令$sum_{mx}=\sum_{i=x+1}^{n}calc(i,mx)$，然后若$calc(x,mx)\ge lim_{i}-sz$，则加入$\lim_{i}-sz$个（删除$calc(x,mx)-(\lim_{i}-sz)$个），否则全部加入并重复此过程
复杂度证明留坑
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define L 200000 4 #define N (L+5) 5 #define ll long long 6 int n,a[N],b[N],c[N],suma[11][N],sumb[N],sum[N*20]; 7 ll ans,g[N],lim[N]; 8 int calc(int x,int v){ 9 int ans=0; 10 for(int i=1;i<=5;i++){ 11 if ((v%i==0)&&(v%(2*i))){ 12 int s=x-(v/i-1)/2; 13 if ((s<0)||(s>L))continue; 14 if (!s)ans+=suma[i][0]; 15 else ans+=suma[i][s]-suma[i][s-1]; 16 } 17 } 18 return ans; 19 } 20 int calc_sufx(int x,int v){ 21 int ans=0; 22 for(int i=1;i<=5;i++) 23 if ((v%i==0)&&(v%(2*i))){ 24 int s=(v/i-1)/2; 25 if (L-s>=0){ 26 if (x-s<=0)ans+=suma[i][min(L-s,L)]; 27 else ans+=suma[i][min(L-s,L)]-suma[i][min(x-s-1,L)]; 28 } 29 } 30 return ans; 31 } 32 int divdn(int x,int y){ 33 if (x>=0)return x/y; 34 return (x-y+1)/y; 35 } 36 int calc_prev(int x,int v){ 37 int ans=0; 38 for(int i=1;i<=5;i++){ 39 int s=x-divdn(divdn(v,i)-1,2); 40 if (s>L)continue; 41 if (s<=0)ans+=suma[i][L]; 42 else ans+=suma[i][L]-suma[i][s-1]; 43 } 44 return ans; 45 } 46 int main(){ 47 scanf("%d",&n); 48 for(int i=1;i<=n;i++)scanf("%d",&a[i]); 49 for(int i=1;i<=n;i++)scanf("%d",&b[i]); 50 for(int i=1;i<=n;i++)scanf("%d",&c[i]); 51 for(int i=1;i<=n;i++)suma[c[i]][a[i]]++; 52 for(int i=1;i<=5;i++) 53 for(int j=1;j<=L;j++)suma[i][j]+=suma[i][j-1]; 54 ll s=0; 55 for(int i=1;i<=n;i++)s+=b[i]; 56 for(int i=1;i<=n;i++)sumb[b[i]]++; 57 for(int i=1;i<=L;i++)sumb[i]+=sumb[i-1]; 58 g[0]=s; 59 for(int i=1;i<=L;i++)g[i]=g[i-1]+sumb[i-1]-(n-sumb[i-1]); 60 for(int i=0;i<=L;i++)g[i]-=1LL*i*n; 61 for(int i=0;i<=L;i++)lim[i]=(s+g[i])/2; 62 int mx=0; 63 ll sz=0; 64 for(int i=L;i>=0;i--){ 65 sz+=calc_prev(i,mx); 66 while (sz>lim[i]){ 67 int las=calc_sufx(i,mx)-sum[mx+L*10]; 68 if (las>sz-lim[i]){ 69 sum[mx+L*10]+=sz-lim[i]; 70 sz=lim[i]; 71 break; 72 } 73 mx--; 74 sz-=las; 75 } 76 while (sz<lim[i]){ 77 mx++; 78 sum[mx+L*10]=calc_sufx(i+1,mx); 79 int las=calc(i,mx); 80 if (las>=lim[i]-sz){ 81 sum[mx+L*10]+=las-(lim[i]-sz); 82 sz=lim[i]; 83 break; 84 } 85 sz+=las; 86 } 87 } 88 for(int i=-L*10;i<=mx;i++)ans+=1LL*(calc_sufx(0,i)-sum[i+L*10])*i; 89 for(int i=1;i<=n;i++)ans+=1LL*c[i]*a[i]*a[i]; 90 printf("%lld",ans); 91 }