大致题意： 有(n)辆车和(n)个加油站分别在(a_{1sim n},b_{1sim n})的位置，每个加油站只能为一辆车加油。每次修改一个(a_i)，求所有车移动距离的最小值。
前言
一开始就想到死胡同里去，结果死活想不出来。。。
点开题解第一眼便看到一个神奇的转化，然后这道题就变成大水题了。。。
看来我还是太菜。
转化
显然可以发现，若把(a,b)分别从小到大排序，则答案就是(sum_{i=1}^n|a_i-b_i|)。
但修改(a_i)会导致大小顺序的改变，所以这个东西并不好维护。
因此，这里就需要一个神奇的转化：
对于第(i)段道路，假设它长度为(l_i)，且在它左侧的车数和加油站数之差为(f_i)，则答案就是(sum l_icdot|f_i|)。
因为相当于有(|f_i|)辆车必须经过这条路，使得车数和加油站数相等，从而相匹配。
分块
那么，现在的问题就是如何维护(f_i)了，而这简直不要太简单。
我们离线先记录下所有有用的位置，然后离散化，就能把道路给分割开。
然后发现，改变一个(a_i)，其实就相当于有一段区间的道路左侧的车数全部加/减(1)。
考虑加/减(1)的修改对答案的影响：
- 若(f_i>0)，则(ans+=l_i/ans-=l_i)
- 若(f_i=0)，则(ans+=l_i/ans+=l_i)。
- 若(f_i<0)，则(ans-=l_i/ans+=l_i)。
所以我们记下(f_i>0)的道路总长度与(f_i<0)道路总长度的差值。并开个(map)，记下(f_i=k)的道路总长度，这样既能求出(f_i=0)的道路总长度，又可以实现差值的维护。
于是，我们就可以用分块轻松解决此题了。
代码
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 50000
#define V 150000
#define GV(x) (lower_bound(dv+1,dv+dc+1,x)-dv)
using namespace std;
int n,m,a[N+5],b[N+5],id[N+5],p[N+5],dc,dv[V+5];
class FastIO
{
private:
#define FS 100000
#define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++)
#define pc(c) (C==E&&(clear(),0),*C++=c)
#define tn (x<<3)+(x<<1)
#define D isdigit(c=tc())
int T;char c,*A,*B,*C,*E,FI[FS],FO[FS],S[FS];
public:
I FastIO() {A=B=FI,C=FO,E=FO+FS;}
Tp I void read(Ty& x) {x=0;W(!D);W(x=tn+(c&15),D);}
Tp I void write(Ty x) {W(S[++T]=x%10+48,x/=10);W(T) pc(S[T--]);}
Tp I void writeln(Con Ty& x) {write(x),pc('
');}
I void clear() {fwrite(FO,1,C-FO,stdout),C=FO;}
}F;
class BlockSolver//分块
{
private:
#define SV 400
int Bs,Bt,f[V+5],Bl[V+5],t[V+5],g[V+5];long long ans;map<int,int> s[SV+5];
I void BF(CI l,CI r,CI v)//暴力修改并重构块
{
RI i,p=Bl[l],L=(p-1)*Bs+1,R=p^Bt?p*Bs:dc;
for(i=L;i<=R;++i) ans-=1LL*abs(f[i]+=t[p])*(dv[i+1]-dv[i]);//删去原先贡献
for(i=l;i<=r;++i) f[i]+=v;for(i=L;i<=R;++i) ans+=1LL*abs(f[i])*(dv[i+1]-dv[i]);//修改并计算新贡献
for(t[p]=g[p]=0,s[p].clear(),i=L;i<=R;++i)//重构
f[i]&&(g[p]+=(f[i]>0?1:-1)*(dv[i+1]-dv[i])),s[p][f[i]]+=dv[i+1]-dv[i];
}
public:
I void Init(int *a,int *b)//初始化
{
RI i;for(i=1;i<=n;++i) ++f[a[i]],--f[b[i]];
for(i=1;i<=dc;++i) f[i]+=f[i-1],ans+=1LL*abs(f[i])*(dv[i+1]-dv[i]);F.writeln(ans);//初始答案
for(Bs=sqrt(dc),i=1;i<=dc;++i) Bl[i]=(i-1)/Bs+1,//初始化块信息
f[i]&&(g[Bl[i]]+=(f[i]>0?1:-1)*(dv[i+1]-dv[i])),s[Bl[i]][f[i]]+=dv[i+1]-dv[i];
Bt=Bl[dc];
}
I void Upt(CI l,CI r,CI v)//区间修改
{
if(Bl[l]==Bl[r]) {BF(l,r,v);goto End;}BF(l,Bl[l]*Bs,v),BF((Bl[r]-1)*Bs+1,r,v);//暴力修改散块
for(RI i=Bl[l]+1;i^Bl[r];++i)//打标记处理完整块
~v?(ans+=(g[i]+=s[i][-t[i]]),g[i]+=s[i][-(++t[i])])//加1
:(ans-=(g[i]-=s[i][-t[i]]),g[i]-=s[i][-(--t[i])]);//减1
End:F.writeln(ans);
}
}B;
int main()
{
RI i;F.read(n);
for(i=1;i<=n;++i) F.read(a[i]),dv[++dc]=a[i];
for(i=1;i<=n;++i) F.read(b[i]),dv[++dc]=b[i];
for(F.read(m),i=1;i<=m;++i) F.read(id[i]),F.read(p[i]),dv[++dc]=p[i];
sort(dv+1,dv+dc+1),dc=unique(dv+1,dv+dc+1)-dv-1,dv[dc+1]=dv[dc];//离散化
for(i=1;i<=n;++i) a[i]=GV(a[i]),b[i]=GV(b[i]);for(i=1;i<=m;++i) p[i]=GV(p[i]);
for(B.Init(a,b),i=1;i<=m;++i) a[id[i]]^p[i]&&
(a[id[i]]<p[i]?B.Upt(a[id[i]],p[i]-1,-1):B.Upt(p[i],a[id[i]]-1,1),a[id[i]]=p[i]);
return F.clear(),0;
}