题解：P2248 分段
Lucyna_Kushinada
·
·
题解
在想到下面的做法前先猜了一波这题有决策单调性（实际上没有），写完交上去获得了目前本题所有提交中唯一的 80 分。
写出没有限制时的转移方程：
f_i=\min_{j} f_{j-1}+K+S\times (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;
}
```