【题解】[HNOI2019] 序列 主席树+二分+单调栈 Loj3059 —Qiuly

可以猜测，对于最优的 $\rm{B}$ 中的区间 $[L,R]$ 满足该区间内所有数相等，那么如果这个数为 $x$ ，则 $A_L$ 到 $A_R$ 的平均数为 $x$ ，显然这个猜测成立。

然后还有一个显然的结论：区间 $[L,R]$ 的长度越小越好，这也是显然的。

我们考虑没有修改的情况，用单调队列维护当前所有的区间。那么现在的问题是对于新加入的 $A_i$ ，如何和之前的区间合并信息。

假设之前的区间为 $[l,r]$ ，$x=\frac{\sum_{i=l}^{r}A_i}{r-l+1}$ ，那么该区间的贡献为：
$$
\sum_{i=l}^{r}(A_i-x)^2\\
\sum_{i=l}^{r}\left(A_i^2+x^2-2xA_i\right)\\
\sum_{i=l}^{r}A_i^2+(r-l+1)x^2-2x\sum_{i=l}^{r}A_i\\
$$
将 $x=\frac{\sum_{i=l}^{r}A_i}{r-l+1}$ 带入后得到：
$$
\sum_{i=l}^{r}A_i^2-\frac{(\sum_{i=l}^{r}A_i)^2}{r-l+1}
$$
这样的话对于单调队列中的区间，只需要维护其区间和，区间平方和，区间长度即可。

维护单调队列的时候，每一次加入一个新的元素，如果该元素比上一个区间的平均值要小就必须和上一个区间合并，否则新成立一个区间，显然这样是对的。

这样就可以应对无修改的情况，每一次修改的话暴力 $O(n)$ 重新求一遍的话结合无修改可以拿到 $50$ 分的好成绩（

---

考虑如何做 $100$ 分。

对于修改点 $x$ ，一定存在一个 $L,R$ ，使得 $L\leq x\leq R$ ，并且令 $B_L$ 到 $B_R$ 全部等于 $\frac{\sum_{i=L}^{R}A_i}{R-L+1}$ 是最优方案，就是说 $L,R$ 是重新 $O(n)$ 跑一遍单调栈后 $x$ 属于的区间的两个端点。

求出来 $L,R$ 之后，对于 $[1,L]$ 的元素的答案不变，只需要单调栈预处理时记录一下 $[1,L]$ 的答案就行了：

inline void Solve_pre() {
    for(int i=1,top=0;i<=n;++i) {
        sta[++top]=Data(1,a[i],mul(a[i],a[i]));
        while(top>1&&sta[top]<=sta[top-1]) sta[top-1]=sta[top-1]+sta[top],--top;
        pre[i].ans=add(pre[i-sta[top].len].ans,sta[top].calc());
        pre[i].rt=pre[i-1].rt,pre[i].top=top;
        Tree.update(pre[i].rt,1,n,pre[i].top,i-sta[top].len+1,i);
    }
}

$Data$ 维护的分别是长度，总和，平方和。

然后 $[R,n]$ 如法炮制。

inline void Solve_suf() {
    for(int i=n,top=0;i>=1;--i) {
        sta[++top]=Data(1,a[i],mul(a[i],a[i]));
        while(top>1&&sta[top-1]<=sta[top]) sta[top-1]=sta[top-1]+sta[top],--top;
        suf[i].ans=add(suf[i+sta[top].len].ans,sta[top].calc());
        suf[i].rt=suf[i+1].rt,suf[i].top=top;
        Tree.update(suf[i].rt,1,n,suf[i].top,i,i+sta[top].len-1);
    }
}

$\rm{Tree}$ 是主席树，用主席树维护相关信息。

然后考虑二分 $L,R$ ，先二分 $R$ ，再二分 $L$ 。对于一个二分的 $R$ ，如果找得到一个 $L$ 使得其满足 $[L,R]$ 的平均数大于前面一段，小于后面一段，那么这个 $R$ 是合法的。如果可以找到多个 $L$ 满足条件，那么显然使得 $[L,R]$ 长度最小的是最优的。

如果 $R$ 是合法的，那么 $R$ 显然越小越优，毕竟区间越短越优；反之则只能增大 $R$ 。

并且可以注意到，假设是从前往后做了一遍单调栈，那么有若干个区间，显然对于任意一段区间将其分成两半，前一半的平均值一定不比后一段小，不然后一段可以单成一段得到更优的结果。

