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

mo_mo_yu0_0 · 2026-10-20 20:15:32 · 题解

大常数，零脑子做法。

贪心前面基本都证明过，在此不多证明。

我们仅介绍另类维护方式，这里不需要用到决策单调性！考虑我们每次点集右移，我们分奇数偶数可以连出来链。

具体的，例如 1,2,3,4,5,6，我们有 (1,2)\to (3,4)\to (5,6)，设计 modify 函数表示把一个位置换成另一个，则按照 modify 关系建立链，有 1\to 3\to 5 和 2\to 4\to 6。

故我们考虑维护一个区间距离所有点的距离和，那么我们可以分左边和右边的贡献。可以见代码中的 modify1,modify2。两个问题是相似的。

我们发现，如果没有经过端点，那么改变时相同的，直接维护是单 \log 的线段树，唯一困难的点是，当 x\to y 对于区间 [L,R]，经过一个端点是不好维护的。于是考虑暴力，注意到链是向右的，所以一个端点只会经过一次。

直接暴力是 \mathcal O(nm\log k+mk\log k) 的。每次重构，平衡规划一下。

时间复杂度 \mathcal O(nm\log k+\min(nk,mk\log k))，期望得分 80 分。

考虑优化，注意到暴力枚举的是个区间，我们直接施加线段树，区间个数是 \log 的。因此可以做到 mk。平衡规划，这里常数大，期望得分 88 分数。

发现 mk 需要每次线段树的 change，而我们的 nk 重构常数非常小。所以 mk 的限制大一点，也就是 3m\le n 时才使用 m。

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

namespace Firefly{

    const int N=5e5+10;
    int L[N],R[N];
    int pre[N][2];
    struct edge{
        int l,r;
    }e[N];
    int m,n,k,kk;
    ll ans;
    bool flag;
    int d[N],d2[N];

    namespace Segment{
        ll addtag[N<<2];
        ll minseg[N<<2];
        #define ls (k<<1)
        #define rs (k<<1|1)
        #define mid ((l+r)>>1)
        void pushup(int k){
            minseg[k]=min(minseg[ls],minseg[rs]);
        }
        void changenode(int k,ll v){
            addtag[k]+=v;
            minseg[k]+=v;
        }
        void pushdown(int k){
            if(addtag[k]==0)return;
            changenode(ls,addtag[k]);
            changenode(rs,addtag[k]);
            addtag[k]=0;
        }
        void build(int k,int l,int r){
            if(l==r){
                minseg[k]=2LL*m*L[l];
                return;
            }
            build(ls,l,mid);
            build(rs,mid+1,r);
            pushup(k);
        }
        void change(int k,int l,int r,int x,int y,ll v){
            if(l>y||r<x)return;
            if(l>=x&&r<=y)return changenode(k,v);
            pushdown(k);
            if(x<=mid)change(ls,l,mid,x,y,v);
            if(y>mid)change(rs,mid+1,r,x,y,v);
            pushup(k);
        }
        void changeR(int k,int l,int r,int x,int y){
            if(l>y||r<x)return;
            if(l==r){
                minseg[k]-=R[l];
                return;
            }
            pushdown(k);
            if(x<=mid)changeR(ls,l,mid,x,y);
            if(y>mid)changeR(rs,mid+1,r,x,y);
            pushup(k);
        }
        void changeL(int k,int l,int r,int x,int y){
            if(l>y||r<x)return;
            if(l==r){
                minseg[k]-=L[l];
                return;
            }
            pushdown(k);
            if(x<=mid)changeL(ls,l,mid,x,y);
            if(y>mid)changeL(rs,mid+1,r,x,y);
            pushup(k);
        }
        void rebuild(int k,int l,int r){
            if(l==r){
                minseg[k]-=1LL*R[l]*d[l];
                d[l]=0;
                minseg[k]-=1LL*L[l]*d2[l];
                d2[l]=0;
                return;
            }
            pushdown(k);
            rebuild(ls,l,mid);
            rebuild(rs,mid+1,r);
            pushup(k);
        }
        #undef ls
        #undef rs
        #undef mid
    }using namespace Segment;

    void modify1(int x,int y){
        int l=1,r=k;
        while(l<r){
            int mid=(l+r+1)>>1;
            if(R[mid]<y)l=mid;
            else r=mid-1;
        }
        int lim=l;
        l=1,r=lim;
        while(l<r){
            int mid=(l+r)>>1;
            if(R[mid]>=x)r=mid;
            else l=mid+1;
        }
        if(R[l]<x)++l;
        if(l!=1)change(1,1,k,1,l-1,y-x);
        if(l<=lim){
            change(1,1,k,l,lim,y);
            if(flag)changeR(1,1,k,l,lim);
            else d[l]++,d[lim+1]--;
        }
    }
    void modify2(int x,int y){
        int l=1,r=k;
        while(l<r){
            int mid=(l+r)>>1;
            if(L[mid]>x)r=mid;
            else l=mid+1;
        }
        int lim=l;
        l=lim,r=k;
        while(l<r){
            int mid=(l+r+1)>>1;
            if(L[mid]<=y)l=mid;
            else r=mid-1;
        }
        if(L[l]>y)--l;
        if(l!=k)change(1,1,k,l+1,k,x-y);
        if(l>=lim){
            change(1,1,k,lim,l,x);
            if(flag)changeL(1,1,k,lim,l);
            else d2[lim]++,d2[l+1]--;
        }
    }
    void modify(int x,int y){
        if(x==y)return;
        if(R[1]<y)modify1(x,y);
        if(L[k]>x)modify2(x,y);
    }

    void main(){
        cin>>m>>n>>k;
        flag=(3LL*m<=n);
        for(int i=1;i<=k;i++)cin>>e[i].l>>e[i].r;
        kk=k;
        sort(e+1,e+k+1,[](edge x,edge y){return x.l!=y.l?x.l<y.l:x.r>y.r;});
        k=0;
        int maxr=-1;
        for(int i=1;i<=kk;i++){
            if(e[i].r<=maxr)continue;
            maxr=e[i].r,++k,L[k]=e[i].l,R[k]=e[i].r;
        }
        vector<vector<int>>a(m,vector<int>(n*2,0));
        for(int i=0;i<m;i++)for(int j=0;j<2*n;j++)cin>>a[i][j];
        for(int i=0;i<m;i++)sort(a[i].begin(),a[i].end());
        build(1,1,k);
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                int x=a[j][i*2],y=a[j][i*2+1];
                modify(pre[j][0],x),pre[j][0]=x;
                modify(pre[j][1],y),pre[j][1]=y;
            }
            if(!flag){
                for(int j=1;j<=k;j++)d[j]+=d[j-1],d2[j]+=d2[j-1];
                rebuild(1,1,k);
            }
            ans+=minseg[1];
        }
        cout<<ans<<'\n';
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    Firefly::main();
    return 0;
}