[IOI2018]会议

最近打模拟赛遇到的，不得不说非常神仙。

又难打又难调，写篇题解纪念一下。

题目链接：luoguP5044。

Subtask2

我们先来看这个部分分。

这是一个比较显然的区间dp。（虽然我在模拟赛时并没有看出来）

设 $ dp_{l,r} $ 为区间 $ [l,r] $ 的最优解， $ p $ 为这个区间内任何一个最大值的位置。

当 $ l=r $ 时，显然 $ dp_{l,r}=h_l $ 。

否则这个方程有两种转移方式。

当 $ l\ne p $ 时，有转移 $ dp_{l,r}=dp_{l,p-1}+(r-p+1)h_p $ 。

当 $ r\ne p $ 时，有转移 $ dp_{l,r}=dp_{p+1,r}+(p-l+1)h_p $ 。

当 $ l\ne r $ 时，会议在 $ p $ 召开显然不会最优，所以忽略。

其中第一种方式是会议地址在最大值左边的情况，第二种方式会议地址在最大值右边。

因为会议地址在最大值一边时，另一边所有点的代价显然都是区间最大值。

并且显然会议地址只能有上述两种方式。

所以这种dp是正确的。

快乐的 $ O(n^2) $ dp。

喜提 $ 19 $ 分。

正解

我们发现这个dp与区间最大值的位置有关系，所以考虑在笛卡尔树进行dp。

我们首先可以把st表和笛卡尔树建出来（因为 $ n $ 不算特别大，所以还是可以 $ O(n\log n) $ 进行建树的）。

首先我们可以想到的思路是对于笛卡尔树上的每一个节点，我们将它所对应区间的dp值求出来。

但是会发现，虽然这样子是可以预处理的，但是无法处理询问，因为如果数列是递增/递降的，笛卡尔树高就会为 $ n $ 。

并且我们在每一次询问的区间不一定对应着笛卡尔树上恰好一个节点，这个区间很可能是由许多节点“拼起来”的。

那么我们对于每一个询问就要访问这个区间的所有节点，极限情况下要访问 $ O(n) $ 个节点。

时间复杂度为 $ O(nq) $ 。

所以我们只能考虑别的方法。

首先我们根据上面的结论：若区间值不唯一，则最优解的位置一定不在区间最大值。

那么我们可以将一个询问拆成两个：一个是最优解在最大值左边的情况，一个是最优解在最大值右边的情况。（最大值选任何一个）

那么这两个询问显然可以通过同一种方式来处理，我们这里主要讲解第二种询问。

第一种询问可以通过将这个序列翻转，然后再做一遍。

那么拆出的这个询问和原来的询问有什么区别呢？

其他地方没什么不同，但是拆出的这个询问多了一个条件——这个区间左边的值大于等于询问区间内所有数的值。

那么这个时候就会有一个新的可行思路:

假设当前节点所对应的下标为 $ mid $ （也就是对应区间最大值的位置） ，所对应的区间为 $ [l,r] $ 。

那么我们能不能将所有的 $ dp_{l,i}(l\le i\le r) $ 求出来呢？

现在我们假设这个节点的左右儿子的 $ dp $ 值都处理完毕，考虑合并 $ dp $ 值。

