「IOI2018」会议

给定长为 \(n\) 的序列 \(h\)，有 \(q\) 次询问，每次询问在 \([l,r]\) 内找一个点 \(x\)，使得 \([l,r]\) 内每个点到 \(x\) 之间最大值的和（即 \(\sum\limits_{i=l}^x\max\limits_{j=i}^xh_j+\sum\limits_{i=x+1}^r\max\limits_{j=x}^ih_j\)）最小。\(n,q\leqslant 750000,h\leqslant 10^9\) 。

发现这个东西没有什么一般性结论，所以我们考虑dp求解。

设 \(f[l,r]\) 为 \([l,r]\) 的答案。首先我们有一个结论，当区间内值不唯一时，区间的最大值的位置一定不为最优解（因为这样每一个元素的贡献都是最大值）。所以我们可以得到转移方程：

\[ f[l,r]=\min(f[l,mid-1]+(r-mid+1)h[mid],f[mid+1,r]+(mid-l+1)h[mid]) \] 其中 \(mid\) 是最大值的位置（有多个时任何一个都可以）。即我们枚举最优解的位置在最大值的左边/右边。这样就有一个 \(n^2\) 的朴素算法。

我们发现转移方程和区间内的最大值有关系，所以我们尝试用笛卡尔树来优化dp。我们对序列建权值为大根堆的笛卡尔树，并且对每个 \([l,r]\) 的询问暴力展开一次，即求 \(f[l,mid-1]\) 和 \(f[mid+1,r]\)。这时我们发现对于每一个 \(f[l,mid-1]\) 的询问，都可以找到一个笛卡尔树中的点 \(c\)，使得 \(c\) 对应的右端点也为 \(mid-1\)（证明可以考虑 \(mid-1\) 和 \(mid\) 的位置关系）。同理对于每个 \(f[mid+1,r]\) 的询问，都可以找到笛卡尔树中左端点为 \(mid+1\) 的点（如果不展开不一定能找到这个点，这就是为什么要展开的原因）。明显这两类询问是类似的，所以我们只考虑处理 \(f[mid+1,r]\) 这一类，对于 \(f[l,mid-1]\) 这一类可以反转数组和询问以后求得。

根据上面的结论，我们发现对于笛卡尔树中的每一个点，如果它对应的区间是 \([l,r]\)，我们只需要求出 \(f[l,l],f[l,l+1]\dots f[l,r]\) 的值。具体地，如果这个节点对应的点为 \(mid\)，我们先递归左子树和右子树求出 \(f[l,l]\dots f[l,mid-1]\) 和 \(f[mid+1,mid+1]\dots f[mid+1,r]\) 然后考虑推出 \(f[l,mid]\dots f[l,r]\)。

让我们再看一遍转移方程： \[ f[l,r]=\min(f[l,mid-1]+(r-mid+1)h[mid],f[mid+1,r]+(mid-l+1)h[mid]) \] 左边部分随着 \(r\) 的增加，每次增加 \(h[mid]\)，右边部分随着 \(r\) 的增加每次增加量都小于等于 \(h[mid]\)（因为 \(h[mid]\) 是区间内最大的值了）所以说如果某一刻左边的值大于了右边，那么再往后左边的值都会大于右边。

所以我们可以维护一棵线段树，当我们在笛卡尔树上 dfs 完某个点的时候，线段树上位置 \(r\) 存的东西就是 \(f[l,r]\) （\(l\) 是 dfs 到的节点代表区间的左端点）。我们在线段树上二分来找到第一个左边>右边的位置，设为 \(pos\)。那么对于小于 \(pos\) 的位置，相当于先区间覆盖一次再区间加等差数列（换句话说就是用一次函数覆盖）；右边的部分就是一个区间加了。

所以我们的线段树需要支持区间覆盖和区间加等差数列（加一个数也是等差数列啦）。对于询问，找到我们所说的那个点 \(c\) 然后把它丢进对应的桶里，dfs 完一个点的时候计算所有询问的答案。

至于实现我们并不需要显式地建出笛卡尔树，我们开一个 st 表然后 dfs 的时候只需要记录当前区间，递归左右儿子就在 st 表里查询区间最大值的位置就可以了。至于如何把询问挂到节点上，我们只需要把左端点相同的询问放到一个桶里，当 dfs 到一个点时，如果它是父亲的右儿子或者是根节点，那么它就是所有与它 \(l\) 相同的节点中 \(r\) 最大的那个，所以只需要在这类点回答询问就好了。

