题解：AT_abc480_g [ABC480G] Zonal Score Minimization

· · 题解

前言：第一眼就觉得应该要用线段树了……

题目大意

给你一个序列，要求你划分这个序列，使得每个段内的 \max-\min 之和最小，同时满足段长 2\le len。

分析

首先可以列出一个朴素的 DP，为：f_i 代表划分完了前 i 个点。

则不难列出转移式为：f_i=\min\limits_{0\le j\le i-2}\{f_j+\max\limits_{j+1\le k\le i}a_k-\min\limits_{j+1\le k\le i}a_k\}，其中 f_1 为无穷大，因为不符题意。

这个朴素的 DP 时间复杂度显然为 O(N^2) 的，考虑优化。

看到最大最小值想到用单调栈维护。考虑每次右移 i，会怎么更新贡献。

则显然 a_i 会给前面的一段区间贡献为最大或最小值或者不贡献，这里用单调栈分别维护即可。

具体的，以维护最大值为例，建一课线段树，每个位置代表若从 f_x 转移到 f_i 实际贡献，因为反正最后只需要看 f_n 的值。

若更新最大值，则在线段树上给被单调栈弹掉的对应的区间加上 -\max+a_i，相当于一次更新完。维护最小值是类似的，但是一定要注意要变号，因为上面的 DP 式中是带负号的。最后在线段树前 i-2 的位置上取最小值放到 f_i 这里即可。时间复杂度 O(N\log N)。

#include<bits/stdc++.h>
#define int long long
#define N 200005
#define L (p<<1)
#define R (L|1)
#define M ((l+r)>>1)
using namespace std;
int n,m;
struct PT{
    int x,l,r;
};
stack<PT> MAX,MIN;

struct GT{//线段树封装 
    struct T{int min,lazy;}T[N<<3];

    void push(int p){
        if(!T[p].lazy) return;
        T[L].min+=T[p].lazy,T[R].min+=T[p].lazy;
        T[L].lazy+=T[p].lazy,T[R].lazy+=T[p].lazy;
        T[p].lazy=0;return;
    }

    void update(int p){T[p].min=min(T[L].min,T[R].min);}

    void insert(int p,int l,int r,int x,int z){
        if(l==r){T[p].min=z;return;}
        if(M>=x) insert(L,l,M,x,z);
        else insert(R,M+1,r,x,z);
        update(p);return;
    }

    int qry(int p,int l,int r,int x,int y){
        if(l>=x&&r<=y) return T[p].min;
        push(p);int z=1e18;
        if(M>=x) z=min(z,qry(L,l,M,x,y));
        if(M<y) z=min(z,qry(R,M+1,r,x,y));
        update(p);return z;
    }

    void Get(int p,int l,int r,int x,int y,int z){
        if(l>=x&&r<=y){T[p].min+=z;T[p].lazy+=z;return;}
        push(p);
        if(M>=x) Get(L,l,M,x,y,z);
        if(M<y) Get(R,M+1,r,x,y,z);
        update(p);return;
    }
}GT;

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    GT.insert(1,0,n,0,0);//初始化 
    GT.insert(1,0,n,1,1e15);//不符题意，取INF 
    for(int i=1,x;i<=n;i++){
        cin>>x;int p=i;
        while(!MAX.empty()&&MAX.top().x<x){
            PT A=MAX.top();MAX.pop();
            p=A.l;GT.Get(1,0,n,A.l-1,A.r-1,x-A.x);
        }//单调栈维护最大值 
        MAX.push((PT){x,p,i});p=i;
        while(!MIN.empty()&&MIN.top().x>x){
            PT A=MIN.top();MIN.pop();
            p=A.l;GT.Get(1,0,n,A.l-1,A.r-1,A.x-x);
        }//单调栈维护最小值
        MIN.push((PT){x,p,i});
        if(i>=2) GT.insert(1,0,n,i,GT.qry(1,0,n+1,0,i-2));//可以同DP式一起理解！ 
    }cout<<GT.qry(1,0,n,n,n);
    return 0;
}