于是选择 $L$ 的时候，只需要选择前每段的左端点即可，如果选择的不是一整段，对于当前段 $[l,r]$ ，选择 $[k+1,r]$ ，留下 $[l,k]$ ，那么既然要选一定是当前的 $[L,R]$ 的平均值小于上一段 $[l,r]$ 的平均值，选择了 $[l,k]$ 后平均值一定不比 $[k+1,r]$ 的平均值高。

$R$ 也一样。

于是主席树维护每一段，二分 $R$ 时在主席树上二分 $L$ 即可。

讲讲二分 $L$ 的方法。

对于当前的主席树上的区间 $[l,r]$ ，如果 $[mid+1,r]$ 中存在合法的 $L$ ，那么就去右区间，否则只能去左区间。

int queryL(int x,int l,int r,int pos,Data&tmp) {
    if(r<=pos) {
        Data Lval=calc(t[x].l,t[x].k),Rval=calc(t[x].k+1,t[x].r);
        if(Rval+tmp<=Lval) return tmp=tmp+calc(t[x].l,t[x].r),0;
        /*如果第 l 段到第 r 段都要合并就合并了，然后表示没找到 L*/
        if(l==r) return t[x].r;
        /*如果不需要合并且找到了 L 就返回*/
        /*其实 k 是维护的第 l 段的右端点位置*/
    }
    /*pos 是当前 x 所在段编号*/
    /*如果 r 比 pos 还大就需要继续，不可能选择一个大于 x 的 L*/
    /*还有一种情况就是第 l 段不需要合并，也就是说有一个解了，但是不知道这个解具体位置，继续二分，往下走*/
    int res=0;
    if(pos>mid&&(res=queryL(t[x].ch[1],mid+1,r,pos,tmp))) return res;
    return queryL(t[x].ch[0],l,mid,pos,tmp);
}

实际代码中 $L$ 是指上述 $L$ 所在区间的上个区间的右端点，就是 $L-1$ 的位置。

最后输出答案，记得把 $[1,L-1]$ 和 $[R+1,n]$ 的贡献加上。

int res=r+1;
int Rpos=res?Tree.queryR(suf[x+1].rt,1,n,suf[x+1].top-res+1):x;
Data tmp=Data(1,y,mul(y,y))+calc(x+1,Rpos);
flag=true;
int Lpos=x>1?Tree.queryL(pre[x-1].rt,1,n,pre[x-1].top,tmp):x;
printf("%d\n",add(tmp.calc(),add(pre[Lpos].ans,suf[Rpos+1].ans)));
/*注意这里 Lpos 不需要-1，上面已经讲明*/

Code：

居然不是很长。

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=1e5+5;
const int LogN=23;
const int mod=998244353;

namespace _ {
    inline int mul(int x,int y) {return 1ll*x*y%mod;}
    inline int dec(int x,int y) {x-=y;if(x<0) x+=mod;return x;}
    inline int add(int x,int y) {x+=y;if(x>=mod) x-=mod;return x;}
    inline void inc(int&x,int y) {x+=y;if(x>=mod) x-=mod;}
    inline int modpow(int x,int y,int res=1) {
        for(;y;y>>=1,x=mul(x,x)) if(y&1) res=mul(res,x);
        return res;
    }
    template <typename _Tp> inline void IN(_Tp&x) {
        char ch;bool flag=0;x=0;
        while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
        while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
        if(flag) x=-x;
    }
}using namespace _;

int n,m,a[N],inv[N];
struct Root {int rt,ans,top;} pre[N],suf[N];
/*rt(对应线段树根节点编号),ans(前缀/后缀答案),top(当前栈顶)*/
struct Data {
    int len,sqr;ll sum;
    Data(int _1=0,ll _2=0,int _3=0):len(_1),sum(_2),sqr(_3){}
    Data operator + (const Data&b) {return Data(len+b.len,sum+b.sum,add(sqr,b.sqr));}
    Data operator - (const Data&b) {return Data(len-b.len,sum-b.sum,dec(sqr,b.sqr));}
    bool operator < (const Data&b) const {return b.len?(len?1.0*sum/len<1.0*b.sum/b.len:1):0;}
    bool operator <= (const Data&b) const {return len?(b.len?1.0*sum/len<=1.0*b.sum/b.len:0):1;}
    int calc() {return dec(sqr,mul(mul(sum%mod,sum%mod),inv[len]));}
} sum[N],sta[N];
Data calc(int l,int r) {return (!l||!r)?Data(0,0,0):(sum[r]-sum[l-1]);}

