自动搬运

查看原文

来自洛谷，原作者为

	lhm_ sjzez 的一名 OI 学生

搬运于2025-08-24 22:15:20，当前版本为作者最后更新于2020-09-28 21:56:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

发现最优情况一定是一直向一个方向走或先走一段后再回来往回走一段。向左和向右是一样的，只需翻转就能转化为同一个问题了。

考虑枚举走的区间，设走完整个区间后的剩余天数为 $k$，那么对于该区间的最优答案一定是参观区间内权值前 $k$ 大的城市，用主席树实现可以做到 $O(n^2 \log n)$ 的复杂度。

发现随着左端点的变大，其对应的最优的右端点一定是不降的，也就是其具有决策单调性。因为之前的最优的右端点的城市一定是参观的，所以将右端点移出区间是不优的。

像决策单调性的 $DP$ 一样分治解决即可，复杂度为 $O(n \log^2 n)$。

#include<bits/stdc++.h>
#define maxn 100010
#define maxm 3000010
#define mid ((l+r)>>1)
using namespace std;
typedef long long ll;
template<typename T> inline void read(T &x)
{
    x=0;char c=getchar();bool flag=false;
    while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    if(flag)x=-x;
}
int n,s,d,cnt,tot;
ll ans;
int rt[maxn],ls[maxm],rs[maxm];
ll a[maxn],b[maxn],siz[maxm],sum[maxm];
void insert(int l,int r,int pos,int &cur)
{
    int x=++tot;
    ls[x]=ls[cur],rs[x]=rs[cur];
    siz[x]=siz[cur]+1,sum[x]=sum[cur]+b[pos],cur=x;
    if(l==r) return;
    if(pos<=mid) insert(l,mid,pos,ls[cur]);
    else insert(mid+1,r,pos,rs[cur]);
}
ll query(int l,int r,int k,int x,int y)
{
    if(k<=0) return 0;
    if(k>siz[y]-siz[x]) return sum[y]-sum[x];
    if(l==r) return b[l]*k;
    if(k<=siz[rs[y]]-siz[rs[x]]) return query(mid+1,r,k,rs[x],rs[y]);
    return query(l,mid,k-siz[rs[y]]+siz[rs[x]],ls[x],ls[y])+sum[rs[y]]-sum[rs[x]];
}
ll calc(int l,int r)
{
    return query(1,cnt,d-(2*(r-s)+s-l),rt[l-1],rt[r]);
}
void solve(int l,int r,int L,int R)
{
    if(l>r) return;
    if(L==R)
    {
        for(int i=l;i<=r;++i) ans=max(ans,calc(i,L));
        return;
    }
    ll pos=L,mx=calc(mid,L);
    for(int i=L+1;i<=R;++i)
    {
        ll v=calc(mid,i);
        if(v>mx) mx=v,pos=i;
    }
    ans=max(ans,mx),solve(l,mid-1,L,pos),solve(mid+1,r,pos,R);
}
void clear()
{
    for(int i=1;i<=n;++i) rt[i]=0;
    for(int i=1;i<=tot;++i) ls[i]=rs[i]=siz[i]=sum[i]=0;
    tot=0;
}
void work()
{
    clear();
    for(int i=1;i<=n;++i) rt[i]=rt[i-1],insert(1,cnt,a[i],rt[i]);
    for(int i=1;i<=s;++i) ans=max(ans,calc(i,s));
    solve(1,s-1,s+1,n);
}
int main()
{
    read(n),read(s),read(d),s++;
    for(int i=1;i<=n;++i) read(a[i]),b[i]=a[i];
    sort(b+1,b+n+1),cnt=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
    work(),s=n-s+1,reverse(a+1,a+n+1),work(),printf("%lld",ans);
    return 0;
}