题解：P11085 [ROI 2019] 学生座位 (Day 2)

· · 题解

模拟赛考到这题，推出前面贪心和决策单调了，忘了怎么分治，O(nm\log_2m+nk) 遗憾离场。

首先容易想到可以把每个班的同学排序，相邻两两一组，这样一定最优。证明可以尝试将两组的同学互换一下，一定更劣。

然后发现如果存在两个桌子满足 L_1\leq L_2\leq R_2\leq R_1，那么第二个桌子可以不要，这样排序后 L,R 都是递增的。

然后编组后每班的每组就是一个独立的问题，如果直接枚举桌子，暴力做是 O(nmk)。将每组的身高排序，处理出前缀和。由于 L,R 递增，所以可以双指针，是 O(nm\log_2m+nk) 的。

仔细观察发现由于每个班身高递增，那么桌子也一定要递增，这是显然的。证明还是可以尝试互换桌子，一定更劣。然后发现其实就是决策单调性，可以分治。

具体来说，solve(ll l1,ll r1,ll l2,ll r2) 处理区间 [l_1,r_1]，决策区间 [l_2,r_2]，那么找到区间中点 mid=(l_1+r_1)/2，求出中点的决策点 pos，由于决策单调性，前面的决策点一定在前面，后面的决策点一定在后面，所以递归 solve(l1,mid-1,l2,pos) 和 solve(mid+1,r1,pos,r2) 即可。

因为每个组之间答案互相独立，所以左右边的答案不会影响中间，所以可以分治。

一共递归 O(\log_2n) 层，时间复杂度 O(nm\log_2m+k\log_2n)

:::success[\texttt{code}]

//#pragma GCC optimize("Ofast","inline")
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=2e5+10,INF=0x3f3f3f3f3f3f3f3f;
vector<vector<ll>> h;
ll w[N<<1],s[N<<1];
ll l[N],r[N],L[N],R[N];
ll m,n,k,ans;
bool cmp(ll x,ll y)
{
    return L[x]==L[y]?R[x]>R[y]:L[x]<L[y];
}
pair<ll,ll> calc(ll i,ll a,ll b)
{
    for(int j=1;j<=m;j++)
        w[2*j-1]=h[j][2*i-1],w[2*j]=h[j][2*i];
    sort(w+1,w+1+2*m); s[1]=w[1];
    for(int j=2;j<=2*m;j++) s[j]=s[j-1]+w[j];
    ll mi=INF,id=0,lw=0,rw=0;
    for(int j=a;j<=b;j++)
    {
        while(lw<2*m&&w[lw+1]<=l[j]) lw++;
        while(rw<2*m&&w[rw+1]<=r[j]) rw++;
        ll nv=lw*l[j]-s[lw]+s[2*m]-s[rw]-(2*m-rw)*r[j];
        if(nv<mi) mi=nv,id=j;
    }
    return {mi,id};
}
void solve(ll l1,ll r1,ll l2,ll r2)
{
    if(l1>r1) return;
    ll mid=(l1+r1)>>1;
    auto [val,pos]=calc(mid,l2,r2);
    ans+=val;
    solve(l1,mid-1,l2,pos);
    solve(mid+1,r1,pos,r2);
}
int main()
{
//  freopen("class.in","r",stdin);
//  freopen("class.out","w",stdout); 
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>m>>n>>k;
    for(int i=1;i<=k;i++) cin>>L[i]>>R[i];
    h.resize(m+1);
    for(int i=1;i<=m;i++)
    {
        h[i].resize(2*n+1);
        for(int j=1;j<=2*n;j++) cin>>h[i][j];
        sort(h[i].begin()+1,h[i].begin()+1+2*n);
    }
    for(int i=1;i<=k;i++) w[i]=i;
    sort(w+1,w+1+k,cmp); ll la=1,kk=0;
    for(int i=2;i<=k;i++)
        if(L[w[la]]<=L[w[i]]&&R[w[i]]<=R[w[la]]) w[i]=0;
        else la=i;
    for(int i=1;i<=k;i++)
        if(w[i]) l[++kk]=L[w[i]],r[kk]=R[w[i]];
    k=kk,solve(1,n,1,k),cout<<ans;
    return 0;
}

:::