首页 > 代码库 > [BZOJ]4908: [BeiJing2017]开车

[BZOJ]4908: [BeiJing2017]开车

Time Limit: 30 Sec  Memory Limit: 256 MB

Description

  你有n辆车,分别a1, a2, ..., an位置和n个加油站,分别在b1, b2, ... ,bn 。每个加油站只能支持一辆车的加油,所以你要把这些车开到不同的加油站加油。一个车从x位置开到y位置的代价为 |x-y| ,问如何安排车辆,使得代价之和最小。同时你有q个操作,每次操作会修改第i辆车的位置到x,你要回答每次修改操作之后最优安排方案的总代价。

Input

  第一行一个正整数n,接下来一行n个整数a1, a2, ...,an,接下来一行n个整数b1, b2,... ,bn。
  接下来一行一个正整数q,表示操作的个数。
  接下来q行,每行有两个整数i(1 ≤ i ≤ n)和x,表示将i这辆车开到x位置的操作。
  1 ≤ n, q ≤ 5 * 10^4,所有的车和加油站的范围一直在0到10^9之间。

Output

  共q+1行,第一行表示一开始的最优代价。接下来q行,第i行表示操作i之后的最优代价。

Sample Input

  2
  1 2
  3 4
  1
  1 3

Sample Output

  4
  2
  【样例解释】
  一开始将第一辆车开到位置4,将第二辆车开到位置3,代价为 |4-1|+|3-2|=4。
  修改后第一辆车的位置变成3,代价为 |3-3|+|4-2|=2。

Solution

  一个显然的结论是把a和b排序后按顺序匹配最优,这里就不做说明了。假设我们有一种模拟这个匹配的过程如下:从左到右扫,碰到车就把就把车加入队列,碰到加油站也把加油站加入队列,如果有车和加油站同时在队列中,我们让他们两两匹配,无法匹配我们就拖着所有车或加油站一起向右走。按照这个思路,我们可以这么计算答案:把坐标离散化后,每个车往对应坐标+1,加油站往对应坐标-1,把+1和-1的标记做前缀和,每个坐标的前缀和的绝对值乘上到下一个坐标的距离之和就是答案。那么一次修改就是把这些标记区间+1或-1,同时维护答案。这个可以分块搞,做法如下:按坐标顺序把前缀和分成若干块,每块内把前缀和排序,并求出排序后的每个坐标到排序前的下一个坐标的距离的前缀和,修改时在边缘的块直接暴力重构,剩下整块修改时,标记前缀和大于0和小于0的分开统计答案,排序可以基排桶排啥的,0的分界点也可以动态维护,但我懒所以都写的log,还好能过。总复杂度$O(nlogn\sqrt{n})$或$O(n\sqrt{n})$。

Code

#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
inline int read()
{
    int x;char c;
    while((c=getchar())<0||c>9);
    for(x=c-0;(c=getchar())>=0&&c<=9;)x=x*10+c-0;
    return x;
}
#define MN 50000
#define MP 150000
#define K 400
int a[MN+5],b[MN+5],c[MN+5],d[MN+5];
int p[MP+5],pn,s[MP+5],ad[K+5];
ll ans;
struct data{int s;ll p;}t[MP+5];
bool cmp(const data&a,const data&b){return a.s<b.s;}
inline ll z(int x){return x<0?-x:x;}
void build(int x)
{
    int i;
    for(i=x;i<x+K;++i)t[i].s=s[i],t[i].p=p[i];
    sort(t+x,t+x+K,cmp);
    for(i=x;++i<x+K;)t[i].p+=t[i-1].p;
}
void add(int l,int r,int x)
{
    int i,lk=(l-1)/K,rk=(r-1)/K;
    for(i=lk*K+1;i<=(lk+1)*K;++i)s[i]+=ad[lk];ad[lk]=0;
    for(i=l;i<=r&&i<=(lk+1)*K;++i)ans-=z(s[i])*p[i],ans+=z(s[i]+=x)*p[i];
    build(lk*K+1);
    for(i=lk+1;i<rk;++i)
    {
        ad[i]+=x;
        int l=i*K+1,r=(i+1)*K,mid,res=0;
        if(x<0)
        {
            while(l<=r)
                if(t[mid=l+r>>1].s+ad[i]<0)res=mid,l=mid+1;
                else r=mid-1;
            ans+=2*t[res].p-t[(i+1)*K].p;
        }
        else
        {
            while(l<=r)
                if(t[mid=l+r>>1].s+ad[i]<=0)res=mid,l=mid+1;
                else r=mid-1;
            ans-=2*t[res].p-t[(i+1)*K].p;
        }
    }
    if(lk==rk)return;
    for(i=rk*K+1;i<=(rk+1)*K;++i)s[i]+=ad[rk];ad[rk]=0;
    for(i=r;i>rk*K;--i)ans-=z(s[i])*p[i],ans+=z(s[i]+=x)*p[i];
    build(rk*K+1);
}
int main()
{
    int n=read(),q,i,j;
    for(i=1;i<=n;++i)p[++pn]=a[i]=read();
    for(i=1;i<=n;++i)p[++pn]=b[i]=read();
    for(q=read(),i=1;i<=q;++i)c[i]=read(),p[++pn]=d[i]=read();
    sort(p+1,p+pn+1);
    for(i=2,j=1;i<=pn;++i)if(p[i]!=p[j])p[++j]=p[i];
    for(i=j;++i<=pn;)p[i]=0;pn=j;
    for(i=1;i<=n;++i)
        ++s[a[i]=lower_bound(p+1,p+pn+1,a[i])-p],
        --s[b[i]=lower_bound(p+1,p+pn+1,b[i])-p];
    for(i=1;i<=q;++i)d[i]=lower_bound(p+1,p+pn+1,d[i])-p;
    for(i=1;i<pn;++i)ans+=z(s[i]+=s[i-1])*(p[i]=p[i+1]-p[i]);p[i]=0;
    printf("%lld\n",ans);
    for(i=1;i<=pn;i+=K)build(i);
    for(i=1;i<=q;++i)
    {
        if(a[c[i]]<d[i])add(a[c[i]],d[i]-1,-1);
        else if(d[i]<a[c[i]])add(d[i],a[c[i]]-1,1);
        a[c[i]]=d[i];
        printf("%lld\n",ans);
    }
}

 

[BZOJ]4908: [BeiJing2017]开车