洛谷 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;
}