电塔
电塔
减少题目限制，让代码更好写
题意为，有 \(n\) 个塔，初始每个塔在位置 \(x_i\)，求最小移动多少距离使得塔两两之间距离 \(>d\)。
显然，调整后塔的顺序不会改变，因此我们先将塔排序。
我们先将塔间距都调为 \(>d\)，然后贪心地进行调整。
方便起见，我们先将塔全部推到最左边，即 \(x'_1=0,x'_2=d , \cdots , x'_n=d\times (n-1)\)。这样我们只考虑将塔向右推。
考虑什么时候要推塔。
设 \(y_i\) 表示塔 \(i\) 还要走多远才能到达 \(x_i\)，若 \(x_i\) 在 \(now_i\) 左侧，\(y_i=0\)（因为塔不能向左推，向左推不仅一定不优，还可能出界） 。
从右往左遍历塔。
塔 \(i\) 往右推的时候可能会使右边的塔被迫右移，增加代价，若代价较小，则推塔，否则不推。推得越多，代价单调不减。
塔 \(i\) 最多主动推 \(y_i\) 距离，因为超过这个距离，塔 \(i\) 就不会提供贡献，而右边的塔贡献一定小于代价（否则之前就推了）。
记录数对 \((p_i,c_i)\)，表示代价为 \(p_i\) 的距离长 \(c_i\)，\(p\) 单调递增，每个塔操作时更新这些数对，时间复杂度 \(O(n^2)\)。
因为一个塔在单位距离最多贡献 \(2\)，所以计算答案最多取常数个数对。
但是考虑到 \(y_i\) 可能很大，更新为 \(O(n)\)，我们二分处理。
二分找到 \(y_i\) 最远能到达的区间，差分标记整个区间的 \(p\) 的加减，最后一块区间可能不完全包括，用优先队列记录标记。
获取答案时，顺便处理标记，区间内有部分区间标记的，将区间拆分。
可以证明一共只会有 \(O(n)\) 个区间，总时间复杂度 \(O(n\log n)\)。
细节较多 qwq 。
AC Code
#include<bits/stdc++.h>
#define sf scanf
#define pf printf
#define il inline
#define int ll
using namespace std;
typedef long long ll;
const int N=2e5+7;
const ll inf=1e18;
int t,n,d;
ll x[N];
ll y[N];
pair<int,ll> st[N*4];
ll C[N*4];
ll tag[N*4];
priority_queue<ll> tag2[N*4];
int top;
int m;
ll ans;
//bool cmp(ll a,ll b){ return a>b; }
int find(ll y){
int l=top+1,r=1;
while(l>r){
int mid=(l+r)>>1;
if(C[top]-C[mid-1]<=y){
l=mid;
}else{
r=mid+1;
}
}
return l;
}
signed main(){
// freopen("ex_ele3.in","r",stdin);
// freopen("ele2.out","w",stdout);
sf("%lld",&t);
while(t--){
m=0;
ans=0;
sf("%lld%lld",&n,&d);
for(int i=1;i<=n;i++){
sf("%lld",&x[i]);
}
sort(x+1,x+n+1);
for(int i=1;i<=n;i++){
y[i]=max((ll)0,1ll*(i-1)*d-x[i]);
ans+=y[i];
// pf("%lld ",y[i]);
y[i]=max(0ll,x[i]-1ll*(i-1)*d);
ans+=y[i];
// pf("%lld ",y[i]);
}
// pf("\n");
// pf("ans1 %lld\n",ans);
// while(!st.empty()) st.pop();
// st.push({0,inf});
memset(C,0,sizeof(C));
memset(tag,0,sizeof(tag));
for(int i=1;i<=top;i++){
while(!tag2[i].empty()) tag2[i].pop();
}
top=0;
st[++top]={0,inf};
C[top]=inf;
for(int i=n;i>=1;i--){
// pf("i %d\n",i);
// pf("m %d\n",m);
if(!y[i]){
m++;
}else{
ll cc=0;
pair<int,ll> now;
// stack<pair<int,ll> > st2;
// while(!st2.empty()) st2.pop();
int x=find(y[i]);
// if(x<=1) pf("aaaaaa\n");
// pf("x %d\n",x);
if(x<=top){
// pf("top %d\n",top);
tag[top]-=2;
tag[x-1]+=2;
}
ll k=y[i]-(C[top]-C[x-1]);
// pf("k %lld\n",k);
if(k)
tag2[x-1].push(k);
while(1){
// if(top>N*3) pf("越界！\n");
now=st[top];
int p=now.first;
ll c=now.second;
// pf("p c %d %lld\n",p,c);
// pf("top,tag[top] %d %lld\n",top,tag[top]);
p+=tag[top];
tag[top-1]+=tag[top];
tag[top]=0;
st[top]={p,c};
int tp=top;
if(!tag2[top].empty()){
C[top]=0;
top--;
while(!tag2[tp].empty()){
ll f=tag2[tp].top();
// pf("f %lld\n",f);
tag2[tp].pop();
ll res=c-f;
// pf("res %lld\n",res);
if(res){
st[++top]={p,res};
// pf("top %d\n",top);
C[top]=C[top-1]+res;
}
// pf("p %d\n",p);
p-=2;
c=f;
}
if(c){
st[++top]={p,c};
C[top]=C[top-1]+c;
}
// pf("p c %d %lld\n",p,c);
continue;
}
now=st[top];
p=now.first,c=now.second;
// pf("p c %d %lld\n",c,p);
if(p+m>=-1) break;
ans+=(p+m+1)*c;
// pf("ans %lld\n",ans);
cc+=c;
top--;
}
// pf("cc %lld\n",cc);
m++;
if(cc){
if(st[top].first==-m){
st[top].second+=cc;
C[top]+=cc;
}else{
st[++top]={-m,cc};
C[top]=C[top-1]+cc;
}
}
}
}
pf("%lld\n",ans);
}
}