差分、线段树

Solution 1：我是数据结构爱好者之力大砖飞。

使用动态开点线段树维护操作后的序列，记录位置在区间 $[l,r]$ 的人数 $cnt$ 以及每个人所在坐标的数值和 $sum$，通过操作让 $[l,r]$ 中的 $cnt$ 个人按从左到右的顺序移动到 $r-cnt+1,r-cnt+2,\cdots,r$ 位置的代价为 $cnt \times r - sum - \dfrac{(cnt - 1) \times cnt}{2}$，同理把所有人向左移动到到 $l,l+1,\cdots,l+cnt-1$ 的代价为 $sum - cnt \times l - \dfrac{(cnt-1) \times cnt}{2}$，可以快速计算。

使用 $x_i$ 表示第 $i$ 个人的当前位置，把第 $k$ 个人移动到位置 $p(x_k \leq p)$ 需要将 $[x_k+1,p]$ 里的所有人移动到 $p$ 右边，这可能需要 $p$ 右边的一些人移动来让出位置。二分被移动的人数 $mid$，如果区间 $[x_k,p+mid-1]$ 中的人数不超过 $mid$ 则合法。这里“合法”是说第 $k+mid-1$ 个人会和移动后的第 $k$ 个人在一个联通块里。

在线段树上二分可以做到 $O(\log V)$，具体地，求出位置在区间 $[x_k,p]$ 内的人数 $cnt$，然后找从 $p$ 开始包含了 $cnt$ 个空位置且右端点 $mid$ 最小的区间 $[p,mid]$。线段树只能做全局第 $k$ 大问题，计算出在 $p$ 之前的空位置数量 $bnt$，找到第 $cnt+bnt$ 个空位置就完成了。向左移动的情况同理。

移动完成后将 $[x_k,mid]$ 中的所有人搬到 $[p,mid]$，用区间赋值维护。操作导致若干个 $x_i$ 发生了变化，考虑使用线段树维护。由于每个人在序列中的相对位置不变，用线段树维护排序后 $x_i$ 的差分序列。

总体时间复杂度 $O(n \log V)$，空间复杂度 $O(n \log V)$，边界条件很多，代码非常难写。

