题解：P3992 [BJOI2017] 开车

· · 题解

不修改的情况下，有经典结论：在 a,b 排序后，对应位置算答案一定更优。证明考虑反证，将 a 的元素排序后放在一边，b 排序后在另一边，两两连线有交叉一定不优。

但是这个结论很没前途，考虑转化为对边计算贡献（即将 a,b 合并到一个数组 c 后，[c_i,c_{i+1}) 这段对答案的贡献）。

考虑先把 a,b 数组里的元素，以及修改操作中的元素合并到一个数组 c，每条边的边长是容易计算的。

我们需要计算每条边被经过了几次，不难发现，假设这条边是 [c_i,c_{i+1})，我们计算 c_i 及以前位置的车辆个数 x，以及加油站个数 y，这条边被经过的次数就是 |x-y|。

定义一个新的数组 f，对于每个位置在 x 的车辆，让 f_x 加 1；对于每个位置在 y 的车辆，让 f_x 减 1，最后求个前缀和 pre，那么 [c_i,c_{i+1}) 被经过的次数就是 |pre_i|。

你会发现这个 c 数组完全是可以离散化的，所以先离散化。

我们需要动态维护这个 pre_i，这个是很容易的，但对 |pre_i| 求和并不容易。

考虑对序列分块。我们对块内的 pre 值从小到大排序，并动态维护块内的答案 sum。注意到每个修改相当于对 pre_i 做区间加减 1 的操作，完全可以对排序后的序列进行二分，找到这个断点，并计算两段（正贡献段和负贡献段）的贡献。散块暴力重构，答案累加 sum 即可。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fr first
#define sc second
#define pii pair<int,int>
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define ro(i,r,l) for(int i=r;i>=l;i--)
const int N=2e5+5;
int n,m,a[N],b[N],base[N],w[N],q;
struct Opt{
    int x,k;
}qr[N];
int v[N];
#define lc(x) (x*val-val+1)
#define rc(x) min(x*val,m)
int val,bk[N],tag[N],ev[N];
ll sum[N],rs;
pair<int,ll>e[N];
void reset(int x){
    rs-=sum[x],sum[x]=0;
    fo(i,lc(x),rc(x)){
        v[i]+=tag[x];
        e[i]={v[i],w[i]};
        sum[x]+=w[i]*abs(v[i]);
    }
    tag[x]=0,rs+=sum[x];
    stable_sort(e+lc(x),e+rc(x)+1);
    fo(i,lc(x)+1,rc(x))
        e[i].sc+=e[i-1].sc;
    fo(i,lc(x),rc(x))
        ev[i]=e[i].fr;
}
void add(int l){
    fo(i,l,rc(bk[l]))
        v[i]++;
    reset(bk[l]);
    fo(i,bk[l]+1,(m-1)/val+1){
        rs-=sum[i];
        int t=lower_bound(ev+lc(i),ev+rc(i)+1,-tag[i])-ev;
        if (t==lc(i))
            sum[i]+=e[rc(i)].sc;
        else sum[i]+=e[rc(i)].sc-e[t-1].sc*2;
        tag[i]++,rs+=sum[i];
    }
}
void del(int l){
    fo(i,l,rc(bk[l]))
        v[i]--;
    reset(bk[l]);
    fo(i,bk[l]+1,(m-1)/val+1){
        rs-=sum[i];
        int t=upper_bound(ev+lc(i),ev+rc(i)+1,-tag[i])-ev;
        if (t==lc(i))
            sum[i]-=e[rc(i)].sc;
        else sum[i]-=e[rc(i)].sc-e[t-1].sc*2;
        tag[i]--,rs+=sum[i];
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    fo(i,1,n){
        cin>>a[i];
        base[i]=a[i];
    }
    fo(i,1,n){
        cin>>b[i];
        base[n+i]=b[i];
    }
    cin>>q;
    fo(i,1,q){
        int x,k;
        cin>>x>>k;
        qr[i]={x,k};
        base[n*2+i]=k;
    }
    sort(base+1,base+n*2+q+1);
    m=unique(base+1,base+n*2+q+1)-base-1;
    fo(i,1,m-1)
        w[i]=base[i+1]-base[i];
    fo(i,1,n){
        a[i]=lower_bound(base+1,base+m+1,a[i])-base;
        b[i]=lower_bound(base+1,base+m+1,b[i])-base;
        v[a[i]]++,v[b[i]]--;
    }
    fo(i,1,q)
        qr[i].k=lower_bound(base+1,base+m+1,qr[i].k)-base;
    val=200;
    fo(i,1,m){
        bk[i]=(i-1)/val+1;
        v[i]+=v[i-1];
    }
    fo(i,1,(m-1)/val+1)
        reset(i);
    cout<<rs<<'\n';
    fo(i,1,q){
        int x=qr[i].x,k=qr[i].k;
        del(a[x]),add(k),a[x]=k;
        cout<<rs<<'\n';
    }
    return 0;
}