题解：P17241 [IOI 2026] 纪念碑 / Monuments

nullptr_qwq_ · 2026-08-15 12:37:48 · 题解

大概用 2h 编出来了做法/youl

考虑对于固定点集中已经配对或已经在 0 的进行消除，有解当且仅当 m\leq n-m。注意到正负数量相同本质上是进行一个完美匹配（可以认为有任意个 0），x,y 匹配的权值 w(x,y)=|x+y|，并且可以构造一种方案使得其中任意恰好一个点是移动的。而 xy\ge 0 匹配并没有意义，必须是一正一负才能节省代价，即 xy<0 时 |x+y|=|x|+|y|-2\min(|x|,|y|)。考虑认为答案是所有点的 |x| 求和然后再减最大节约代价。

问题转为对 x<0<y 的连边，要求不能是两个固定点匹配，权值为 \min(-x,y)，求二分图最大权匹配。

通过一些解集调整手法（严格相交调成包含不劣），直接对匹配的形态考虑，两端点均白和任意线段都是包含关系，白黑/黑白线段内部都是包含，可以得到一个 O(n^2) 做法，并没有前途。

考虑左部点点集 S 和右部点点集 T 不存在限制时的最优匹配（sub 2,3）是 S,T 各自从大到小排序求 f(S,T)=\sum_{i=1}^{\min(|S|,|T|)}\min(S_i,T_i)。

令左边自由点集为 L_0，固定点集为 L_1，右边同理有 R_0,R_1，不允许 L_1,R_1 匹配。问题等于求一个子集 S\subseteq L_0 最大化 f(S\cup L_1,R_0)+f(L_0-S,R_1)。而有解要求 L_0,R_0 的匹配数量不超过 \lfloor\frac{n}{2}\rfloor-m，此处只需限制 |S|\leq k=\lfloor\frac{n}{2}\rfloor-m。

