提供另一种维护方式：使用分块，时间复杂度 $O(n\sqrt n)$，但是常数小。

题意

给定一个序列，每次询问单点修改，再求把区间 $[l,r]$ 划分为若干段使每段的和构成的序列是交替的。

性质分析

这部分另外的题解已经讲得很详细了，但为了形成一篇完整的题解，就在这略提几句。

首先发现在最优方案下，一定是划分成一些大段和一些长度为 1 的小段，因为如果小段长度 $>1$，把剩下的分到大段一定不劣。

在最优方案下，合法大段的充要条件是 $\sum_{i=l}^r a_i > a_{l-1}$ 且 $>a_{r+1}$。注意到在不保证最优条件下，这样划分也可以得到正确段数。考虑如下证明：假设一个长度 $>1$ 的小段 $[l,r]$，左侧有大段 $[l_1,r_1]$，右侧大段 $[l_2,r_2]$，若 $a_l<a_r$，那么把右侧变为 $[l+1,r_2]$ 依然合法，反之同理拓展左边；若 $[l,r]$ 在最左侧，若 $a_1<a_{l_2-1}$，那么把 $l_2$ 移动到 $2$，否则新增一段 $[1,l_2-2]$，在最右边同理对称一下。

成满足上述条件的段为好段，发现找好段划分满足最优条件下充要条件，一定可以找出不劣于最优解的答案，且已经证明这样求出的答案不会出现使答案偏大的不合法情况，于是只要计算好段划分即可。

现在的问题变为了，有一些区间 $[l,r]$，要选出一些区间使它们无交，最多选出多少个区间。可以贪心，按照右端点从小到大，尽量选择右端点小的。设 $nxt_i$ 表示若上一个好段结尾为 $i$，那下一个可以接在它后面的好段的最小右端点。于是我们会 $O(n^2)$ 了，暴力修改 $nxt$，然后询问时候暴力计算跳了多少次 $nxt$。需要稍微讨论一下开头结尾是否存在小段，这也是简单的，因为若不存在小段，根据贪心思想第一个大段也被确定了。

感觉每次只修改一位，把整个 $nxt$ 重算一遍过于浪费。发现有重要性质：$nxt_i - i$ 为 $O(\log V)$ 级别。考虑从下个好段中任意一点向左右拓展，每拓展一次需满足当前和 $<$ 拓展的位置，也就是说和至少翻倍，因此 $O(\log V)$ 次拓展后和大于任意一个相邻的数。有这个性质之后，每次修改只会影响 $O(\log V)$ 个位置的 $nxt$。

好像不是略提几句了

快速跳 $nxt$

可以 LCT，但那太蠢了，而且我不会。也可以线段树，是 $\log n \log V$ 的，但是常数不小而且不是很好写。

注意到这部分和 P3203 非常像。借鉴那题的分块，维护 $t_i$ 和 $c_i$ 表示从当前块内一点第一次跳到块外的位置和跳跃次数。

修改的时候，假设 $nxt_i$ 发生变动的区间为 $[l,r]$，首先修改 $[l,r]$ 内的 $t$ 和 $c$，然后修改剩下的和 $l$ 在一个块内的位置的 $t$ 和 $c$，修改可以递推，单个位置 $O(1)$，这部分最多修改 $\log V + \sqrt n$ 和点。

询问时候先跳 $t$，再跳 $nxt$，两段跳跃次数都不超过 $\sqrt n$。

因此最后的复杂度是 $O(n \log^2 V + n\sqrt n)$，稍劣于线段树，但是常数小啊，一发交上去是目前的最优解。

Code

代码不长，但是有一些细节。

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define mod 998244353
#define N 250010
#define int long long
#define szi sizeof(int)
#define il inline
int n,q,sq,a[N],x,y,l,ll,r,rr,nxt[N],p[N],t[N],c[N],ans;
il void cmax(int &x,int y){x=(x>y)?x:y;return ;}
il void cmin(int &x,int y){x=(x<y)?x:y;return ;}
il void upd(int l,int r){
    for(int i=r;i>=l;--i){
        nxt[i]=nxt[i+1];
        for(int j=i+2,s=a[i+2];j<=n&&j-i<=65;s+=a[++j])
            if(s>a[i+1]&&s>a[j+1]){cmin(nxt[i],j);break;}
        if(p[nxt[i]]==p[i]) t[i]=t[nxt[i]],c[i]=c[nxt[i]]+2;
        else t[i]=nxt[i],c[i]=2;
    }
    for(int i=l-1;i>=0&&p[i]==p[l];--i){
        if(p[nxt[i]]==p[i]) t[i]=t[nxt[i]],c[i]=c[nxt[i]]+2;
        else t[i]=nxt[i],c[i]=2;
    }
    return ;
}
il int calc(int l,int r){
    int res=0; --l; if(l>=r) return -inf;
    while(t[l]<r) res+=c[l],l=t[l]; while(nxt[l]<r) res+=2,l=nxt[l];
    return res;
}
signed main(){
    // freopen("a.in","r",stdin);
    // freopen("a.out","w",stdout);
    scanf("%lld",&n),sq=sqrt(n);
    for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
    for(int i=0;i<=n;++i) p[i]=i/sq+1; p[n+1]=p[n]+1;
    nxt[n+1]=n+1,upd(0,n),scanf("%lld",&q);
    while(q--){
        scanf("%lld%lld%lld%lld",&x,&y,&l,&r),++l,a[x]=y;
        upd(max(0ll,x-65),x-1),ans=1,ll=r+1,rr=l-1;
        for(int i=l,s=a[l];i<r;s+=a[++i]) if(s>a[i+1]){ll=i+1;break;}
        for(int i=r,s=a[r];i>l;s+=a[--i]) if(s>a[i-1]){rr=i-1;break;}
        cmax(ans,calc(l,r)+1),cmax(ans,calc(ll,r)+2);
        cmax(ans,calc(l,rr)+2),cmax(ans,calc(ll,rr)+3);
        printf("%lld\n",ans);
    }
    return 0;
}