IOI2018会议题解

可能更洛谷的阅读体验

很好的题，能够很好的练习枚举最大值转移 DP。

我们一步一步来，顺着 subtask 来走：

有一个显然的想法，就是暴力选取开会的位置，直接做即可，复杂度$O(n^2 q)$。

考虑 sub 2 如何做，首先注意到询问的是一个区间的答案，我们可以暴力预处理出来，但时间复杂度要在$O(n^2)$ 以内，怎么做？注意到我们实际上不用暴力枚举，我们只需要一个区间的最大值出现在哪里，这个最大值将会贡献答案，让后枚举把会议丢在该位置左边还是右边即可。

具体来说，我们设$f(l,r)$ 表示在$[l,r]$ 的位置区间选会议的最小代价，转移是显然的：

$$f(l,r)=\min\left\{f(l,p-1)+(r-p+1) \times a_p,f(p+1,r)+(p-l+1) \times a_{p} \right\}$$

$p$ 即为$[l,r]$ 的最大值，发现这两边形式一致，就可以只考虑一半东西，然后另一半直接将序列翻转再做一遍即可得到，利用 st 表即可做到 19 分。

我们观察这个转移方程，多次涉及区间$\max$ 来进行转移，我们考虑笛卡尔树，不难发现我们枚举的最大值节点就是笛卡尔树的根节点，转移方程实际上就是在对左右儿子的答案进行统计，注意到原题目标准复杂度为$O(q \log n)$，启示我们使用一些数据结构优化。

首先因为这是类似于笛卡尔树的 DP，我们可以考虑类似于树形 DP 的方式，从底往上进行 DP，但是如果直接做仍是$O(n^2)$ 的，怎么办，自底向上合并答案？考虑这个东西我们可以用线段树试试？注意到线段树刚好符合上面的转移方程（甜菜的想法），观察上面的转移方程刚好符合线段树的区间形式。考虑转移，不对暴力转移还是$O(n^2)$ 的啊！我们根据转移方程，。发现$i$ 越小，在左侧所需代价一定越来越小，而$i$ 越来越大的时候，在右侧所需代价也一定越来越小，这两个形似一次函数，具有单调性，考虑线段树二分找交点（俗称转移优化），交点左侧为左侧的 DP 更新，右侧即右侧更新，线段树即可做：

这就是我们所说的枚举最大值转移，枚举最大值转移 DP，实际上就是排列在笛卡尔树结构上的 DP（注意不是真正的笛卡尔树），有点类似于分治的思想。我们利用的是一个笛卡尔树的性质：我们设一个区间$[l,r]$ 最大值的位置为$pos$，发现可以把区间分成$[l,pos]$ 和$[pos,r]$ 两个区间，并且两个区间互不影响，也就是说我左边怎么乱搞放数也不会影响右边的区间。这个时候全局最大值作为区间的端点出现。自底向上类似 “树形 DP” 来合并区间。

代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=8e5+15;
struct Query{
    int l,r;
}qry[MN];
int n,q,ans[MN],h[MN],st[MN][30],arcst[MN][30],lg[MN];
vector<int> pos[MN];

struct Segment{
#define ls p<<1
#define rs p<<1|1

    struct Node{
        int l,r,cov,k,b,lmx,rmx;
    }t[MN<<2];

    void docov(int p){
        t[p].cov=1;
        t[p].k=t[p].b=t[p].lmx=t[p].rmx=0;
    }

    void doadd(int p,int k,int b){
        t[p].k+=k;
        t[p].b+=b;
        t[p].lmx+=k*t[p].l+b;
        t[p].rmx+=k*t[p].r+b;
    } 

    void pushdown(int p){
        if(t[p].cov){
            docov(ls);
            docov(rs);
        }
        if(t[p].k||t[p].b){
            doadd(ls,t[p].k,t[p].b);
            doadd(rs,t[p].k,t[p].b);
        }
        t[p].cov=t[p].k=t[p].b=0;
    }

    void pushup(int p){
        t[p].lmx=t[ls].lmx,t[p].rmx=t[rs].rmx;
    }

    void build(int p,int l,int r){
        t[p].l=l;
        t[p].r=r;
        if(l==r) return;
        int mid=(l+r)>>1;
        build(ls,l,mid);
        build(rs,mid+1,r);
        pushup(p);
    }