struct Segment_Tree {
    #define mid ((l+r)>>1)
    int tot;
    struct Node {int ch[2],l,r,k;} t[N*LogN<<1];
    inline void pushup(int x) {
        t[x].l=t[t[x].ch[0]].l,t[x].r=t[t[x].ch[t[x].ch[1]>0]].r,
        t[x].k=t[t[x].ch[0]].k;
    }
    void update(int&x,int l,int r,int pos,int L,int R) {
        t[++tot]=t[x],x=tot;
        if(l==r) return (void)(t[x].l=L,t[x].r=t[x].k=R);
        (pos<=mid)?update(t[x].ch[0],l,mid,pos,L,R):update(t[x].ch[1],mid+1,r,pos,L,R);
        pushup(x);
    }
    int queryR(int x,int l,int r,int pos) {/*找第 pos 段的右端点*/
        if(l==r) return t[x].r;
        return (pos<=mid)?queryR(t[x].ch[0],l,mid,pos):queryR(t[x].ch[1],mid+1,r,pos);
    }
    int queryL(int x,int l,int r,int pos,Data&tmp) {
        if(r<=pos) {
            Data Lval=calc(t[x].l,t[x].k),Rval=calc(t[x].k+1,t[x].r);
            if(Rval+tmp<=Lval) return tmp=tmp+calc(t[x].l,t[x].r),0;
            if(l==r) return t[x].r; 
        }
        int res=0;
        if(pos>mid&&(res=queryL(t[x].ch[1],mid+1,r,pos,tmp))) return res;
        return queryL(t[x].ch[0],l,mid,pos,tmp);
    }
}Tree;

inline void Solve_pre() {
    for(int i=1,top=0;i<=n;++i) {
        sta[++top]=Data(1,a[i],mul(a[i],a[i]));
        while(top>1&&sta[top]<=sta[top-1]) sta[top-1]=sta[top-1]+sta[top],--top;
        pre[i].ans=add(pre[i-sta[top].len].ans,sta[top].calc());
        /*上一段答案+当前段贡献*/
        pre[i].rt=pre[i-1].rt,pre[i].top=top;
        Tree.update(pre[i].rt,1,n,pre[i].top,i-sta[top].len+1,i);
    }
}
inline void Solve_suf() {
    for(int i=n,top=0;i>=1;--i) {
        sta[++top]=Data(1,a[i],mul(a[i],a[i]));
        while(top>1&&sta[top-1]<=sta[top]) sta[top-1]=sta[top-1]+sta[top],--top;
        suf[i].ans=add(suf[i+sta[top].len].ans,sta[top].calc());
        /*上一段答案+当前段贡献*/
        suf[i].rt=suf[i+1].rt,suf[i].top=top;
        Tree.update(suf[i].rt,1,n,suf[i].top,i,i+sta[top].len-1);
    }
}

int main() {
    IN(n),IN(m),inv[1]=1;
    for(int i=1;i<=n;++i) IN(a[i]),sum[i]=sum[i-1]+Data(1,a[i],mul(a[i],a[i]));
    for(int i=2;i<=n;++i) inv[i]=mul(inv[mod%i],(mod-mod/i));
    Solve_pre();
    Solve_suf();
    printf("%d\n",pre[n].ans);/*pre[n].ans=suf[1].ans*/
    int x,y;
    while(m--) {
        IN(x),IN(y);
        int l=0,r=suf[x+1].top-1;
        /*存在 L=x 或者 R=x 的情况*/
        /*注意每次二分到的 mid 指的是编号为"(x 所在段编号)-mid+1"的段*/
        /*所以 r 的初值为 suf[x+1].top-1, l 的初值为 0*/
        while(l<=r) {
            int Rpos=mid?Tree.queryR(suf[x+1].rt,1,n,suf[x+1].top-mid+1):x;
            Data tmp=Data(1,y,mul(y,y))+calc(x+1,Rpos);
            int Lpos=x>1?Tree.queryL(pre[x-1].rt,1,n,pre[x-1].top,tmp):x;
            if(tmp<calc(Rpos+1,Tree.queryR(suf[x+1].rt,1,n,suf[x+1].top-mid))) r=mid-1;
            /*如果当前 [L,R] 满足比下一段 (即 [R+1,x]) 的平均值要小就合法*/
            else l=mid+1;
        }
        int res=r+1;
        int Rpos=res?Tree.queryR(suf[x+1].rt,1,n,suf[x+1].top-res+1):x;
        Data tmp=Data(1,y,mul(y,y))+calc(x+1,Rpos);
        int Lpos=x>1?Tree.queryL(pre[x-1].rt,1,n,pre[x-1].top,tmp):x;
        printf("%d\n",add(tmp.calc(),add(pre[Lpos].ans,suf[Rpos+1].ans)));
    }
    return 0;
}