题解：P16214 [ECUSTPC 2025] 午夜季风

lailai0916 · 2026-08-31 03:42:46 · 题解

题意简述

每次单点修改一个多重集合后，将所有元素任意排列。求所有不相邻位置对应元素之差的绝对值之和的最小值。

解题思路

记所有元素对的距离和为 D，排列中相邻元素的距离和为 A。每对元素恰好属于相邻或不相邻中的一类，所以目标值为 D-A。其中 D 与排列无关，问题转化为最大化 A。

将当前元素排序为 x_1\le x_2\le\dots\le x_n，并记相邻差为 g_t=x_{t+1}-x_t。若排列中的一条边连接 x_i 与 x_j，其中 i\le t<j，它的贡献就包含一次 g_t。设整条排列路径有 e_t 条边跨过切口 [1,t] 与 [t+1,n]。于是：

切口较小一侧包含 \min(t,n-t) 个点。路径中每个点的度数至多为 2，而整条路径仅有 n-1 条边。因此：

这个上界可以用大小元素交替排列达到。它也直接给出 A 的最大值。

令 k=\lfloor\frac{n}{2}\rfloor，最小的 k 项之和为 L，最大的 k 项之和为 R。

当 n=2k 时，中央切口最多被 n-1 条边跨过。其他切口都能达到两倍的较小侧点数。取排列 x_k,x_{2k},x_{k-1},x_{2k-1},\dots,x_1,x_{k+1}，每个切口都达到该上界。因此：

当 n=2k+1 时，中央两个切口的上界均为 2k。若二者同时达到上界，每条路径边都必须同时跨过两个切口。此时中位数无法接入路径。因此，其中一个切口至少少跨一次，其余切口仍能达到上界。两种交替排列可以分别让一个中央切口少跨一次。选择相邻差较小的一侧即可：

然后维护与排列无关的 D。插入一个值 x 前，设严格小于它的元素个数和元素和为 c_l,s_l。严格大于它的对应量为 c_r,s_r。新产生的距离为：

删除时，在数据结构中先移除该值，再减去它到剩余元素的距离。这样修改前后的 D 都可以直接更新。

所有修改离线读入后，将每个元素可能出现的值离散化。两棵树状数组分别维护各值的出现次数与元素和。次数树状数组可以倍增求第 i 小值。结合和树状数组，还能求最小若干项之和，从而得到 L、R 与中央相邻差。

所有测试数据的时间复杂度为 O((\sum n+\sum m)\log(\sum n+\sum m))，空间复杂度为 O(\sum n+\sum m)。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=100005;
const int M=200005;
int a[N],p[N],d[N],v[M],len;
ll res;
struct BIT
{
    ll c[M];
    void add(int u,ll v){while(u<=len){c[u]+=v;u+=u&-u;}}
    ll sum(int u){ll res=0;while(u){res+=c[u];u-=u&-u;}return res;}
}C,S;
int get_pos(int x){return lower_bound(v+1,v+len+1,x)-v;}
int kth(ll k)
{
    int u=0,bit=1;
    while((bit<<1)<=len)bit<<=1;
    for(int i=bit;i;i>>=1)
    {
        if(u+i<=len&&C.c[u+i]<k)
        {
            k-=C.c[u+i];
            u+=i;
        }
    }
    return u+1;
}
ll sum_k(int k)
{
    if(!k)return 0;
    int u=kth(k);
    ll cnt=C.sum(u-1);
    return S.sum(u-1)+(k-cnt)*v[u];
}
ll dist(int x)
{
    int u=get_pos(x);
    ll lc=C.sum(u-1),rc=C.sum(len)-C.sum(u);
    ll ls=S.sum(u-1),rs=S.sum(len)-S.sum(u);
    return 1LL*x*lc-ls+rs-1LL*x*rc;
}
void change(int x,int op)
{
    int u=get_pos(x);
    if(op==1)
    {
        res+=dist(x);
        C.add(u,1);
        S.add(u,x);
    }
    else if(op==-1)
    {
        C.add(u,-1);
        S.add(u,-x);
        res-=dist(x);
    }
}
ll get_ans(int n)
{
    int k=n/2;
    ll low=sum_k(k),high=S.sum(len)-sum_k(n-k);
    ll mx=2*(high-low);
    if(n%2==0)
    {
        ll x=v[kth(k)],y=v[kth(k+1)];
        mx-=y-x;
    }
    else if(n%2==1)
    {
        ll x=v[kth(k)],y=v[kth(k+1)],z=v[kth(k+2)];
        mx-=min(y-x,z-y);
    }
    return res-mx;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
    {
        int n,m;
        cin>>n>>m;
        len=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            v[++len]=a[i];
        }
        for(int i=1;i<=m;i++)
        {
            cin>>p[i]>>d[i];
            a[p[i]]+=d[i];
            v[++len]=a[p[i]];
        }
        for(int i=m;i;i--)a[p[i]]-=d[i];
        sort(v+1,v+len+1);
        len=unique(v+1,v+len+1)-v-1;
        res=0;
        for(int i=1;i<=n;i++)change(a[i],1);
        for(int i=1;i<=m;i++)
        {
            change(a[p[i]],-1);
            a[p[i]]+=d[i];
            change(a[p[i]],1);
            cout<<get_ans(n)<<'\n';
        }
        fill(C.c+1,C.c+len+1,0);
        fill(S.c+1,S.c+len+1,0);
    }
    return 0;
}