根据几个比较经典的 cnoi 题，猜测 f 具有某种凸性以及决策的单调性，初始令 S=\varnothing，然后选使得 \Delta calc(S') 最大的 x\not\in S 加入进来，如此做 k 遍就可以得到最终最优秀的 S。在此过程使用数据结构加速即可。也就是初始为 f(L_1,R_0)+f(L_0,R_1)，整个过程 R_0,R_1 恒定，每次操作就是将 L_0 的某个元素扔到 L_1，要求新的 f 之和最大。

刻画 f(S,T) 可以考虑转置维度拆贡献，即 f(S,T)=\sum_{k>0}\min(\sum[S_i\ge k],\sum[T_i\ge k])。

考虑固定集合 B，支持对 A 仅插入/仅删除，实时查询 f(A,B)。令 a_k=\sum[A_i\ge k],b_k=\sum[B_i\ge k]，那么相当于 b 单调降而要支持 a 前缀加/减。考虑前缀加，那么所有 v_k=a_k-b_k 而 v_k<0 的会对 f 产生 +1 的贡献。同理前缀减就是 v_k\leq 0 产生 -1 的贡献。而移动一个 x 只需要关注这个最大的变化量。

对值离散化从而只有 O(n) 段，当仅插入的 v_k 第一次 <0 时则将其提出，仅删除的 v_k 第一次 \leq 0 同理，线段树维护最小值出现位置即可。当被提出时，使用另一个线段树维护所有 x 对应的 \Delta calc(S')，提取最大值并操作即可。被考虑过就要删除，均摊是 O(n) 次的。

时间复杂度 O(n\log n)。

https://qoj.ac/submission/2769624

#include<bits/stdc++.h>
#include"monuments.h"
#define bll __int128
#define ull unsigned long long
#define ll long long
#define uint unsigned
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
#define inf 1000000000
#define infll 1000000000000000000ll
#define pii pair<int,int>
#define rep(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define per(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define dF(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define SZ(x) ((int)x.size())
#define all(x) x.begin(),x.end()
using namespace std;
bool ST;
template<typename T>inline void chkmax(T &x,const T &y){ x=std::max(x,y); }
template<typename T>inline void chkmin(T &x,const T &y){ x=std::min(x,y); }
const int maxn=500005;
int L[maxn],n;
#define ls (o<<1)
#define rs (o<<1|1)
namespace seg{
    int siz[maxn<<2],t[maxn<<2],tag[maxn<<2],ps[maxn<<2];
    void mt(int o,int val){ tag[o]+=val,t[o]+=val; }
    void pd(int o){ if(tag[o])mt(ls,tag[o]),mt(rs,tag[o]),tag[o]=0; }
    void up(int o){
        siz[o]=siz[ls]+siz[rs];
        if(siz[ls]==0)ps[o]=ps[rs],t[o]=t[rs];
        else if(siz[rs]==0)ps[o]=ps[ls],t[o]=t[ls];
        else ps[o]=t[ls]>=t[rs]?ps[ls]:ps[rs],t[o]=max(t[ls],t[rs]);
    }
    void update(int o,int l,int r,int ql,int qr,int val){
        if(ql>qr)return;
        if(ql<=l&&qr>=r)return mt(o,val),void();
        int mid=(l+r)>>1;pd(o);
        if(ql<=mid)update(ls,l,mid,ql,qr,val);
        if(qr>mid)update(rs,mid+1,r,ql,qr,val);
        up(o);
    }
    void change(int o,int l,int r,int pos,int val){
        if(l==r)return siz[o]+=val,ps[o]=siz[o]<=0?0:l,void();
        int mid=(l+r)>>1;pd(o);
        (pos<=mid)?change(ls,l,mid,pos,val):change(rs,mid+1,r,pos,val);
        up(o);
    }
}
struct{
    bool del[maxn<<2];
    int t[maxn<<2],ps[maxn<<2],tag[maxn<<2];
    void mt(int o,int val){ tag[o]+=val,t[o]+=val; }
    void pd(int o){ if(tag[o])mt(ls,tag[o]),mt(rs,tag[o]),tag[o]=0; }
    void up(int o){
        del[o]=del[ls]&del[rs];
        if(del[o])return;
        if(del[rs])t[o]=t[ls],ps[o]=ps[ls];
        else if(del[ls])t[o]=t[rs],ps[o]=ps[rs];
        else ps[o]=t[ls]>=t[rs]?ps[ls]:ps[rs],t[o]=max(t[ls],t[rs]);
    }
    void update(int o,int l,int r,int ql,int qr,int val){
        if(ql>qr)return;
        if(ql<=l&&qr>=r)return mt(o,val),void();
        int mid=(l+r)>>1;pd(o);
        if(ql<=mid)update(ls,l,mid,ql,qr,val);
        if(qr>mid)update(rs,mid+1,r,ql,qr,val);
        up(o);
    }
    void change(int o,int l,int r,int pos){
        if(l==r)return del[o]=1,ps[o]=0,void();
        int mid=(l+r)>>1;pd(o);
        (pos<=mid)?change(ls,l,mid,pos):change(rs,mid+1,r,pos);
        up(o);
    }
    void build(int o,int l,int r){
        ps[o]=l;
        if(l==r)return;
        int mid=(l+r)>>1;
        build(ls,l,mid),build(rs,mid+1,r);
    }
}t1,t2;
#undef ls
#undef rs
ll get_cost(std::vector<int>X,std::vector<int>P){
    auto calc=[&](vector<int>a,vector<int>b){
        sort(all(a)),sort(all(b)),reverse(all(a)),reverse(all(b));
        ll sum=0;
        F(i,0,min(SZ(a),SZ(b))-1)sum+=min(a[i],b[i]);
        return sum;
    };
    map<int,int>mp,mp1;
    vector<bool>vis(SZ(X),0);
    for(int&i:P)vis[i]=1;
    vector<int>A,B;
    F(i,0,SZ(X)-1)
        if(vis[i])++mp[X[i]],++mp1[X[i]];
        else if(X[i]!=0)A.push_back(X[i]);
    for(auto&it:mp1)if(it.fi<0){
        int x=it.fi,val=min(it.se,mp1[-x]);
        if(val)mp[x]-=val,mp[-x]-=val;
    }
    for(auto&it:mp)if(it.se&&it.fi!=0)F(_,1,it.se)B.push_back(it.fi);
    if(SZ(X)-SZ(P)<SZ(B))return -1;
    ll output=0,ans=0;
    for(int&i:A)output+=abs(i);
    for(int&i:B)output+=abs(i);
    vector<int>L0,R0,L1,R1;
    for(int&i:A)(i<0?L0:R0).push_back(abs(i));
    for(int&i:B)(i<0?L1:R1).push_back(abs(i));
    chkmax(ans,calc(L0,R1)+calc(L1,R0));
    ll cur=ans;
    vector<int>lsh;
    lsh.push_back(0);
    for(vector<int>x:{L0,R0,L1,R1})for(int&i:x)lsh.push_back(i);
    sort(all(lsh)),lsh.erase(unique(all(lsh)),lsh.end()),n=SZ(lsh)-1;
    if(!n)return output;
    F(i,1,n)L[i]=lsh[i]-lsh[i-1];
    for(int&i:L0)i=lower_bound(all(lsh),i)-lsh.begin();
    for(int&i:R0)i=lower_bound(all(lsh),i)-lsh.begin();
    for(int&i:L1)i=lower_bound(all(lsh),i)-lsh.begin();
    for(int&i:R1)i=lower_bound(all(lsh),i)-lsh.begin();
    int k=min(SZ(L0),((SZ(A)+SZ(B))>>1)-SZ(B));
    t1.build(1,1,n),t2.build(1,1,n);
    F(i,1,n)seg::update(1,1,n,i,n,L[i]);
    for(int&i:L0)seg::change(1,1,n,i,1);
    auto flush=[&](){
        for(;;){
            if(t1.del[1]||t1.t[1]<0)break;
            int u=t1.ps[1];
            t1.change(1,1,n,u),seg::update(1,1,n,u,n,-L[u]);
        }
        for(;;){
            if(t2.del[1]||t2.t[1]<0)break;
            int u=t2.ps[1];
            t2.change(1,1,n,u),seg::update(1,1,n,u,n,-L[u]);
        }
    };
    for(int&u:R1)t2.update(1,1,n,1,u,1);
    for(int&u:L0)t2.update(1,1,n,1,u,-1);
    for(int&u:R0)t1.update(1,1,n,1,u,-1);
    for(int&u:L1)t1.update(1,1,n,1,u,1);
    flush();
    while(k--){
        if(seg::t[1]<0)break;
        int u=seg::ps[1];
        cur+=seg::t[1],chkmax(ans,cur);
        t1.update(1,1,n,1,u,1);
        t2.update(1,1,n,1,u,1);
        flush();
    }
    return output-(ans<<1);
}
// g++ grader.cpp qoj19102.cpp -o a -std=c++14 -O2