洛谷 P6602 数轴
时光倒流+暴力+尺取
第一次看到这题，是在神子杏的课堂上
这就是一个裸的双指针，洛咕上多倍经验的题太多了。 ——神子杏
那好，我们就用双指针来考虑这道题。
首先可以发现
- 答案区间$ (l,r) $ 一定在某两个标记点之间，也就是说，$l-1 $ 应当是一个有标记点，\(r+1\) 也应是一个有标记的点。
证明很显然，假如右端点的右侧没有标记，那么右端点一定可以继续向右延伸。左端点同理。
往数轴上增加标记不好做，考虑从数轴上拿走标记。我们可以预处理出所有标记点都在数轴上时的答案，也就是输出答案的最后一行。关于这一步，我们可以发现暴力枚举每一个可能的答案区间\((l,r)\)的复杂度为\(O(n^2)\)，这显然是不能接受的。发现每当我们确定一个左端点l，则随着l的增大，r是单调不降的。基于这一性质，考虑用双指针扫一遍，\(O(n)\)美滋滋。
接下来考虑依次删去每一个标记，即将这一标记的权值设为\(0\)，同时统计对应的答案。统计答案的方法同上。但是我们会发现这样单次复杂度最坏是\(O(n)\),不能接受。
还需要注意的是，题目中要求标记个数不大于k，发现k很小，考虑暴力做。可以发现
- 删除一个标记点时，至多只会影响这个点左侧k个和右侧k个点（想一想，为什么）。
所以我们只需要在每次删除时，以\(O(k)\)的复杂度用双指针来找这个标记点的左右能不能作为答案即可。
继续考虑优化。删除一个标记，我们不仅删除它的权值，而且删除这个标记的在数组存储中的下标，枚举端点的时候直接跳过它。没错，我们可以使用一个链表来维护每一个端点的前驱和后继。在删除标记时，只需修改其前驱后继的关系即可。
最后需要特判一种情况：删除上一个标记点时的答案区间为\((l0,r0)\)，删除当前标记点的答案区间为\((l,r)\)，两个区间不是包含关系。这时需要将当前的答案取两者中较大的即可。
则总复杂度为\(O(nk)\)
Code
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e+6+100;
const int inf = 0x7f7f7f7f;
struct Data{
int x,a,tim;
};
int n,m,k;
Data opt[maxn];
int tim[maxn];
int ans[maxn];
int pre[maxn],suc[maxn];
inline int read(){
int v=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-f; ch = getchar();}
while(ch>='0'&&ch<='9'){v=(v<<3)+(v<<1)+ch-'0';ch=getchar();}
return v*f;
}
inline bool cmp(Data x,Data y){
return x.x<y.x;
}
int main(){
n=read();m=read();k=read();
for(register int i=1;i<=n;++i){
opt[i].x=read();opt[i].a=read();opt[i].tim = i;
ans[i] = -1;
}
opt[n+1]=Data{-1,inf,0};
opt[n+2]=Data{m+1,inf,0};
sort(opt+1,opt+n+3,cmp);
for(register int i=1;i<=n+2;++i) tim[opt[i].tim] = i;
for(register int l=1,r=1,cnt=0;r<=n+2;++r){
cnt+=opt[r].a;
while(cnt>k){
cnt-=opt[l++].a;
if(l>r) break;;
}
if(k==0) ans[n] = max(ans[n],opt[r].x-opt[r-1].x-2);
else ans[n]=max(ans[n],opt[r+1].x-opt[l-1].x-2);
}
for(register int i=1;i<=n+2;++i){
if(i!=1)pre[i] = i-1;
suc[i] = i+1;
}
for(register int i=n-1;i>=1;--i){
int t=tim[i+1];
opt[t].a=0;
pre[suc[t]] = pre[t];
suc[pre[t]] = suc[t];
int r=t,lim=t;
for(int p=0;p<=k+10;++p){
r=max(pre[r],2);
lim=min(suc[lim],n+2);
}
for(register int l=r,cnt=0;r<=lim;r=suc[r]){
cnt+=opt[r].a;
while(cnt>k){
cnt-=opt[l].a;
l=suc[l];
}
if(k==0) ans[i] = max(ans[i],opt[r].x-opt[pre[r]].x-2);
else ans[i] = max(ans[i],opt[suc[r]].x-opt[pre[l]].x-2);
}
ans[i]=max(ans[i+1],ans[i]);
}
for(register int i=1;i<=n;++i) printf("%d\n",ans[i]);
return 0;
}