代码：

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
struct query{int l,r;ll ans[2];}c[750005];
vector<int>v[3000005];
int now,n,f[2000005][20],lg[750005];
ll h[750005];
int merge(int x,int y)
{
    if(h[x]!=h[y])return h[x]>h[y]?x:y;
    if(now)return x<y?x:y;
    return x>y?x:y;
}
int ask(int x,int y)
{
    int t=lg[y-x+1];
    return merge(f[x][t],f[y-(1<<t)+1][t]);
}
struct Segment_Tree
{
    ll tree[3000005],cov[3000005],addk[3000005],addb[3000005];
    //加一个(x-a)*c+d的等差数列
    void init()
    {
        memset(tree,0,sizeof(tree));
        memset(cov,0x80,sizeof(cov));
        memset(addk,0,sizeof(addk));
        memset(addb,0,sizeof(addb));
    }
    void pushdown(int l,int r,int x)
    {
        if(cov[x]!=-2139062144)
        {
            tree[x]=cov[x];
            if(l!=r)cov[x*2]=cov[x],cov[x*2+1]=cov[x],addk[x*2]=addb[x*2]=addk[x*2+1]=addb[x*2+1]=0;
            cov[x]=-2139062144;
        }
        if(addk[x]||addb[x])
        {
            tree[x]+=addb[x]+addk[x]*(r-l);
            if(l!=r)
            {
                int mid=(l+r)>>1;
                addk[x*2]+=addk[x],addb[x*2]+=addb[x];
                addk[x*2+1]+=addk[x],addb[x*2+1]+=addb[x]+(mid+1-l)*addk[x];
            }
            addk[x]=addb[x]=0;
        }
    }
    void add(int l,int r,int x,int a,int b,ll c,ll d)//a恰好加上d
    {
        pushdown(l,r,x);
        if(l>=a&&r<=b)
        {
            addk[x]+=c,addb[x]+=(l-a)*c+d;
            return;
        }
        int mid=(l+r)>>1;
        if(a<=mid)add(l,mid,x*2,a,b,c,d);
        if(b>mid)add(mid+1,r,x*2+1,a,b,c,d);
        pushdown(l,mid,x*2),pushdown(mid+1,r,x*2+1);
        tree[x]=tree[x*2+1];
    }
    void modify(int l,int r,int x,int a,int b,ll c)
    {
        pushdown(l,r,x);
        if(l>=a&&r<=b)
        {
            cov[x]=c;
            addk[x]=addb[x]=0;
            return;
        }
        int mid=(l+r)>>1;
        if(a<=mid)modify(l,mid,x*2,a,b,c);
        if(b>mid)modify(mid+1,r,x*2+1,a,b,c);
        pushdown(l,mid,x*2),pushdown(mid+1,r,x*2+1);
        tree[x]=tree[x*2+1];
    }
    ll query(int l,int r,int x,int a)
    {
        pushdown(l,r,x);
        if(l==r)return tree[x];
        int mid=(l+r)>>1;
        if(a<=mid)return query(l,mid,x*2,a);
        else return query(mid+1,r,x*2+1,a);
    }
    int get(int l,int r,int x,int a,int b,ll c,ll d,int e)
    {
        pushdown(l,r,x);
        if(l==r)return l;
        int mid=(l+r)>>1;
        if(a<=mid&&b>mid)
        {
            pushdown(l,mid,x*2);
            if(c+(mid-(a-1)+1)*d>tree[x*2]+((a-1)-e+1)*d)
                return get(l,mid,x*2,a,b,c,d,e);
            return get(mid+1,r,x*2+1,a,b,c,d,e);
        }
        else if(a<=mid)return get(l,mid,x*2,a,b,c,d,e);
        return get(mid+1,r,x*2+1,a,b,c,d,e);
    }
    ll operator [](int x){return query(1,n,1,x);}
}T;
void dfs(int l,int r,bool s)
{
    int mid=ask(l,r);
    if(l<mid)
    {
        dfs(l,mid-1,0);
        T.modify(1,n,1,mid,mid,T[mid-1]+h[mid]);
    }
    else T.modify(1,n,1,mid,mid,h[mid]);
    if(r>mid)
    {
        dfs(mid+1,r,1);
        int t;
        ll tmp=(l<mid)?T[mid-1]:0;
        if(T[r]+(mid-l+1)*h[mid]>=tmp+(r-mid+1)*h[mid])
            t=r+1;
        else t=T.get(1,n,1,mid+1,r,tmp,h[mid],l);
        //t为第一个使得左>右的位置
        if(t!=mid+1)
        {
            T.modify(1,n,1,mid+1,t-1,tmp);
            T.add(1,n,1,mid+1,t-1,h[mid],2*h[mid]);
        }
        if(t!=r+1)T.add(1,n,1,t,r,0,(mid-l+1)*h[mid]);
    }
    if(s)
    {
        for(int i=0;i<v[l].size();i++)
            c[v[l][i]].ans[now]=T[c[v[l][i]].r];
    }
}
int main()
{
    int q;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%lld",&h[i]),f[i][0]=i;
    for(int i=1;i<=q;i++)scanf("%d%d",&c[i].l,&c[i].r),c[i].l++,c[i].r++;
    again:
    for(int i=1;i<=n;i++)v[i].clear();
    T.init();
    for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
    for(int k=1;k<=19;k++)
        for(int i=1;i<=n;i++)
            f[i][k]=merge(f[i][k-1],f[i+(1<<(k-1))][k-1]);
    for(int i=1;i<=q;i++)
    {
        int t=ask(c[i].l,c[i].r);
        if(t!=c[i].r)v[t+1].push_back(i);
    }
    
    dfs(1,n,1);
    if(!now)
    {
        now=1;
        reverse(h+1,h+n+1);
        for(int i=1;i<=q;i++)
            c[i].l=n-c[i].l+1,c[i].r=n-c[i].r+1,swap(c[i].l,c[i].r);
        goto again;
    }
    else
        for(int i=1;i<=q;i++)
        {
            int t=ask(c[i].l,c[i].r);
            printf("%lld\n",min(c[i].ans[0]+(c[i].r-t+1)*h[t],c[i].ans[1]+(t-c[i].l+1)*h[t]));
        }
    return 0;
}