P9334 [JOISC 2023] Mizuyokan 2 (Day2) 题解

一句话题意：给定一个序列，单点修改，区间询问把这个区间划分成若干区间和交替的子段的最大划分段数。

先考虑不带修改且询问一整个区间怎么做，我们称划分中比旁边大的段叫大段，否则叫小段，朴素 dp 是

O(n^3)

的。太蠢了，这个题性质很好，尝试找点性质。

一个非常容易想到的性质是一定存在一组最优解小段长度为 1，否则你可以直接拆出来一个数归到左边或者右边。这样显然不劣。而对于一个大段似乎也存在类似的性质，因为如果大段太长你会发现你很有可能找到一个位置断开这整个段。

尝试更精确地分析一下这种情况什么时候会发生，对于大段里的点

i

，我们能从这个位置分裂当且仅当它小于对应前缀和和后缀和，任意一个条件不满足都不行，但是你注意到如果不满足这个条件，前缀和必然至少翻倍，换言之，对于前缀来说最多只会有

O(\log V)

个这样的节点。

对于后缀来说也是这样的，于是两部分拼起来也只有

O(\log V)

个节点不能断，于是你会发现最优解里大段长度就是

O(\log V)

的。

加上这俩性质就可以快速 dp 了。由于 dp 的本质是每次拼上一段，考虑这个过程能不能用一些手法加速。由于这个拼接的性质很好，考虑贪心，每次尝试拼上一个小段和一个大段，我们贪心地选右端点尽量左的合法大段，但是你注意到此时可能评上的小段不是目前的右端点，不过这也没关系，因为我们总能把目前的大段拉过去或者后面的大段拉过来，简单分讨一下大小关系即可证明。

于是你可以预处理每个点下次跳到的是哪个点并用数据结构加速这个过程，注意一些边界的细节，可能比较繁琐，单点修改也是好做的，因为段长是

O(\log V)

的，因此你可以暴力更新前后

O(\log V)

个点，线段树简单维护一下即可，时间复杂度

O(n \log V \log n)

。

CPP


#include<bits/stdc++.h>

#define ll long long
#define pi pair<int,int>
#define vi vector<ll>
#define cpy(x,y,s) memcpy(x,y,sizeof(x[0])*(s))
#define mset(x,v,s) memset(x,v,sizeof(x[0])*(s))
#define all(x) begin(x),end(x)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ary array
#define eb emplace_back
#define IL inline
#define For(i,j,k) for(ll i=(j);i<=(k);i++)
#define Fol(i,k,j) for(ll i=(k);i>=(j);i--)

using namespace std;

#define B 67
#define N 300005

ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0' || ch>'9')f=(ch=='-'?-1:f),ch=getchar();
    while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x*f;
}
void write(ll x){
    if(x<0)x=-x,putchar('-'); 
    if(x/10)write(x/10);
    putchar(x%10+'0');
}

void debug(auto &&...x){
    ((cerr<<x<<' '),...);
    cerr<<'\n';
}

ll nex[N],a[N],n;

void refresh(ll i){
    ll sum=0;
    For(j,i+2,n){
        sum+=a[j];
        if(sum>a[i+1] && sum>a[j+1]){nex[i]=j;break;}
    }
}

struct info{
    int l,r;
    pi f[B+2];
    info(ll lef=0,ll ri=0){l=lef;r=ri;f[1]=mp(lef,0);}
};
info merge(info x,info y){
    ll l=x.l,r=y.r;
    For(i,1,min(x.r-x.l+1,B)){
        ll pos=x.f[i].fi;
        if(nex[pos]<=r){
            pos=nex[pos];x.f[i].se+=2;
            x.f[i].fi=y.f[pos-y.l+1].fi;x.f[i].se+=y.f[pos-y.l+1].se;
        }
    }
    For(i,y.l,y.r){
        if(i-x.l+1>B)break;
        swap(x.f[i-x.l+1],y.f[i-y.l+1]);
    }
    x.r=y.r;
    return x;
}

struct seg{
    info v[N<<2];
    #define ls (x<<1)
    #define rs ((x<<1)|1)
    #define mid ((l+r)>>1)
    void upd(ll x,ll L,ll R,ll l=0,ll r=n){
        if(l==r)return v[x].l=l,v[x].r=r,v[x].f[1]=mp(l,0),void();
        if(L<=mid)upd(ls,L,R,l,mid);
        if(R>mid)upd(rs,L,R,mid+1,r);v[x]=merge(v[ls],v[rs]);
    }
    info ask(ll x,ll L,ll R,ll l=0,ll r=n){
        if(l>=L && r<=R)return v[x];
        if(L<=mid && R>mid)return merge(ask(ls,L,R,l,mid),ask(rs,L,R,mid+1,r));
        else if(L<=mid)return ask(ls,L,R,l,mid);
        return ask(rs,L,R,mid+1,r);
    }
}T;

int main(){
    #ifdef EAST_CLOUD
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    #endif

    n=read();
    For(i,1,n)a[i]=read();a[n+1]=-1;
    For(i,0,n)nex[i]=n+1;nex[n+1]=n+1;
    For(i,0,n-2)refresh(i);
    Fol(i,n,0)nex[i]=min(nex[i],nex[i+1]);
    ll q=read();T.upd(1,0,n);
    For(i,1,q){
        ll x=read(),val=read(),l=read(),r=read();a[x]=val;l++;
        Fol(j,min(x,n-2),max(0ll,x-B))nex[j]=n+1,refresh(j),nex[j]=min(nex[j],nex[j+1]);
        T.upd(1,max(0ll,x-B),x);
        int ans=1;
        ll sum=0,beg=0,ed=0;
        For(j,l,r-1){
            sum+=a[j];
            if(sum>a[j+1]){beg=j;break;}
        }
        sum=0;
        Fol(j,r,l+1){
            sum+=a[j];
            if(sum>a[j-1]){ed=j-2;break;}
        }
        ans=max(ans,T.ask(1,l-1,r-1).f[1].se+1);
        if(beg && beg<=r-1)ans=max(ans,T.ask(1,beg,r-1).f[1].se+2);
        if(ed && l-1<=ed)ans=max(ans,T.ask(1,l-1,ed).f[1].se+2);
        if(beg && ed && beg<=ed)ans=max(ans,T.ask(1,beg,ed).f[1].se+3);
        write(ans);putchar('\n');
    }

    return 0;
}

P9334 [JOISC 2023] Mizuyokan 2 (Day2) 题解

文章操作

相关推荐

评论

P9334 [JOISC 2023] Mizuyokan 2 (Day2) 题解