对于 $ dp_{l,i}(i

对于 $ dp_{l,i}(i=mid) $ ，有 $ dp_{l,i}=dp_{l,i-1}+h_i $ 。（因为最优解一定不在区间最大值）

对于 $ dp_{l,i}(i>mid) $ ，有 $ dp_{l,i}=\min(dp_{l,mid}+(i-mid)h_{mid},dp_{mid+1,i}(mid-l+1)h_{mid}) $ 。

这个 $ \min $ 的第一个值表示会议地址在最大值左边，第二个值表示会议地址在最大值右边。

和 $ 19 $ 分做法的dp方程差不多。

好像也不好做啊。

我们再来仔细观察，就会发现当 $ mid

再来观察上面的 $ dp $ 方程。随着 $ i $ 的增加，左边的值会增加 $ h_{mid} $ ，而右边的值增加量一定小于等于 $ h_{mid} $ 。

这告诉我们对于这个区间，一定是左边的一部分用第一种决策，剩下的部分都用第二种决策。

所以我们可以二分出这两种决策的分界线。

那么如何转移呢？

对于第二种转移，需要在原来的基础上区间加一个值；对于第一种转移，则需要先区间赋 $ 0 $ ，再加上一个一次函数。

再结合之前二分的需求，我们就可以用一个支持区间赋值、区间增加一次函数（假设常数也算一次函数）的线段树来解决问题。

最后询问只需要在拆出的两次询问中选最小值即可。

代码：

#include
#include
#include
#include
using namespace std;
using pi=pair;
using ll=long long;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
vectorq[750001];
int st[750001][21];
ll tagk[3000001];
ll tagb[3000001];
ll tagf[3000001];
ll num[3000001];
int mid[750001];
ll ans[750001];
int l[750001];
int r[750001];
int h[750001];
int p[750001];
bool flag;
int root;
int n,m;
inline int get_max(int l,int r)
{
    int num=p[r-l],val1=st[l][num],val2=st[r-(1<h[val2]?val1:val2);
    if(!flag) return h[val1]>h[val2]?val1:val2;
    return h[val1]>=h[val2]?val1:val2;
}
void run_st()
{
    for(int i=n;i;i--) for(int j=1;i+(1<>1;
    if(~tagf[p])
    {
        tagk[p*2]=tagk[p*2|1]=tagb[p*2]=tagb[p*2|1]=0;
        tagf[p*2]=tagf[p*2|1]=num[p*2]=num[p*2|1]=tagf[p];
        tagf[p]=-1;
    }
    num[p*2]+=mid*tagk[p]+tagb[p];
    num[p*2|1]+=pr*tagk[p]+tagb[p];
    tagk[p*2]+=tagk[p],tagk[p*2|1]+=tagk[p],tagk[p]=0;
    tagb[p*2]+=tagb[p],tagb[p*2|1]+=tagb[p],tagb[p]=0;
}
void push_up(int p)
{
    num[p]=num[p*2|1];
}
void cover(int p,int pl,int pr,int l,int r,ll y)
{
    if(l<=pl&&pr<=r){ tagk[p]=tagb[p]=0,tagf[p]=num[p]=y;return ;}
    push_down(p,pl,pr);
    int mid=(pl+pr)>>1;
    if(l<=mid) cover(p*2,pl,mid,l,r,y);
    if(mid>1;
    if(x<=mid) return get(p*2,pl,mid,x);
    else return get(p*2|1,mid+1,pr,x);
}
int cal(int p,int pl,int pr,int l,int r,int len,ll dp)
{
    if(pl==pr)
    {
        if(dp+(ll)(pl-l+1)*h[l-1]<=num[p]+(ll)len*h[l-1]) return pl;
        return pl-1;
    }
    push_down(p,pl,pr);
    int mid=(pl+pr)>>1;
    if(l>mid) return cal(p*2|1,mid+1,pr,l,r,len,dp);
    if(mid>=r) return cal(p*2,pl,mid,l,r,len,dp);
    if(dp+(ll)(mid-l+1)*h[l-1]<=num[p*2]+(ll)len*h[l-1]) return cal(p*2|1,mid+1,pr,l,r,len,dp);
    return cal(p*2,pl,mid,l,r,len,dp);
}
void add(int p,int pl,int pr,int l,int r,ll k,ll b)
{
    // printf("add %d %d %d %d %d %lld %lld : %lld\n",p,pl,pr,l,r,k,b,num[p]);
    if(l<=pl&&pr<=r)
    {
        tagk[p]+=k,tagb[p]+=b;
        num[p]+=k*pr+b;
        return ;
    }
    push_down(p,pl,pr);
    int mid=(pl+pr)>>1;
    if(l<=mid) add(p*2,pl,mid,l,r,k,b);
    if(midnum)//(num,mi]
        {
            cover(1,1,n,num+1,mi,0);
            add(1,1,n,num+1,mi,h[num],dp-(ll)num*h[num]);
        }
        if(mi