题目
给定一个长度为 (n) 的序列 (A)，以及 (m) 个操作，每个操作将一个 (A_i) 修改为 (k)。
第一次修改之前及每次修改之后，都要求你找到一个同样长度为 (n) 的单调不降序列 (B)，
使得 (sum_{i=1}^n(A_i-B_i)^2) 最小，并输出最小值。
需要注意的是每次操作的影响都是独立的，也即每次操作只会对当前询问造成影响。
(nleq 10^5,Aleq 10^9)
分析
对于形如最小化 (sum C_i(A_i-m)^2) 的问题，(m) 应取 (large frac{sum C_iA_i}{sum C_i})
而且这个序列 (B) 等同于用单调递增的 (m) 去覆盖，这种问题可以用单调栈维护均值。
考虑比较独立的修改可以离线做，此时 ([1,x)) 和 ((x,n]) 的单调栈都可以求出来。
反向的单调栈原理相同，先倒着做一遍再把出入栈撤销。
修改的位置会修改中间一段，两边依旧是原来的单调栈，
所以可以二分右端点，其位置越靠前，答案越小；
当右端点二分的情况下，再二分左端点，其位置越靠后答案越小。
时间复杂度 (O(nlog ^2 n))
代码
#include <cstdio>
#include <cctype>
#include <stack>
#define rr register
using namespace std;
const int N=100011,mod=998244353;
typedef long long lll; lll s[N];
struct node{int y,next;}q[N]; stack<int>K[N];
int wl[N],wr[N],a[N],_s[N],n,Q,as[N],Tol,Tor,stal[N],star[N],ans[N];
inline signed iut(){
int ans=0; char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}
inline void print(int ans){
if (ans>9) print(ans/10);
putchar(ans%10+48);
}
inline signed mo(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline signed o(int x){return 1ll*x*x%mod;}
inline signed ksm(int x,int y){
rr int ans=1;
for (;y;y>>=1,x=1ll*x*x%mod)
if (y&1) ans=1ll*ans*x%mod;
return ans;
}
struct rec{
lll x; int y;
inline bool operator <=(const rec &t)const{
return (double)x*t.y<=(double)t.x*y;
}
inline signed ans(){return 1ll*o(x%mod)*ksm(y,mod-2)%mod;}
}cl[N],cr[N];
inline rec slope(int l,int r){return (rec){s[r]-s[l-1],r-l+1};}
inline signed Get(int x,int now){
rr int l=0,r=Tol;
while (l<r){
rr int mid=(l+r+1)>>1;
if (cl[mid]<=(rec){s[x-1]-s[stal[mid]]+now,x-1-stal[mid]}) l=mid;
else r=mid-1;
}
return l;
}
inline signed query(int now){
rr int l=0,r=Tor,mid,_l;
while (l<r){
_l=Get(star[mid=(l+r+1)>>1],now);
if ((rec){s[star[mid]-1]-s[stal[_l]]+now,star[mid]-1-stal[_l]}<=cr[mid]) l=mid;
else r=mid-1;
}
_l=Get(star[r],now);
return mo(mo(wl[_l],wr[r]),(rec){s[star[r]-1]-s[stal[_l]]+now,star[r]-stal[_l]-1}.ans());
}
signed main(){
n=iut(),Q=iut(),star[0]=n+1;
for (rr int i=1;i<=n;++i) s[i]=s[i-1]+(a[i]=iut());
for (rr int i=1;i<=n;++i) _s[i]=mo(_s[i-1],o(a[i]));
for (rr int i=1;i<=Q;++i){
rr int x=iut(),y=iut();
q[i]=(node){y-a[x],as[x]},as[x]=i;
}
for (rr int i=n;i;--i){
for (;Tor&&cr[Tor]<=slope(i,star[Tor]-1);K[i].push(star[Tor--]));
star[++Tor]=i,wr[Tor]=mo(wr[Tor-1],(cr[Tor]=slope(i,star[Tor-1]-1)).ans());
}
print(mo(_s[n],mod-wr[Tor]));
for (rr int i=1;i<=n;++i){
--Tor;
for (;!K[i].empty();K[i].pop())
star[++Tor]=K[i].top(),wr[Tor]=mo(wr[Tor-1],(cr[Tor]=slope(star[Tor],star[Tor-1]-1)).ans());
rr int now=mo(_s[n],mod-o(a[i]));
for (rr int j=as[i];j;j=q[j].next)
ans[j]=mo(now,mo(o(a[i]+q[j].y),mod-query(q[j].y)));
for (;Tol&&slope(stal[Tol]+1,i)<=cl[Tol];--Tol);
stal[++Tol]=i,wl[Tol]=mo(wl[Tol-1],(cl[Tol]=slope(stal[Tol-1]+1,i)).ans());
}
for (rr int i=1;i<=Q;++i) putchar(10),print(ans[i]);
return 0;
}