自动搬运

查看原文

来自洛谷，原作者为

	shadowice1984 これが勘違いでも、これが勘違いでも

搬运于2025-08-24 21:55:19，当前版本为作者最后更新于2018-07-01 14:19:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

喜闻乐见的5w分块……

需要稍微卡卡常数，(其实是我人傻常数大)

---

本题题解

我们认为车和加油站是点，那么这就构成了一条链

直接两两匹配进行计算不是十分容易，所以我们考虑交换Σ，换句话说，考虑贡献

我们考虑在最后的方案中每一条边的贡献，那么我们会发现一条边的贡献应该是

这条边的长度×|这条边之前的车数-这条边之前的加油站数|

感性理解一下就是要么是车从左向右开过去，要么是加油站让车开过来，总之这条边上一定会通过二者之差的车数，所以贡献就是上面的式子

那么我们如果我们直接按照上面的式子进行对答案进行计算的话我们会发现这个做法不是十分明智

因为我们要支持以下操作

维护一个序列，每个点上有两个属性a和b

1.修改某个点的点权b

2.区间a加1区间a减1

3.区间平移

3.求上面带绝对值式子的和

我们发现似乎这个东西不是十分好用线段树做，于是我们考虑使用块状链表/块状数组强行维护这个东西

那么问题来了我们发现如果你使用块状链表来维护的话你会发现你要支持插入和删除一个点，那么换句话说你需要支持分裂一个较大的块这个操作……

此时你的代码就会极度恶心并且不能看了……

所以我们考虑加点常数然后消掉这个恶心的分裂操作

那么我们将所有修改强行离线之后我们将这15w个点强行离散化，然后对这15w个边进行分块

此时我们会发现，刚才的式子仍然成立，因为如果这个边的左端点暂时没有车的话，你相当于将一条长边拆成两条短边计算贡献，当然上边的式子还是成立的

但是此时就变成了普通的区间加区间减了因为我们已经把所有的询问离线塞到我们数据结构里了，也就是说我们没有了恶心的插入和删除操作，只剩下加法和减法了

这样的话我们会略微好写一点

这样的话我们就只需要区间加区间减了，恶心的修改点权和分裂块全部都没有了

那么现在我们考虑怎么做这个操作

我们将所有边分成$\sqrt{N}$块

然后每个块内按照a(也就是前面车的个数减加油站个数)进行排序

现在考虑如何维护块内答案(就是那个式子的和)

首先如果这个块不是整体的被加1或者减1的话可以直接重构了

因为每次操作最多重构两个块

如果是整体加1或者减1的话我们可能需要一些特殊技巧

注意这里如果是整体加a整体减b的话会更难写一点

先介绍一下一般的做法

我们假设$f(x)$为这个块在整体被加x的时候的答案值

你发现这是一个若干带绝对值式子求和的形式

高中数学知识告诉你这是一个分段函数，并且你发现这个函数仅仅分了$O(\sqrt{n})$段

因此我们可以暴力的维护每一个分段的函数此时我们就可以lower_bound 出x所在的分段，然后就可以直接计算了

但是我们发现只是加一和减一所以我们可以偷点懒

具体来说我们维护按a排序的序列，然后处理出这个按a排序的序列的b的前缀和

每次加1和减1的时候暴力的二分出此时0的位置

如果是加1，那么答案变化量是所有非负数的b值和-负数的b值和

如果是减1，那么答案变化量是所有非正数的b值和-正数的b值和

当我们二分出0的位置之后就可以使用前缀和表达这个答案的变化量了

然后分块打一下标记就可以愉快的做完这道题了

如果发现常数不是十分对劲的话可以将重构时的快速排序换成计数排序

复杂度$O(N\sqrt{N}logN)$

上代码~

