P11822 [湖北省选模拟 2025] 团队分组 / divide 题解

首先对于字典序最小这一限制我们有个显然的暴力，即对于每个

i

从右往左贪心，能分裂一段就分裂一段，这样可以简单地做到

O(n^2)

。

考虑优化，你发现这题似乎没什么特别好的性质，于是可以考虑加速一下上述贪心中的分裂过程，尽量让一次分裂多分裂几段。

我们设一个阈值

B

，对于每个

i+1\le j \le i+B

的

j

预处理出最后一次分裂分裂出的段为

[i+1,j]

时，每次不停往前跳长度小于等于

B

的串会跳到哪里，以及路径上的贡献，这部分可以直接双指针做到

O(nB)

，如果跳出去的长度大于

B

了可以直接停止处理。

对于询问，我们每次能跳预处理出的段就跳，否则如果上次跳的段长大于

B

了或者下面的部分没被预处理，我们就暴力二分找出下一个要跳过去的段，不难发现二分的次数是

O(\frac{n}{B})

的，令

B=\sqrt{n \log n}

即可得到

O(n \sqrt{n \log n})

的复杂度。

做法跑得挺快的，不用怎么卡常，不过也可能是数据比较水。实现上由于空间限制，

B

只能开到 450 左右，不过似乎

B

开小一点跑得比开大要快。

CPP

#include<bits/stdc++.h>

#define vi vector<int>
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pi pair<int,int>
#define ll long long
#define IL inline
#define For(i,j,k) for(int i=(j);i<=(k);i++)
#define Fol(i,j,k) for(int i=(j);i>=(k);i--)

using namespace std;

#define mod 998244353
#define N 100005
#define B 310

int read(){
    int 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)putchar('-'),x=-x;
    if(x/10)write(x/10);
    putchar(x%10+'0');
}

ll a[N],s[N];
struct Node{
    int cnt,pos,len;ll ans,sum;
    Node(int cnt=0,ll ans=0,ll sum=0,int pos=0,int len=0):cnt(cnt),ans(ans),sum(sum),pos(pos),len(len){}
    Node operator +(const Node &x){
        return Node(x.cnt+cnt,x.ans+ans+cnt*x.sum,x.sum+sum,pos,(len==0?x.len:len));
    }
};
Node f[N][B+2];

int main(){
    int n=read();a[0]=s[0]=1e15;
    For(i,1,n)a[i]=read(),s[i]=s[i-1]+a[i];
    For(i,1,n){
        int j=i;ll sum=0,sum2=a[i];int cur=(i%(B+1));
        For(k,i+1,min(n,i+B)){
            sum+=a[k];
            while(j>=max(i-B+1,1) && sum2<=sum)j--,sum2+=a[j];
            if(j<i-B+1)f[i][k-i]=Node(0,0,0,i,0);
            else{
                if(j==0)f[i][k-i]=Node(1,i+1,i+1,-1,i-j+1);
                else{
                    int las=((j-1)%(B+1));
                    f[i][k-i]=f[j-1][i-j+1]+Node(1,i+1,i+1,j-1,i-j+1);
                }
            }
        }
        Node now=Node(1,i+1,i+1,i,1);int r=i-1,len=1;
        while(r>0){
            if(f[r][len].len!=0){
                Node val=f[r][len];r=val.pos;len=val.len;
                now=val+now;
            }
            if(r<=0)break;
            do{
                int L=0,R=r;
                while(L<R){
                    int mid=(L+R+1)>>1;
                    if(s[r]-(mid==0?0:s[mid-1])>s[r+len]-s[r])L=mid;
                    else R=mid-1;
                }
                now=Node(1,r+1,r+1,L-1,r-L+1)+now;len=r-L+1;r=L-1;
                if(r<=0)break;
            }while(len>B);
            if(r<=0)break;
        }
        if(r==0)write(now.ans+now.sum+1),putchar(' ');
        else write(now.ans),putchar(' ');
    }
    return 0;
}

P11822 [湖北省选模拟 2025] 团队分组 / divide 题解

文章操作

相关推荐

评论

P11822 [湖北省选模拟 2025] 团队分组 / divide 题解