[HNOI2019]序列（单调栈+二分）

通过打表证明发现答案就是把序列划分成若干段，每段的b都是这一段a的平均数。50分做法比较显然，就是单调栈维护，每次将新元素当成一个区间插入末尾，若b值不满足单调不降，则将这个区间与单调栈前一个区间合并。

由于题目要求每次只修改一个数，所以可以前后缀拼起来，单调栈要改变，然后发现这个显然满足二分的性质，二分完位置左端点后再二分右端点，写一个可持久化单调栈维护一下就可以了。

还有一种主席树做法，后序可能会补上。

#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int>pii;

typedef long long ll;

const int N=1e5+,mod=;

int n,m,sum,tp1,tp2,a[N],f[N],g[N],inv[N],ans[N],st1[N],st2[N];

ll s[N];

vector<int>G[N];

vector<pii>q[N];

bool cmp(int l,int r,int L,int R,int x,int y)

{return (s[r]-s[l-]+x)*(R-L+)>(s[R]-s[L-]+y)*(r-l+);}

int calc(int l,int r,int x)

{return mod-(s[r]-s[l-]+x)%mod*((s[r]-s[l-]+x)%mod)%mod*inv[r-l+]%mod;}

int main()

{

    scanf("%d%d",&n,&m);

    inv[]=;for(int i=;i<=n;i++)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;

    for(int i=;i<=n;i++)scanf("%d",&a[i]),s[i]=s[i-]+a[i],sum=(sum+1ll*a[i]*a[i])%mod;

    q[].push_back(pii(a[],)),ans[]=sum;

    for(int i=,x,y;i<=m;i++)

    scanf("%d%d",&x,&y),q[x].push_back(pii(y,i)),ans[i]=(sum+1ll*(mod-a[x])*a[x]+1ll*y*y)%mod;

    for(int i=;i<=n;i++)

    {

        while(tp1&&cmp(st1[tp1-]+,st1[tp1],st1[tp1]+,i,,))G[i].push_back(st1[tp1--]);

        st1[++tp1]=i,f[tp1]=(f[tp1-]+calc(st1[tp1-]+,i,))%mod;

    }

    st2[]=n+;

    for(int i=n;i;i--)

    {

        tp1--;

        reverse(G[i].begin(),G[i].end());

        for(int j=;j<G[i].size();j++)

        st1[++tp1]=G[i][j],f[tp1]=(f[tp1-]+calc(st1[tp1-]+,G[i][j],))%mod;

        if(i<n)

        {

            while(tp2&&cmp(i+,st2[tp2]-,st2[tp2],st2[tp2-]-,,))tp2--;

            st2[++tp2]=i+,g[tp2]=(g[tp2-]+calc(i+,st2[tp2-]-,))%mod;

        }

        for(int j=;j<q[i].size();j++)

        {

            int x=q[i][j].first,y=q[i][j].second,l=,r=tp1,mid,now=,d=x-a[i];

            while(l<=r)

            {

                mid=l+r>>;

                if(cmp(st1[mid-]+,st1[mid],st1[mid]+,i,,d))r=mid-;

                else l=mid+,now=mid;

            }

            if(!tp2||!cmp(st1[now]+,i,i+,st2[tp2-]-,d,))

            ans[y]=(1ll*ans[y]+calc(st1[now]+,i,d)+f[now]+g[tp2])%mod;

            else{

                l=,r=tp2-;

                int ret=,cur=;

                while(l<=r)

                {

                    mid=l+r>>;

                    int L=,R=now,Mid,pos=;

                    while(L<=R)

                    {

                        Mid=L+R>>;

                        if(cmp(st1[Mid-]+,st1[Mid],st1[Mid]+,st2[mid]-,,d))R=Mid-;

                        else L=Mid+,pos=Mid;

                    }

                    if(mid&&cmp(st1[pos]+,st2[mid]-,st2[mid],st2[mid-]-,d,))r=mid-;

                    else l=mid+,ret=mid,cur=pos;

                }

                ans[y]=(1ll*ans[y]+calc(st1[cur]+,st2[ret]-,d)+f[cur]+g[ret])%mod;

            }

        }

    }

    for(int i=;i<=m;i++)printf("%d\n",ans[i]);

}

单调栈做法