自动搬运

查看原文

来自洛谷，原作者为

	zhuweiqi 攀峰之高险，岂有崖颠；搏海之明辉，何来彼岸？前进不止，奋斗不息。

搬运于2025-08-24 22:58:00，当前版本为作者最后更新于2024-02-13 23:49:31，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

如果我们将签到点按其坐标从小到大排序，容易发现，对于第 $i$ 个签到点来说，设其是路径上经过的最左边的签到点，如果此路径上经过的最右边的签到点是第 $j$ 个签到点，那么在排除原第 $p$ 个签到点的奖励的干扰下，$i$ 递增时 $j$ 不减，因此考虑用双指针维护。当然也需要考虑原第 $p$ 个签到点的影响。具体操作如下：

第一步，记录原签到点在排序后对应的位置，设原第 $p$ 个签到点排序后对应为第 $st$ 个签到点。

第二步，枚举第 $i$ 个签到点（此处默认为排序后的新编号，下同）作为当前路径的最左端（可以证明这样枚举一定能找到最优解）：

如果 $i\leq st$，讨论能否在时间限制 $+5$ 的情况下到达第 $st$ 个签到点：

• 如果能，将时间限制 $+5$，跳转至第三步。

• 否则，讨论单单往返一次第 $i$ 个签到点会不会超时，会超时直接跳过本轮循环，跳转至第三步。

否则，则说明时间限制无法 $+5$。特别地，注意当 $i=st+1$ 时右指针 $j$ 需要回退，因为第 $st$ 个签到点给的奖励突然消失了。

第三步，用双指针维护出当前情况下能到达的最右边的签到点，这点也需要按 $x_i$ 和 $x_j$ 的正负分类讨论，在此不过多赘述，详见代码。

第四步，得出当前这组答案 $(i,j)$，$ans$ 及时更新，如果其是最优解之一则先记录下 $i$ 这个左指针的位置。

第五步，当 $i$ 枚举完时我们已经得到了各个最优解的左指针的位置，此时我们只需顺序枚举，找到第 $i$ 个签到点在排序后对应的位置，用双指针或者二分筛去期望度不是最大的解，具体地：

• 如果使用二分，则二分查找第一个（即左指针坐标最小的）和最后一个（即左指针坐标最大的）包含此签到点的路径，将答案区间范围缩小（可以证明，答案区间范围一定连续）当然如果没有一条路径包含此签到点，就不能缩小答案区间范围。

• 但是我们能优化成双指针，因为答案区间范围中间不可能有空隙，假设原点左边有一组答案，则路径一定包含原点到其左指针的所有签到点，右边亦是如此，中间不可能有任何一条路径都不包含的签到点。

综上，总时间复杂度为 $O(n\log n)$，但是这个 $O(n\log n)$ 的复杂度是常数小的 sort 快排贡献的，其余双指针相关操作的时间复杂度均为 $O(n)$，所以 $n\leq 10^5$ 的子任务是给第一部分没用双指针的选手准备的，如果复杂度正确通过 $n\leq 10^6$ 的子任务是绰绰有余的。

Std：（仅供参考）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read(){
	ll n=0;
	int f=1;
	char c=getchar();
	while(c<'0' || c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0' && c<='9'){
		n=(n<<3)+(n<<1)+(c^48);
		c=getchar();
	}
	return n*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9) write(x/10);
	putchar(x%10^48);
	return;
}
struct node{
	ll x;
	int idx;
}s[1000002];
bool cmp(node a,node b){return a.x<b.x;}
vector<int> v;
int q[1000002];
int mat[1000002];
int e[1000002];
int main(){
	int n=read();
	ll m=read();
	int p=read();
	for(int i=1;i<=n;i++) s[i].x=read(),s[i].idx=i;
	sort(s+1,s+1+n,cmp);
	for(int i=1;i<=n;i++) mat[s[i].idx]=i;
	int st=mat[p];
	int ans=0;
	int j=1;
	for(int i=1;i<=n;i++){
		int f=0;
		if(i<=st){
			if(s[st].x<=0 && (-s[i].x<<1)<=m+5) f=5;
			if(s[i].x<=0 && 0<=s[st].x && (s[st].x-s[i].x<<1)<=m+5) f=5;
			if(0<=s[i].x && (s[st].x<<1)<=m+5) f=5;
		}
		if(i==st+1) j=i;
		if(f==0 && abs(s[i].x<<1)>m) continue;
		j=max(i,j);
		while(j<=n){
			if(s[j].x<=0) j++;
			else if(s[i].x<=0 && 0<=s[j].x && (s[j].x-s[i].x<<1)<=m+f) j++;
			else if(s[i].x>=0 && (s[j].x<<1)<=m+f) j++;
			else break;
		}
		j--;
		if(j-i+1==ans) v.push_back(i);
		if(j-i+1>ans){
			v.clear();
			ans=j-i+1;
			v.push_back(i);
		}
		j++;
	}
	int cnt=0;
	for(auto it:v) q[++cnt]=it;
	int l=1,r=cnt;
	for(int i=1;i<=n;i++){
		e[i]=mat[i];
		if(e[i]<q[l] || q[r]+ans-1<e[i]) continue;
		while(l<r && q[l]+ans-1<e[i]) l++;
		while(l<r && e[i]<q[r]) r--;
		if(l==r) break;
	}
	write(ans);
	putchar('\n');
	for(int i=q[l];i<=q[l]+ans-1;i++) write(s[i].idx),putchar(' ');
	return 0;
}