P5892 holiday 假期题解
前言：
如果您想要过这一道题，需要的前置条件：
- 知道什么是决策单调性。
- 知道可持久化线段树怎么找前 $k$ 大。
- 有耐心看很多文字。
对于第二点，如果您不会的话，可以参考我的学习笔记（专门为过这道题做的）。
链接：https://i.cnblogs.com/posts/edit;postId=17697328
参考博客链接：https://www.luogu.com.cn/blog/hl666/solution-p5892
正解：
注释：若下面的任何一步通过看大佬的题解已经明白的，可以跳过。
-
四种走法：我们发现最终有可能成为答案的走法只有四种，一直向左走，一直向右走，先左走并最终走到右侧，先右走并且最终走到左侧。前两种走法我就不再解释了。对于后两种走法其中一个方面是因为你可能走到最左侧或者最右侧还有很多剩余步数可供消耗，可以用于一些折返。至于其他的走的方式，也很容易举出反例或者利用贪心证明其不是最优。
-
四种方程：上文可知，我们有四种走的方式，因此肯定是四种。
-
最初的状态的设计以及转移的思想：我们可以用 $f_i$来表示从起点走到最远的点是 $i$ 点的最佳答案。因为是最远的点，此时花费的时间最多为 $2\times dis_{start,i}$。那么我们显然可以枚举这个花费的时间，假设为 $cost$，那么我们用于参观的时间就有 $cost-dis_{start,i}$ 这么长，而这个就相当于我在区间 $[ i,start ]$ 中（假设 $i$ 小于 $start$），选择这么多个景点让我参观，贪心一点，我们肯定选前几个是吧。于是就可以用可持久化线段树来找就好。但是我们会发现时间复杂度不太对，在 $n^2\times\log n$ 这样。不仅如此，还会发现就这样设计状态的话，对于后两种很难表示（我个人认为）。
-
优化状态设计。换一个状态，用 $f_i$ 表示用时 $i$ 能有的最佳答案，然后再枚举最远走到的地方，而主要思想并没有变化，至于时间上的问题，可以看第五点理解。
-
优化：其实，仔细看看上面的第三点可以发现，我根本就没有什么转移方程，感觉像暴力一样！但实际上，我们发现，随着你分配的时间更多，我肯定是走的比上一次远更好一些。用类似整体二分的思想分治，二分时间，然后枚举决策点区间找最优，根据当前决策点依单调性保证去除没用的点就好。
-
详细理解优化：如果上面没看懂，可以康康这一点。让我们假设在做先向左再向右的这个情况，此时左侧折返顶点为 $X$，右侧最终到达点为 $Y$，决策单调性保证 $X$ 左侧移动时 $Y$ 也向左侧移动。要是我们已经知道左侧顶点取值范围为 $[L,R]$，我们可以分治他在 $MID$，接着用 $n$ 的时间来看 $Y$ 的位置，并在这段区间不同的前 $k$ 大中找出最有答案，然后接着二分就好啦！最后扫一遍得到答案即可。
-
简化代码（可跳过），发现其实正着做一遍两个转移，反着做一遍同样的两个转移是一样的涅，但是我懒得写新的主席树的函数，就不想这么做涅。
代码：
其实感觉和其他大佬的代码没啥大的区别，关键还是要靠理解啊！
#include<bits/stdc++.h>
using namespace std;
int num[250005];
int lsh[250005];
int buc[250005];
int cnt=0;
vector<int>root;
struct node{
int rs;
int ls;
long long sum;
int val;
}tree[2000005];
inline int addnode(int x){
int ret=++cnt;
tree[ret]=tree[x];
return ret;
}
inline void pushup(int rt){
tree[rt].val=tree[tree[rt].ls].val+tree[tree[rt].rs].val;
tree[rt].sum=tree[tree[rt].ls].sum+tree[tree[rt].rs].sum;
}
inline void build(int rt,int l,int r){
if(l==r){
tree[rt].val=0;
return;
}
tree[rt].ls=++cnt;
tree[rt].rs=++cnt;
int mid=(l+r)>>1;
build(tree[rt].ls,l,mid);
build(tree[rt].rs,mid+1,r);
}
inline int change(int rt,int x,int val,int L,int R){
int now=addnode(rt);
int le=L;
int ri=R;
if(le==ri){
tree[now].val=val;
tree[now].sum=1ll*val*lsh[x];
return now;
}
int mid=(le+ri)>>1;
if(x<=mid){
tree[now].ls=change(tree[now].ls,x,val,L,mid);
}
else{
tree[now].rs=change(tree[now].rs,x,val,mid+1,R);
}
pushup(now);
return now;
}
inline long long get(int Lrt,int Rrt,int k,int L,int R){//求前k大的和
int le=L;
int ri=R;
if(le==ri){
return 1ll*lsh[le]*k;
}
int Lls=tree[Lrt].ls;
int Lrs=tree[Lrt].rs;
int Rls=tree[Rrt].ls;
int Rrs=tree[Rrt].rs;
int rsum=tree[Rrs].val-tree[Lrs].val;
int mid=(L+R)>>1;
if(rsum<k){
return 1ll*(tree[Rrs].sum-tree[Lrs].sum+get(Lls,Rls,k-rsum,L,mid));
}
else{
return 1ll*get(Lrs,Rrs,k,mid+1,R);
}
}
int n,s,d;
inline long long findkth(int le,int ri,int k){
if(k==0||le>ri){
return 0;
}
k=min(k,ri-le+1);
return 1ll*get(root[le-1],root[ri],k,1,n);
}
//----------------------------------------以上是打的可持久化线段树
int pos[250005];
long long f1[250005],f2[250005],f3[250005],f4[250005];
inline void clear(){
memset(pos,0,sizeof(pos));
}
inline void solveleft(int begin,int ed,int l,int r){//看英文名应该懂我在干啥吧
if (l>r){
return;
}
int mid=(l+r)>>1;
for(int i=begin;i<=ed;i++){
if (mid-(i-s)>=0){
long long ret=findkth(s,i,mid-(i-s));
if (!pos[mid]||ret>f1[mid]){
f1[mid]=ret;
pos[mid]=i;
}
}
}
solveleft(begin,pos[mid],l,mid-1);
solveleft(pos[mid],ed,mid+1,r);
}
inline void solverl(int begin,int ed,int l,int r){
if (l>r){
return;
}
int mid=(l+r)>>1;
for(int i=begin;i<=ed;i++){
if (mid-((i-s)*2)>=0){
long long ret=findkth(s,i,mid-(i-s)*2);
if (!pos[mid]||ret>f2[mid]){
f2[mid]=ret;
pos[mid]=i;
}
}
}
solverl(begin,pos[mid],l,mid-1);
solverl(pos[mid],ed,mid+1,r);
}
inline void solveright(int begin,int ed,int l,int r){
if (l>r){
return;
}
int mid=(l+r)>>1;
for(int i=begin;i<=ed;i++){
if (mid-((s-i))>=0){
long long ret=findkth(i,s-1,mid-(s-i));
// cout<<"TEST"<<i<<" "<<s-1<<" "<<mid-(s-i)<<" "<<ret<<endl;
if (!pos[mid]||ret>f3[mid]){
f3[mid]=ret;
pos[mid]=i;
}
}
}
solveright(pos[mid],ed,l,mid-1);
solveright(begin,pos[mid],mid+1,r);
}
inline void solvelr(int begin,int ed,int l,int r){
if (l>r){
return;
}
int mid=(l+r)>>1;
for(int i=begin;i<=ed;i++){
if (mid-((s-i)*2)>=0){
long long ret=findkth(i,s-1,mid-(s-i)*2);
if (!pos[mid]||ret>f4[mid]){
f4[mid]=ret;
pos[mid]=i;
}
}
}
solvelr(pos[mid],ed,l,mid-1);
solvelr(begin,pos[mid],mid+1,r);
}
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9')
x=x*10+ch-'0',ch=getchar();
return x*f;
}
void write(long long x)
{
if(x<0)
putchar('-'),x=-x;
if(x>9)
write(x/10);
putchar(x%10+'0');
return;
}
int main(){
// ios::sync_with_stdio(false);
// cin >> n >> s >> d;
n=read();
s=read();
d=read();
s++;
for(int i=1;i<=n;i++){
num[i]=read();
lsh[i]=num[i];
}
root.push_back(0);
build(0,1,n);
sort(lsh+1,lsh+1+n);
int cntt=unique(lsh+1,lsh+1+n)-lsh-1;
for(int i=1;i<=n;i++){
num[i]=lower_bound(lsh+1,lsh+1+cntt,num[i])-lsh;
root.push_back(change(root[i-1],num[i],++buc[num[i]],1,n));
}
//可持久化线段树模板
findkth(3,5,4);
clear();
solveleft(s,min(s+d,n),1,d);
clear();
solverl(s,min(s+(d*2),n),1,d);
clear();
solveright(max(1,s-d),s,1,d);
clear();
solvelr(max(1,s-d*2),s,1,d);
long long ans=0;
// cout<<cnttt<<endl;
// for(int i=0;i<=d;i++){
// cout<<f1[i]<<" "<<f2[i]<<" "<<f3[i]<<" "<<f4[i]<<endl;
// }
for(int i=0;i<=d;++i){
ans=max(ans,max(f1[i]+f4[d-i],f2[i]+f3[d-i]));
}
cout<<ans;
}
后记：
这道题要算好主席树的大致空间限制，以及要记得由于我们状态和时间有关，应该开到 $n$ 的 $3$ 倍左右比较保险。