【BJOI2017】开车 | Mrsrz's blog

分块

题目大意：

有 $n$ 辆车和 $n$ 个加油站在数轴上，车从点 $a$ 开到 $b$ 要走的距离为 $|a-b|$。

现在要求一辆车开到一个加油站里，一个加油站只能给一辆车加油。问车要开的最少的总距离是多少。

有 $q$ 次操作，每次会改变一辆车的位置，每次改变完后需要再次回答这个问题。

题解：

有一个显然的贪心，每个加油站和最早的车（如果之前有未匹配的车）匹配，每辆车和最早的加油站（如果之前有未匹配的加油站）匹配。

换个思路，考虑将点离散化，然后考虑维护相邻两个点之间的这段距离被经过的次数。

我们令车为 $1$，加油站为 $-1$，设 $f_i$ 表示前 $i$ 个位置的前缀和，那么位置 $i$ 到 $i+1$ 这条边被经过的次数，就是 $|f_i|$，即未匹配的车或加油站数。

那么修改一辆车的位置，相当于区间加 $1$ 或者区间减 $1$。

由于有这个绝对值的限制，比较难用一些数据结构可以。

考虑数列分块，然后每个块里按照 $f_i$ 进行排序，那么这个绝对值，相当于块内，前一半是负贡献，后一半是正的贡献。

然后考虑区间加 $1$，减 $1$ 操作。

边角暴力修改，重新排序。

中间的整块部分，有一部分会加上贡献，另一部分会减去贡献。我们二分这个临界点，然后用前缀和累加贡献即可。

时间复杂度 $O(q\sqrt n\log n)$。足以通过本题。

实际上可以做到 $O(q\sqrt n)$。具体是暴力修改时使用基数排序代替sort，整块部分，将 $f_i$ 相同的缩起来，那么区间加 $1$ 或减 $1$，都最多使临界点的位置改变 $1$。这样就把两个部分的 $\log$ 都降下来了。

代码写的还是带 $\log$ 的。

Code：

#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<vector>
#define bel(x)((x-1)/siz+1)
using namespace std;
typedef long long LL;
typedef pair<int,int>PII;
const int N=150050,siz=400;
vector<int>vec;
int m,n,q,A[N],B[N],L[404],R[404],blocks;
PII a[N];
struct Mov{
    int id,x;
}que[N];
inline int find(int x){return lower_bound(vec.begin(),vec.end(),x)-vec.begin();}
struct Block{
    PII a[404],b[404];int tag;
    int prs[404];
    LL ans;
    int L,R,len;
    inline void re_ans(){
        ans=0;
        for(int i=1;i<=len;++i)
        ans=ans+(LL)abs(b[i].first+tag)*b[i].second,prs[i]=prs[i-1]+b[i].second;
    }
    void init(int l,int r){
        L=l,R=r,len=r-l+1;tag=0;
        for(int i=l;i<=r;++i)
        a[i-l+1]=b[i-l+1]=::a[i];
        sort(b+1,b+len+1);
        re_ans();
    }
    void modify(int l,int r,int x){
        for(int i=l;i<=r;++i)
        a[i-L+1].first+=x;
        for(int i=1;i<=len;++i)b[i]=a[i];
        sort(b+1,b+len+1);
        re_ans();
    }
    void modify(int x){
        if(x==1){
            int id=lower_bound(b+1,b+len+1,make_pair(-tag,0))-b-1;
            ans-=prs[id];
            ans+=prs[len]-prs[id];
        }else
        if(x==-1){
            int id=lower_bound(b+1,b+len+1,make_pair(-tag+1,0))-b-1;
            ans+=prs[id];
            ans-=prs[len]-prs[id];
        }
        tag+=x;
    }
}G[404];
void modify(int l,int r,int x){
    const int bL=bel(l),bR=bel(r);
    if(bL==bR)
    G[bL].modify(l,r,x);else{
        G[bL].modify(l,R[bL],x);
        G[bR].modify(L[bR],r,x);
        for(int i=bL+1;i<bR;++i)
        G[i].modify(x);
    }
}
int main(){
    vec.push_back(-1);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>m;
    for(int i=1;i<=m;++i)cin>>A[i],vec.push_back(A[i]);
    for(int i=1;i<=m;++i)cin>>B[i],vec.push_back(B[i]);
    cin>>q;
    for(int i=1;i<=q;++i)
    cin>>que[i].id>>que[i].x,vec.push_back(que[i].x);
    sort(vec.begin(),vec.end());
    vec.erase(unique(vec.begin(),vec.end()),vec.end());
    n=vec.size()-1;
    blocks=bel(n);
    for(int i=1;i<=blocks;++i)L[i]=R[i-1]+1,R[i]=i*siz;R[blocks]=n;
    for(int i=1;i<=m;++i)
    ++a[A[i]=find(A[i])].first,--a[find(B[i])].first;
    for(int i=1;i<=n;++i)
    a[i].first+=a[i-1].first,a[i].second=i==n?0:vec[i+1]-vec[i];
    for(int i=1;i<=blocks;++i)
    G[i].init(L[i],R[i]);
    LL ans=0;
    for(int i=1;i<=blocks;++i)ans+=G[i].ans;
    cout<<ans<<'\n';
    for(int i=1;i<=q;++i){
        int id=que[i].id,x=find(que[i].x),lst=A[id];
        if(lst<x)modify(lst,x-1,-1);else
        if(lst>x)modify(x,lst-1,1);
        A[id]=x;
        ans=0;
        for(int i=1;i<=blocks;++i)ans+=G[i].ans;
        cout<<ans<<'\n';
    }
    return 0;
}