    void update(int p,int fl,int fr,int k){
        if(t[p].l>=fl&&t[p].r<=fr){
            doadd(p,0,k);
            return;
        }
        pushdown(p);
        int mid=(t[p].l+t[p].r)>>1;
        if(mid>=fl) update(ls,fl,fr,k);
        if(mid<fr) update(rs,fl,fr,k);
        pushup(p);
    }

    void merge(int p,int fl,int fr,int k,int b){
        if(t[p].l>=fl&&t[p].r<=fr){
            int lv=t[p].l*k+b,rv=k*t[p].r+b;
            if(lv>=t[p].lmx&&t[p].rmx<=rv) return;
            if(t[p].lmx>=lv&&rv<=t[p].rmx){
                docov(p);
                doadd(p,k,b);
                return;
            }
        }  
        pushdown(p);
        int mid=(t[p].l+t[p].r)>>1;
        if(mid>=fl) merge(ls,fl,fr,k,b);
        if(mid<fr) merge(rs,fl,fr,k,b);
        pushup(p);
    }

    int querylmx(int p,int pos){
        if(t[p].l==t[p].r) return t[p].lmx;
        pushdown(p);
        int mid=(t[p].l+t[p].r)>>1;
        if(mid>=pos) return querylmx(ls,pos);
        return querylmx(rs,pos);
    }

    int queryrmx(int p,int pos){
        if(t[p].l==t[p].r) return t[p].rmx;
        pushdown(p);
        int mid=(t[p].l+t[p].r)>>1;
        if(mid>=pos) return queryrmx(ls,pos);
        else return queryrmx(rs,pos);
    }
#undef ls
#undef rs
}s,t;

void initst(){
    for(int j=1;j<=20;j++){
        for(int i=1;i<=n;i++){
            if(i+(1<<j)-1>n) break;
            st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
            if(st[i][j]==st[i][j-1]) arcst[i][j]=arcst[i][j-1];
            else arcst[i][j]=arcst[i+(1<<(j-1))][j-1];
        }
    }
}

int cmp(int l,int r){
    int len=__lg(r-l+1);
    if(st[l][len]>=st[r-(1<<len)+1][len]){
        return arcst[l][len];
    }else return arcst[r-(1<<len)+1][len];
}

void solve(int l,int r){
    if(l>r) return;
    int mid=cmp(l,r);
    solve(l,mid-1);
    solve(mid+1,r);
    for(auto now:pos[mid]){
        ans[now]=h[mid]*(qry[now].r-qry[now].l+1);
        if(qry[now].l<mid){
            ans[now]=min(ans[now],s.querylmx(1,qry[now].l)+h[mid]*(qry[now].r-mid+1));
        }
        if(qry[now].r>mid){
            ans[now]=min(ans[now],t.queryrmx(1,qry[now].r)+h[mid]*(mid-qry[now].l+1));
        }
    }

    int sx=h[mid],tx=h[mid];
    if(l<mid) tx+=t.queryrmx(1,mid-1);
    if(r>mid) sx+=s.queryrmx(1,mid+1);
    s.update(1,mid,mid,sx);
    t.update(1,mid,mid,tx);
    if(l<mid){
        s.update(1,l,mid-1,h[mid]*(r-mid+1));
        s.merge(1,l,mid-1,-1*h[mid],sx+mid*h[mid]);
    }
    if(r>mid){
        t.update(1,mid+1,r,h[mid]*(mid-l+1));
        t.merge(1,mid+1,r,1ll*h[mid],tx-1ll*mid*h[mid]);
    }

}

signed main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>h[i];
        st[i][0]=h[i];
        arcst[i][0]=i;
    }
    for(int i=1;i<=q;i++){
        cin>>qry[i].l>>qry[i].r;
        qry[i].l++;
        qry[i].r++;
    }
    initst();
    for(int i=1;i<=q;i++){
        pos[cmp(qry[i].l,qry[i].r)].push_back(i);
    }
    s.build(1,1,n);
    t.build(1,1,n);
    solve(1,n);
    for(int i=1;i<=q;i++) cout<<ans[i]<<'\n';
    return 0;
}