题目链接

题意

给定一个序列，要求将它改造成一个非降序列，修改一个数的代价为其改变量的平方。

最小化总代价。

另有\(Q\) 次询问，每次修改一个位置上的数。(询问之间独立,互不影响)

Sol

神仙 保序回归 问题，完全不会。

首先是一个暴力的每次 \(O(n)\) 做法。

结论是: 最后的结果序列一定是一段段的相同的数，其值为段中所有元素的平均数。

所以暴力就是维护一个单调栈。

每次加入一个数后形成一段。

然后不断比较栈顶的段和下面一个段的平均数的大小，如果栈顶小一些就把它和下面那个段合并。

然后考虑多组询问。

显然每次重新计算所有的数太呆了，有很多重复计算且没有必要的地方。

一个很直观的想法就是考虑求出最后修改的数所在段的左右端点，这样我们维护一个前缀后缀的答案后就能够 \(O(1)\) 算出最后的答案了。

所以我们先对前后缀分别维护好答案以及单调栈(用可持久化线段树)。

发现如果我们确定了左端点那么右端点是唯一确定的。

首先我们要知道从后往前做上面的贪心也是正确的。

然后你现在从后往前已经求出了了 \([R+1,n]\) 这些数的单调栈。

当前段的右端点是 \(R\)，然后计算其左端点。

考虑左边来了一个段，其平均数为 \(x\) ，当前平均数为 \(p\)

1. \(x>p\)

   这时我们显然要把前面那个段给合并进来，那么当前的平均数就会变大。

   由于 \(x\) 往前是单调不升的，所以肯定会在某一个地方停止合并。

2. \(x<p\)

   那么这个时候已经停止合并，只可能在后面某处停止合并。

所以左端点具有可二分性，可以线段树上二分求出。

然后考虑求右端点。

这个同样具有可二分性，因为当前段合法的话往后再并入一个后的平均值小于后面那一个段，就更加小于并入后的后继段了。

二分套二分求出左右端点就能算答案了。

code:

/*
  1. 一个点最后会在的右端点一定是某个后缀单调栈节点的边界?  通过从后往前暴力的正确性可知
  2. 二分的依据&正确性?  非情况讨论出往前加入一系列单调栈节点后平均值的变化,为一个单峰函数

 */