#include<bits/stdc++.h>
using namespace std;
constexpr int ext=500'000,lim=101'000'000;
namespace dyn{
    struct Segment{int w,m,ls,rs;long long sum;}s[200'005*60];
    constexpr Segment emp=Segment{0,0,0,0,0ll};
    static int seg;
    void mark(int &u,int l,int r,int k){
        if(u==0) u=++seg;
        if((s[u].m=k)==-1) s[u].w=0,s[u].sum=0ll;
        else s[u].w=r-l+1,s[u].sum=1ll*(l+r)*(r-l+1)/2;
    }
    void pushdown(int u,int l,int r){
        int mid=(l+r)>>1;
        mark(s[u].ls,l,mid,s[u].m);
        mark(s[u].rs,mid+1,r,s[u].m);
        s[u].m=0;
    }
    void pushup(Segment &u,const Segment &ls,const Segment &rs){
        u.w=ls.w+rs.w,u.sum=ls.sum+rs.sum;
    }
    void update(int &u,int l,int r,int ql,int qr,int k){
        if(u==0) u=++seg;
        if(l>=ql&&r<=qr) return mark(u,l,r,k);
        int mid=(l+r)>>1;
        if(s[u].m) pushdown(u,l,r);
        if(ql<=mid) update(s[u].ls,l,mid,ql,qr,k);
        if(qr>mid) update(s[u].rs,mid+1,r,ql,qr,k);
        pushup(s[u],s[s[u].ls],s[s[u].rs]);
    }
    Segment query(int u,int l,int r,int ql,int qr){
        if(l>=ql&&r<=qr) return s[u];
        Segment ret=emp,ls=emp,rs=emp;
        int mid=(l+r)>>1;
        if(s[u].m) pushdown(u,l,r);
        if(ql<=mid) ls=query(s[u].ls,l,mid,ql,qr);
        if(qr>mid) rs=query(s[u].rs,mid+1,r,ql,qr);
        pushup(ret,ls,rs);
        return ret;
    }
    int frank(int u,int l,int r,int k){
        if(l==r) return l;
        int mid=(l+r)>>1;
        if(s[u].m) pushdown(u,l,r);
        if(k<=mid-l+1-s[s[u].ls].w) return frank(s[u].ls,l,mid,k);
        return frank(s[u].rs,mid+1,r,k-(mid-l+1-s[s[u].ls].w));
    }
}
namespace sta{
    struct Segment{int w,m;}s[800'005];
    void mark(int u,int l,int r,int k){
        s[u].w=(r-l+1)*k,s[u].m=k;
    }
    void pushdown(int u,int l,int r){
        int mid=(l+r)>>1;
        mark(u*2,l,mid,s[u].m);
        mark(u*2+1,mid+1,r,s[u].m);
        s[u].m=0;
    }
    void update(int u,int l,int r,int ql,int qr,int k){
        if(l>=ql&&r<=qr) return mark(u,l,r,k);
        int mid=(l+r)>>1;
        if(s[u].m) pushdown(u,l,r);
        if(ql<=mid) update(u*2,l,mid,ql,qr,k);
        if(qr>mid) update(u*2+1,mid+1,r,ql,qr,k);
        s[u].w=s[u*2].w+s[u*2+1].w;
    }
    int query(int u,int l,int r,int ql,int qr){
        if(l>=ql&&r<=qr) return s[u].w;
        int ret=0,mid=(l+r)>>1;
        if(s[u].m) pushdown(u,l,r);
        if(ql<=mid) ret+=query(u*2,l,mid,ql,qr);
        if(qr>mid) ret+=query(u*2+1,mid+1,r,ql,qr);
        return ret;
    }
}
int n,m,ro,a[200'005];
long long ans;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],a[i]+=ext;
    for(int i=1;i<=n;i++){
        dyn::update(ro,1,lim,a[i],a[i],1);
        sta::update(1,1,n,i,i,a[i]-a[i-1]);
    }
    cin>>m;
    for(int i=1;i<=m;i++){
        static int x,y,l,r,cnt,pos;
        cin>>x>>y,y+=ext;
        pos=sta::query(1,1,n,1,x);
        if(pos<y){
            cnt=y-1-dyn::query(ro,1,lim,1,y-1).w;
            cnt+=dyn::query(ro,1,lim,pos,y-1).w;
            r=dyn::frank(ro,1,lim,cnt);
            auto w=dyn::query(ro,1,lim,pos,r);
            ans+=1ll*w.w*r-w.sum-1ll*w.w*(w.w-1)/2;
            dyn::update(ro,1,lim,pos,y-1,-1);
            dyn::update(ro,1,lim,y,r,1);
            int las=0,nxt=0;
            if(x!=1) las=sta::query(1,1,n,1,x-1);
            if(x+(r-y)!=n) nxt=sta::query(1,1,n,1,x+(r-y)+1);
            sta::update(1,1,n,x,x,y-las);
            if(r!=y) sta::update(1,1,n,x+1,x+(r-y),1);
            if(nxt!=0) sta::update(1,1,n,x+(r-y)+1,x+(r-y)+1,nxt-r);
        }
        else if(pos>y){
            cnt=y-1-dyn::query(ro,1,lim,1,y-1).w+1;
            cnt-=dyn::query(ro,1,lim,y,pos).w-1;
            l=dyn::frank(ro,1,lim,cnt);
            auto w=dyn::query(ro,1,lim,l,pos);
            ans+=w.sum-1ll*w.w*l-1ll*w.w*(w.w-1)/2;
            dyn::update(ro,1,lim,y+1,pos,-1);
            dyn::update(ro,1,lim,l,y,1);
            int las=0,nxt=0;
            if(x-(y-l)!=1) las=sta::query(1,1,n,1,x-(y-l)-1);
            if(x!=n) nxt=sta::query(1,1,n,1,x+1);
            sta::update(1,1,n,x-(y-l),x-(y-l),l-las);
            if(l!=y) sta::update(1,1,n,x-(y-l)+1,x,1);
            if(nxt!=0) sta::update(1,1,n,x+1,x+1,nxt-y);
        }
    }
    cout<<ans<<'\n';
    return 0;
}

Solution 2：考虑每个人的坐标形成的序列，实时维护需要执行形如区间赋值差为 $1$ 的等差数列 $k,k+1,k+2,\cdots$ 的操作，在这种操作的同时维护区间和是困难的，并且区间覆盖 $+1$ 等差数列也是困难的。

采取一个整体二分的手法，将 $a_i$ 减去 $i$ 从而把单调上升序列转化为单调不降序列，在转化之后区间赋值 $+1$ 等差数列的操作变为平凡的区间赋值操作。引用一下上文。

使用 $x_i$ 表示第 $i$ 个人的当前位置，把第 $k$ 个人移动到位置 $p(x_k \leq p)$ 需要将 $[x_k+1,p]$ 里的所有人移动到 $p$ 右边，这可能需要 $p$ 右边的一些人移动来让出位置。二分被移动的人数 $mid$，如果区间 $[x_k,p+mid-1]$ 中的人数不超过 $mid$ 则合法。这里“合法”是说第 $k+mid-1$ 个人会和移动后的第 $k$ 个人在一个联通块里。

这也就是说，如果 $x_{k+mid-1} \leq p+mid-1$ 则 $mid$ 合法，二分得到最大的 $mid$ 就行。这一步可以在线段树上二分做到 $O(\log n)$，很可惜写完调完上面那坨代码之后我一点都不想这样做了。

对答案的贡献计算完毕后区间赋值维护序列，注意线段树查询 $x_i$ 位置之后要加上 $i$ 得到真实位置。由于可能会把点移动到负数位置，所有位置都要加上一个偏移量来保证计算过程中不出现负数位置。

总体时间复杂度 $O(n \log ^2 n)$。

#include<bits/stdc++.h>
using namespace std;
constexpr int ext=500'000;
struct Segment{int m,l,r;long long w;}s[800'005];
long long ans;
int n,m;
void build(int u,int l,int r){
    s[u].l=l,s[u].r=r;
    if(l==r) return;
    build(u*2,l,(l+r)/2);
    build(u*2+1,(l+r)/2+1,r);
}
void mark(int u,int k){
    s[u].m=k,s[u].w=1ll*k*(s[u].r-s[u].l+1);
}
void pushdown(int u){
    mark(u*2,s[u].m),mark(u*2+1,s[u].m),s[u].m=0;
}
void update(int u,int l,int r,int k){
    if(s[u].l>r||s[u].r<l) return;
    if(s[u].l>=l&&s[u].r<=r) return mark(u,k);
    if(s[u].m) pushdown(u);
    update(u*2,l,r,k),update(u*2+1,l,r,k);
    s[u].w=s[u*2].w+s[u*2+1].w;
}
long long query(int u,int l,int r){
    if(s[u].l>r||s[u].r<l) return 0ll;
    if(s[u].l>=l&&s[u].r<=r) return s[u].w;
    if(s[u].m) pushdown(u);
    return query(u*2,l,r)+query(u*2+1,l,r);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n,build(1,1,n);
    for(int i=1;i<=n;i++){
        static int x;
        cin>>x,x+=ext;
        update(1,i,i,x-i);
    }
    cin>>m;
    for(int i=1;i<=m;i++){
        static int x,y;
        cin>>x>>y,y+=ext;
        if(query(1,x,x)+x<y){
            int l=1,r=n-x+1,aim=1;
            while(l<=r){
                int mid=(l+r)>>1;
                if(query(1,x+mid-1,x+mid-1)+(x+mid-1)<=y+mid-1) aim=mid,l=mid+1;
                else r=mid-1;
            }
            ans+=1ll*aim*(y+aim-1)-(query(1,x,x+aim-1)+1ll*(x+(x+aim-1))*aim/2)-1ll*aim*(aim-1)/2;
            update(1,x,x+aim-1,y-x);
        }
        else if(query(1,x,x)+x>y){
            int l=1,r=x,aim=1;
            while(l<=r){
                int mid=(l+r)>>1;
                if(query(1,x-mid+1,x-mid+1)+(x-mid+1)>=y-mid+1) aim=mid,l=mid+1;
                else r=mid-1;
            }
            ans+=(query(1,x-aim+1,x)+1ll*((x-aim+1)+x)*aim/2)-1ll*aim*(y-aim+1)-1ll*aim*(aim-1)/2;
            update(1,x-aim+1,x,(y-aim+1)-(x-aim+1));
        }
    }
    cout<<ans<<'\n';
    return 0;
}