// luogu-judger-enable-o2
#pragma GCC optimize(2)
#include<cstdio>
#include<algorithm>
#include<map>
#include<cmath>
#include<ctime>
using namespace std;const int N=15*1e4+10;const int B=400;typedef long long ll;
map <int,int> mp1,mp2;int n;int m;int pos[N];int bs;int bt;int tot;int qu[N];int qv[N];
ll res=0;inline ll mabs(ll x){return x>0?x:-x;}int* AB;int st;int ed;
inline bool cmp(const int& a,const int& b){return AB[a]<AB[b];}
struct b_arr
{
    int st[B];int tp;int ab[B];int w[B];ll pre[B];int miu;ll ans;
    inline void app(){for(int i=1;i<=tp;i++)ab[i]-=miu;miu=0;}
    inline void rebuild()
    {
        AB=ab;sort(st+1,st+tp+1,cmp);//暴力重构
        for(int i=1;i<=tp;i++)pre[i]=pre[i-1]+w[st[i]];ans=0;
        for(int i=1;i<=tp;i++)ans+=mabs(ab[st[i]])*w[st[i]];
    }
    inline void rb_add(const int& lc,const int& p)
    {for(int i=1;i<=tp;i++)st[i]=i;app();for(int i=lc;i<=tp;i++)ab[i]+=p;rebuild();}
    inline void lb_miu()
    {
        int l=0;int r=tp;//打标记，可能这里为了方便二分的处理可能需要打减法标记
        while(l!=r){int mid=(l+r+1)/2;if(ab[st[mid]]<=miu)l=mid;else r=mid-1;}
        ans+=2*pre[l]-pre[tp];miu++;
    }
    inline void lb_add()
    {
        --miu;int l=0;int r=tp;
        while(l!=r){int mid=(l+r+1)/2;if(ab[st[mid]]<=miu)l=mid;else r=mid-1;}
        ans+=pre[tp]-2*pre[l];
    }
    inline void ins(const int& Ab,const int& W){++tp;st[tp]=tp;ab[tp]=Ab;w[tp]=W;}
}bl[B];int bu[N];int bv[N];//维护编号到块编号的映射
int main()
{
    scanf("%d",&n);//偷懒使用了map进行离散化
    for(int i=1;i<=n;i++){scanf("%d",&pos[i]);mp1[pos[i]]=1;mp2[pos[i]]++;}
    for(int i=1,po;i<=n;i++){scanf("%d",&po);mp1[po]=1;mp2[po]--;}
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {scanf("%d%d",&qu[i],&qv[i]);mp1[qv[i]]=1;if(mp2[qv[i]]==0)mp2[qv[i]]=0;}
    tot=mp1.size()-1;bs=sqrt(tot);//注意最后一个点没有边，所以删掉
    for(int i=0;i*bs<=tot;i++)
        for(int j=1;j<=bs&&i*bs+j<=tot;j++)bu[i*bs+j]=i+1,bv[i*bs+j]=j;
    map <int,int> :: iterator it,it1;tot=0;
    for(it=mp2.begin(),it1=it,++it1;it1!=mp2.end();++it,++it1)it1->second+=it->second;
    for(it=mp1.begin(),it1=it,++it1;it1!=mp1.end();++it,++it1)
    {it->second=++tot,bl[bu[tot]].ins(mp2[it->first],it1->first-it->first);}
    mp1.erase(--mp1.end());mp2.erase(--mp2.end()); 
    bt=(tot-1)/bs+1;for(int i=1;i<=bt;i++)bl[i].rebuild();
    for(int i=1;i<=bt;i++)res+=bl[i].ans;printf("%lld\n",res);
    for(int t=1;t<=m;t++)
    {
        int ls=mp1[pos[qu[t]]];int rs=mp1[qv[t]];//讨论下是区间加还是区间减
        if(ls==0){bl[bu[rs]].rb_add(bv[rs],1);for(int i=bu[rs]+1;i<=bt;i++)bl[i].lb_add();}
        else if(rs==0){bl[bu[ls]].rb_add(bv[ls],-1);for(int i=bu[ls]+1;i<=bt;i++)bl[i].lb_miu();}
        else if(ls<rs)
        {
            bl[bu[ls]].rb_add(bv[ls],-1);bl[bu[rs]].rb_add(bv[rs],1);
            for(int i=bu[ls]+1;i<=bu[rs];i++)bl[i].lb_miu();
        }
        else if(ls>rs)
        {
            bl[bu[ls]].rb_add(bv[ls],-1);bl[bu[rs]].rb_add(bv[rs],1);
            for(int i=bu[rs]+1;i<=bu[ls];i++)bl[i].lb_add();
        }res=0;for(int i=1;i<=bt;i++)res+=bl[i].ans;
        printf("%lld\n",res);pos[qu[t]]=qv[t];//更改位置
    }return 0;//拜拜程序~
}