#include<bits/stdc++.h>
using namespace std;
template<class T>inline void init(T&x){
    x=0;char ch=getchar();bool t=0;
    for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') t=1;
    for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch-48);
    if(t) x=-x;return;
}typedef long long ll;
typedef double db;
const int N=1e5+10;
const int MAXN=N*80;
const int mod=998244353;
template<class T>inline void Inc(T&x,int y){x+=y;if(x>=mod) x-=mod;}
template<class T>inline void Dec(T&x,int y){x-=y;if(x < 0 ) x+=mod;}
template<class T>inline int fpow(int x,T k){int ret=1;for(;k;k>>=1,x=(ll)x*x%mod) if(k&1) ret=(ll)ret*x%mod;return ret;}
inline int Sum(int x,int y){x+=y;if(x>=mod) x-=mod;return x;}
inline int Dif(int x,int y){x-=y;if(x < 0 ) x+=mod;return x;}
int maxnum;int n,m;
int A[N];int ans=0,inv[N];
struct node{
    int len;ll sum;int sump;
    node(int _l=0,ll _s=0,int _sump=0){len=_l,sum=_s,sump=_sump;}
    inline int Calc(){int ms=sum%mod;return Dif(sump,(ll)ms*ms%mod*inv[len]%mod);}
    inline node operator +(node b){return node(len+b.len,sum+b.sum,Sum(sump,b.sump));}
    inline node operator -(node b){return node(len-b.len,sum-b.sum,Dif(sump,b.sump));}
    inline bool operator <(node b)const{
        if(!len) return b.len;if(!b.len) return 0;
        return (db)sum/len<(db)b.sum/b.len;
    }
}Su[N];
inline node Get(int l,int r){if(!l&&!r) return node();return Su[r]-Su[l-1];}
struct seg{
    int ls,rs,L,R,Rls;
    inline void Merge(seg LS,seg RS){L=LS.L,R=max(RS.R,LS.R);Rls=LS.Rls;}
}T[MAXN];int cnt=0;
int prelen[N],suflen[N];
int preans[N],sufans[N];
int rtpre[N],rtsuf[N];
node stk[N];int top=0;
inline node Pack(int i){return node(1,A[i],(ll)A[i]*A[i]%mod);}
void Modify(int&u,int l,int r,int p,int ML,int MR){
    T[++cnt]=T[u];u=cnt;
    if(l==r) {T[u].ls=T[u].rs=0,T[u].L=ML,T[u].R=MR;T[u].Rls=MR;return;}
    int mid=(l+r)>>1;
    if(mid>=p) Modify(T[u].ls,l,mid,p,ML,MR);
    else       Modify(T[u].rs,mid+1,r,p,ML,MR);
    T[u].Merge(T[T[u].ls],T[T[u].rs]);
    return;
}
inline int Query_Suf(int u,int l,int r,int p){
    if(l==r) return T[u].R;int mid=(l+r)>>1;
    if(mid>=p) return Query_Suf(T[u].ls,l,mid,p);return Query_Suf(T[u].rs,mid+1,r,p);
}
inline int Query_Pre(int u,int l,int r,int p,node&Re){
    if(r<=p) {
        node tw=Get(T[u].Rls+1,T[u].R),tl=Get(T[u].L,T[u].Rls);
        if(!(tl<(Re+tw))) {Re=Re+Get(T[u].L,T[u].R);return 0;}
        if(l==r) return T[u].R;
    }int mid=(l+r)>>1,pos=0;
    if(p>mid) pos=Query_Pre(T[u].rs,mid+1,r,p,Re);
    if(pos) return pos;return Query_Pre(T[u].ls,l,mid,p,Re);
}
int main()
{
    freopen("sequence.in","r",stdin);
    freopen("sequence.out","w",stdout);
    init(n),init(m);for(int i=1;i<=n;++i) {init(A[i]);Su[i]=Su[i-1]+Pack(i);}
    inv[1]=1;for(int i=2;i<=n;++i) inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;top=0;
    for(int i=1;i<=n;++i) {
        rtpre[i]=rtpre[i-1];stk[++top]=Pack(i);
        while(top>1&&stk[top]<stk[top-1]) stk[top-1]=stk[top]+stk[top-1],Modify(rtpre[i],1,n,top,0,0),--top;
        Modify(rtpre[i],1,n,top,i-stk[top].len+1,i);
        preans[i]=Sum(preans[i-stk[top].len],stk[top].Calc());
        prelen[i]=top;
    }top=0;
    for(int i=n;i;--i) {
        rtsuf[i]=rtsuf[i+1];stk[++top]=Pack(i);
        while(top>1&&stk[top-1]<stk[top]) stk[top-1]=stk[top]+stk[top-1],Modify(rtsuf[i],1,n,top,0,0),--top;
        Modify(rtsuf[i],1,n,top,i,i+stk[top].len-1);
        sufans[i]=Sum(sufans[i+stk[top].len],stk[top].Calc());
        suflen[i]=top;
    }printf("%d\n",preans[n]);
    while(m--){
        int x,y;init(x),init(y);int dat=A[x];A[x]=y;
        int l=0,r=suflen[x+1]-1,pos=r+1;
        while(l<=r){
            int mid=(l+r)>>1,rp=mid? Query_Suf(rtsuf[x+1],1,n,suflen[x+1]-mid+1):x;
            node val=Pack(x)+Get(x+1,rp);
            int lp=x>1? Query_Pre(rtpre[x-1],1,n,prelen[x-1],val):1;
            if(val<Get(rp+1,Query_Suf(rtsuf[x+1],1,n,suflen[x+1]-mid))) pos=mid,r=mid-1;
            else l=mid+1;
        }
        int rp=pos? Query_Suf(rtsuf[x+1],1,n,suflen[x+1]-pos+1):x;
        node val=Pack(x)+Get(x+1,rp);
        int lp=x>1? Query_Pre(rtpre[x-1],1,n,prelen[x-1],val):1;
        printf("%d\n",Sum(val.Calc(),Sum(preans[lp],sufans[rp+1])));
        A[x]=dat;
    }return 0;
}