hdu6606多校第四次04——线段树加速dp

深藏阁楼爱情的钟 2023-10-11 09:10 10阅读 0赞

/* 首先想到二分答案，难点在于如何判断是否有K段，每段和<=mid 把问题转化成求最多有R段，最少有L段，每段的的和<=mid,如果 L<=K<=R 那么显然存在把这个序列分成K段的策略 用dp_max[i]表示到i位最多可分成的段数，那么只要枚举下标为[1,i-1]里所有 pre[j]+mid<=pre[i]的 j , 找到最大的dp_max[j]再+1就是dp_max[i] dp_min[i]同理，然后一旦找到 dp_min[i]<=K<=dp_max[i] 就是可行 可是n的范围是2e5，我们可以用线段树来优化找dp_max[j]的过程：因为找的是所有pre[j]>=pre[i]-mid的j，那直接用线段树维护代表pre[j]的dp_max[j]即可，然后就可以进行查询 要注意处理边界问题(pre[0]=0的情况) 
    */
    #include<bits/stdc++.h>
    using namespace std;
    #define maxn 200005
    #define ll long long
    #define INF 0x3f3f3f3f3f3f
    ll m,k,n,a[maxn],pre[maxn],s[maxn];
    
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    int Max[maxn<<2];
    void pushup(int rt){Max[rt]=max(Max[rt<<1],Max[rt<<1|1]);}
    void update(int pos,int val,int l,int r,int rt){
        if(l==r){
            Max[rt]=val;return;
        }
        int m=l+r>>1;
        if(pos<=m)update(pos,val,lson);
        else update(pos,val,rson);
        pushup(rt);
    }
    int query(int L,int R,int l,int r,int rt){
        if(L<=l && R>=r){
        return Max[rt];}
        int m=l+r>>1,res=-0x3f3f3f3f;
        if(L<=m)res=max(res,query(L,R,lson));
        if(R>m)res=max(res,query(L,R,rson));
        return res;
    }
    int zero;
    int judge(ll mid){
        memset(Max,-0x3f,sizeof Max);
        update(zero,0,1,m,1);
        for(int i=1;i<=n;i++){
            int pos1=lower_bound(s+1,s+1+m,pre[i]-mid)-s; 
            int pos2=lower_bound(s+1,s+1+m,pre[i])-s;
            if(pos1>m)continue;//越界了，不去线段树里查询 
            int tmp=query(pos1,m,1,m,1);//查询区间的最大值
            tmp++;
            if(tmp>=k)return 1;
            else update(pos2,tmp,1,m,1); 
        }
        return 0;
    }
    
    int main(){
        int t;cin>>t;
        while(t--){
            scanf("%lld%lld",&n,&k);
            for(int i=1;i<=n;i++){
                scanf("%lld",&a[i]);
                pre[i]=pre[i-1]+a[i];
                s[++m]=pre[i];
            }
            s[++m]=0;
            sort(s+1,s+1+m);
            m=unique(s+1,s+1+m)-s-1;
            zero=lower_bound(s+1,s+1+m,0)-s;
            
            
            ll mid,ans,L=-INF,R=INF;
            while(L<=R){
                mid=L+R>>1;
                if(judge(mid))
                    ans=mid,R=mid-1;
                else L=mid+1;
            }    
            cout<<ans<<endl;
        }
        return 0;
    }

转载于:https://www.cnblogs.com/zsben991126/p/11268444.html