题解：P2248 分段

在想到下面的做法前先猜了一波这题有决策单调性（实际上没有），写完交上去获得了目前本题所有提交中唯一的

80

分。

写出没有限制时的转移方程：

f_i=\min_{j} f_{j-1}+K+S\times (P_{j,i}-Q_{j,i})

P_{j,i}

是该段中所有数的最大值，

Q_{j,i}

是该段中所有数的最小值。

对于一条限制

(x,y)

，假设

x<y

，则对于

i\ge y

，其枚举的决策点

j

需要满足

j>x

。

设

st_i

为

i

对应的最小决策点

j

，对于

(x,y)

，执行

st_y\leftarrow \max(st_y,x+1)

，最后做一遍前缀最大值就能求出。

考虑分治，分治结构如下：

设当前处理区间为 $[l,r]$ ，取 $mid=\lfloor\frac{l+r}{2}\rfloor$ 。
递归处理 $[l,mid]$ 。
处理决策点在 $[l,mid]$ 时对 $[mid+1,r]$ 的贡献。
递归处理 $[mid+1,r]$ 。

P_{j.i}-Q_{j,i}

比较难处理，因为

j\in[l,mid],i\in[mid+1,r]

，考虑分讨，分讨最大值和最小值的下标分别在

mid

的左侧还是右侧，一共有四种情况，这样就能把

[l,mid]

和

[mid+1,r]

独立开来，然后用线段树维护一下就行了，具体见代码，比较好理解。

时间复杂度

O(n\log^2 n)

。

CPP

#include<bits/stdc++.h>
using namespace std;

#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(r);i>=(l);--i)
#define pr pair<int,int>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define bg(x) (x).begin()
#define ed(x) (x).end()

#define N 102510
#define int long long

int n,m,vk,vs,a[N],st[N],f[N];
int ln[N],lx[N],rn[N],rx[N],ar[N];

struct segt{
    #define mid ((l+r)>>1)

    int mn[N<<2];

    inline void un(int k){
        mn[k]=min(mn[k*2],mn[k*2+1]);
    }

    inline void build(int k,int l,int r){
        if(l==r){
            mn[k]=1e18;
            return;
        }
        build(k*2,l,mid);
        build(k*2+1,mid+1,r);

        un(k);
    }

    inline void upd(int k,int l,int r,int p,int d){
        if(l==r){
            mn[k]=d;
            return;
        }
        if(p<=mid){
            upd(k*2,l,mid,p,d);
        }
        else{
            upd(k*2+1,mid+1,r,p,d);
        }

        un(k);
    }

    inline int ask(int k,int l,int r,int L,int R){
        if(L>R){
            return 1e18;
        }
        if(L<=l&&R>=r){
            return mn[k];
        }
        int ans=1e18;

        if(L<=mid){
            ans=min(ans,ask(k*2,l,mid,L,R));
        }
        if(R>mid){
            ans=min(ans,ask(k*2+1,mid+1,r,L,R));
        }

        return ans;
    }

    #undef mid
}t;

inline void sol(int l,int r){
    if(l==r){
        f[l]=min(f[l],f[l-1]+vk);
        return;
    }

    int mid=(l+r)>>1;
    sol(l,mid);

    ln[mid+1]=1e9;
    lx[mid+1]=0;
    per(i,l,mid){
        ln[i]=min(a[i],ln[i+1]);
        lx[i]=max(a[i],lx[i+1]);
    }

    rn[mid]=1e9;
    rx[mid]=0;
    rep(i,mid+1,r){
        rn[i]=min(a[i],rn[i-1]);
        rx[i]=max(a[i],rx[i-1]);
    }

    //mx left mn left
    {
        t.build(1,l,mid);
        rep(i,l,mid){
            t.upd(1,l,mid,i,f[i-1]+vs*(lx[i]-ln[i]));
        }

        int j=mid;
        rep(i,mid+1,r){
            while(j>=l&&(ln[j]>rn[i]||lx[j]<rx[i])){
                j--;
            }
            if(j<l){
                break;
            }

            f[i]=min(f[i],t.ask(1,l,mid,st[i],j)+vk);
        }
    }

    //mx left mn right
    {
        t.build(1,l,mid);
        rep(i,l,mid){
            t.upd(1,l,mid,i,f[i-1]+vs*lx[i]);
        }

        int j=mid,k=mid+1;
        rep(i,mid+1,r){
            while(j>=l&&lx[j]<rx[i]){
                j--;
            }
            while(k-1>=l&&ln[k-1]>=rn[i]){
                k--;
            }
            if(j<l){
                break;
            }

            f[i]=min(f[i],t.ask(1,l,mid,max(st[i],k),j)-vs*rn[i]+vk);
        }
    }

    //mx right mn left
    {
        t.build(1,l,mid);
        rep(i,l,mid){
            t.upd(1,l,mid,i,f[i-1]-vs*ln[i]);
        }

        int j=mid,k=mid+1;
        rep(i,mid+1,r){
            while(j>=l&&ln[j]>rn[i]){
                j--;
            }
            while(k-1>=l&&lx[k-1]<=rx[i]){
                k--;
            }
            if(j<l){
                break;
            }

            f[i]=min(f[i],t.ask(1,l,mid,max(st[i],k),j)+vs*rx[i]+vk);
        }
    }

    //mx right mn right
    {
        ar[mid+1]=1e18;
        int j=mid+1;

        rep(i,mid+1,r){
            while(j-1>=l&&ln[j-1]>=rn[i]&&lx[j-1]<=rx[i]){
                j--;
                ar[j]=min(ar[j+1],f[j-1]);
            }

            if(st[i]<j){
                f[i]=min(f[i],ar[j]+vs*(rx[i]-rn[i])+vk);
            }
            else if(st[i]<=mid){
                f[i]=min(f[i],ar[st[i]]+vs*(rx[i]-rn[i])+vk);
            }
        }
    }

    sol(mid+1,r);
}

signed main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>n>>m>>vk>>vs;

    rep(i,1,n){
        cin>>a[i];
        st[i]=1;
        f[i]=1e18;
    }

    rep(i,1,m){
        int x,y;
        cin>>x>>y;

        if(x>y){
            swap(x,y);
        }
        st[y]=max(st[y],x+1);
    }

    rep(i,1,n){
        st[i]=max(st[i],st[i-1]);
    }

    sol(1,n);

    cout<<f[n]<<'\n';

    return 0;
}

文章操作

相关推荐

评论

题解：P2248 分段