题解 P5892 【[IOI2014]holiday 假期】

· · 题解

首先我们考虑如果起点为端点，只能往一个方向走怎么办，那么很容易想到暴力枚举最远走到哪个点，然后在这个区间内将剩下的前k大数之和求出来更新答案，其中k是还可以进行的操作数

那么如果起点在中间，那么我们走的方法是怎么样的呢？乍一看好像很复杂，但我们仔细分析一下会发现只有以下四种走法：

  1. 从起点开始向右走
  2. 从起点开始向右走，并且走回到起点
  3. 从起点开始向左走
  4. 从起点开始向左走，并且走回到起点

其中1,4可以组合起来，2,3同理

那么我们容易想到直接DP，用f1,f2,f3,f4分别表示上面的走法，其中f1_i就表示向右走i天最多可以参观多少个景点，其余的同理，那么我们容易想到更新答案：

\max_{i=0}^m \max(f1_i+f4_{m-i},f2_i+f3_{m-i})

那么现在问题就是如何求出f1,f2,f3,f4了，回忆前面的那个暴力的做法，我们发现这个DP有一个明显的决策点，就是最远走到的点

然后再想一下不难发现这个DP满足决策单调性，以f1为例，设f1_i对应的走到最远的点为pos_i，那么对于f1_{i+1}，其能走到的最远的点pos_{i+1}\ge pos_i

然后我们就可以舒舒服服的利用经典的分治法进行处理，那个区间前k大和直接主席树维护即可，最终的复杂度就是O(n\log^2 n)

#include<cstdio>
#include<cstring>
#include<algorithm>
#define RI register int
#define CI const int&
#define Ms(f,x) memset(f,x,sizeof(f))
using namespace std;
const int N=100005,M=300005;
typedef long long LL;
int n,m,st,a[N],pos[M],rst[N],num; LL f1[M],f2[M],f3[M],f4[M],ans;
// f1:toward right; f2:toward right then return; f3:toward left; f4:toward left then return;
class President_Tree
{
    private:
        struct segment
        {
            int ch[2],size; LL sum;
        }node[N*20]; int rt[N],tot;
        #define lc(x) node[x].ch[0]
        #define rc(x) node[x].ch[1]
        #define sz(x) node[x].size
        #define sum(x) node[x].sum
        #define TN CI l=1,CI r=num
        inline void _insert(CI lst,int& now,CI val,CI rv,TN)
        {
            node[now=++tot]=node[lst]; ++sz(now); sum(now)+=rv;
            if (l==r) return; int mid=l+r>>1;
            if (val<=mid) _insert(lc(lst),lc(now),val,rv,l,mid);
            else _insert(rc(lst),rc(now),val,rv,mid+1,r); 
        }
        inline LL _query(CI x,CI y,CI rk,LL ret=0,TN)
        {
            if (l==r) return ret+1LL*rst[l]*rk; int mid=l+r>>1;
            if (rk<=sz(rc(y))-sz(rc(x))) return _query(rc(x),rc(y),rk,ret,mid+1,r);
            else return _query(lc(x),lc(y),rk-(sz(rc(y))-sz(rc(x))),ret+sum(rc(y))-sum(rc(x)),l,mid);
        }
    public:
        inline void insert(CI pos,CI val,CI rv)
        {
            _insert(rt[pos-1],rt[pos],val,rv);
        }
        inline LL query(CI l,CI r,CI rk)
        {
            if (l>r) return 0; return _query(rt[l-1],rt[r],min(rk,r-l+1));
        }
        #undef lc
        #undef rc
        #undef sz
        #undef sum
        #undef TN
}SEG;
#define Itval CI l=1,CI r=m
inline void solve1(CI beg,CI end,Itval)
{
    if (l>r) return; int mid=l+r>>1;
    for (RI i=beg;i<=end;++i) if (mid-(i-st)>=0)
    {
        LL ret=SEG.query(st,i,mid-(i-st));
        if (!pos[mid]||ret>f1[mid]) f1[mid]=ret,pos[mid]=i;
    }
    solve1(beg,pos[mid],l,mid-1); solve1(pos[mid],end,mid+1,r);
}
inline void solve2(CI beg,CI end,Itval)
{
    if (l>r) return; int mid=l+r>>1;
    for (RI i=beg;i<=end;++i) if (mid-(i-st<<1)>=0)
    {
        LL ret=SEG.query(st,i,mid-(i-st<<1));
        if (!pos[mid]||ret>f2[mid]) f2[mid]=ret,pos[mid]=i;
    }
    solve2(beg,pos[mid],l,mid-1); solve2(pos[mid],end,mid+1,r);
}
inline void solve3(CI beg,CI end,Itval)
{
    if (l>r) return; int mid=l+r>>1;
    for (RI i=beg;i<=end;++i) if (mid-(st-i)>=0)
    {
        LL ret=SEG.query(i,st-1,mid-(st-i));
        if (!pos[mid]||ret>f3[mid]) f3[mid]=ret,pos[mid]=i;
    }
    solve3(pos[mid],end,l,mid-1); solve3(beg,pos[mid],mid+1,r);
}
inline void solve4(CI beg,CI end,Itval)
{
    if (l>r) return; int mid=l+r>>1;
    for (RI i=beg;i<=end;++i) if (mid-(st-i<<1)>=0)
    {
        LL ret=SEG.query(i,st-1,mid-(st-i<<1));
        if (!pos[mid]||ret>f4[mid]) f4[mid]=ret,pos[mid]=i;
    }
    solve4(pos[mid],end,l,mid-1); solve4(beg,pos[mid],mid+1,r);
}
#undef Itval
int main()
{
    RI i; for (scanf("%d%d%d",&n,&st,&m),++st,i=1;i<=n;++i)
    scanf("%d",&a[i]),rst[i]=a[i]; sort(rst+1,rst+n+1);
    for (num=unique(rst+1,rst+n+1)-rst-1,i=1;i<=n;++i)
    a[i]=lower_bound(rst+1,rst+num+1,a[i])-rst,SEG.insert(i,a[i],rst[a[i]]);
    Ms(pos,0); solve1(st,min(st+m,n)); Ms(pos,0); solve2(st,min(st+(m>>1),n));
    Ms(pos,0); solve3(max(1,st-m),st); Ms(pos,0); solve4(max(1,st-(m>>1)),st);
    for (i=0;i<=m;++i) ans=max(ans,max(f1[i]+f4[m-i],f2[i]+f3[m-i]));
    return printf("%lld",ans),0;
}