纪念一下第一次补完 ARC 的所有题。
本题解介绍 \(2 log\) 做法，需要卡常才能过。
感谢 @Rainbow_qwq 大佬的耐心讲解，拜谢拜谢拜谢。
首先注意到每次操作是前后缀修改，自然想到维护差分数组。
假设当前操作到了 \(a_i\)，那么差分数组的 \(a_i\) 这位加 \(2\)，然后差分数组全局最小的值大于 \(0\) 的地方减 \(1\)。
注意到我们其实只有维护每次有哪些位置与 \(0\) 取了最大值，也就是差分数组减一的位置和其更小的位置。
其他的贡献是简单的，也就是 \(\displaystyle\sum_{i=1}^{n} m-2 \times a_i\)
那我也就可以维护一个小根堆，每次插入两个 \(a_x\)，删除掉小根堆的堆顶并加入答案。
注意到这是个类似贪心的问题，自然想到建图转模拟费用流。
源点向每个点 \(i\) 连一条边，流量为 \(2\)，成本为 \(a_i\)，\(i\) 向 \(i+1\) 连一条边，流量为无穷大，成本为 \(0\)，每个点 \(i\) 向汇点连边，流量为 \(1\)，成本为 \(0\)。
其实这就是 [P9168 省选联考 2023] 人员调度 的链的部分分，大概的做法为：
把 \(1\) 看成根，维护每个点的子树还能加多少次。
如果加入一个点之后，这个点到根的每个点都还能加点，那么直接加即可。
否则找到最大的点它不能再加点了，那么就找到里面的最大值，
如果能当前代价小于最大值，那么就直接替换。
修改边权的操作看为先把这个边给删了，然后再加入一个新边，注意到删除不太能做，用线段树分治变插销即可。
代码很丑，将就看看把：
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+3,M=(1<<18);
int n,m,Q,tot,la[N],lb[N];
ll res,ans[N];
struct Nod{int x,y;}a[N];
inline int read()
{
int x=0,f=1;char c=getchar();
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return x*f;
}
inline void write(ll X)
{
int s[20],o=0;
while(X){s[++o]=X%10;X/=10;}
if(!o)s[++o]=0;
while(o)putchar(s[o--]+'0');
putchar('\n');
}
#define ls (p<<1)
#define rs (p<<1|1)
#define mi ((l+r)>>1)
struct Sgt2
{
int tr[N],tag[N];
void Build(int p,int l,int r)
{
if(l==r){tr[p]=n-l+1;return;}
Build(ls,l,mi);Build(rs,mi+1,r);tr[p]=tr[rs];
}
void Upd(int R,int p,int l,int r,int d)
{
if(r<=R){tr[p]+=d;tag[p]+=d;return;}
Upd(R,ls,l,mi,d);
if(R>mi)Upd(R,rs,mi+1,r,d);
tr[p]=min(tr[ls],tr[rs])+tag[p];
}
inline int Ask(int p,int l,int r,int w)
{
while(l<r)
{
w+=tag[p];
tr[rs]+w==0?(l=mi+1,p=rs):(r=mi,p=ls);
}
return l;
}
int Find(int R,int p,int l,int r,int w)
{
if(r<=R)return tr[p]+w==0?Ask(p,l,r,w):-1;
w+=tag[p];
if(R<=mi)return Find(R,ls,l,mi,w);
int x=Find(R,rs,mi+1,r,w);
return x==-1?Find(R,ls,l,mi,w):x;
}
}T2;
struct Sgt3
{
int num[N];
struct cmp
{
inline bool operator ()(const int &x,const int &y){return a[x].y!=a[y].y?a[x].y<a[y].y:x<y;}
};
struct PQ
{
priority_queue<int,vector<int>,cmp> q1,q2;
inline void Insert(int x){q1.push(x);}
inline void Erase(int x){q2.push(x);}
inline int Top()
{
while(!q1.empty()&&!q2.empty()&&q1.top()==q2.top())q1.pop(),q2.pop();
return q1.empty()?0:q1.top();
}
}pq[N];
inline int Cmp(int x,int y){return a[x].y>a[y].y?x:y;}
inline void Upd(int p,int u){for(num[p+=M]=u,p>>=1;p;p>>=1)num[p]=Cmp(num[ls],num[rs]);}
inline int Ask(int l)
{
int s=0,r=n;
for(l+=M-1,r+=M+1;l^r^1;l>>=1,r>>=1)
{
if(~l&1)s=Cmp(s,num[l^1]);
if(r&1)s=Cmp(s,num[r^1]);
}
return s;
}
inline void Add(int id){int z=a[id].x;pq[z].Insert(id);Upd(z,pq[z].Top());}
inline void Del(int id){int z=a[id].x;pq[z].Erase(id);Upd(z,pq[z].Top());}
}T3;
struct Sgt1
{
vector<int>now[N];
vector<Nod>cur[N];
inline void Addnew(int id){res+=a[id].y;T3.Add(id);T2.Upd(a[id].x,1,1,n,-1);}
inline void Delnew(int id){res-=a[id].y;T3.Del(id);T2.Upd(a[id].x,1,1,n,1);}
inline Nod Add(int id)
{
int x=T2.Find(a[id].x,1,1,n,0);
if(x==-1){Addnew(id);return {id,-1};}
int mx=T3.Ask(x);
if(a[id].y>=a[mx].y)return {-1,-1};
Addnew(id);Delnew(mx);return {id,mx};
}
inline void Del(Nod t)
{
if(t.x!=-1)Delnew(t.x);
if(t.y!=-1)Addnew(t.y);
}
void Upd(int L,int R,int p,int l,int r,int u)
{
if(L<=l&&r<=R){now[p].push_back(u);return;}
if(L<=mi)Upd(L,R,ls,l,mi,u);
if(R>mi)Upd(L,R,rs,mi+1,r,u);
}
void Ans(int p,int l,int r)
{
for(int x:now[p])cur[p].push_back(Add(x)),cur[p].push_back(Add(x));
if(l==r)ans[l]+=res;
else Ans(ls,l,mi),Ans(rs,mi+1,r);
for(int i=(int)cur[p].size()-1;i>=0;i--)Del(cur[p][i]);
}
}T1;
int main()
{
n=read();m=read();Q=read();T2.Build(1,1,n);
for(int i=1,y;i<=n;i++)y=read(),a[++tot]={i,y},lb[i]=tot,ans[0]+=m-2*y;
for(int i=1,x,y;i<=Q;i++)
{
x=read();y=read();T1.Upd(la[x],i-1,1,0,Q,lb[x]);ans[i]=ans[i-1];ans[i]-=m-2*a[lb[x]].y;
a[++tot]={x,y};lb[x]=tot;la[x]=i;ans[i]+=m-2*y;
}
for(int i=1;i<=n;i++)T1.Upd(la[i],Q,1,0,Q,lb[i]);
T1.Ans(1,0,Q);
for(int i=1;i<=Q;i++)write(ans[i]);
}
我很乐意解答关于此题解的任何疑惑，欢迎与我交流。