CF2147I2

xujindong_ · 2025-09-24 14:08:22 · 题解

有简单的爆标做法，轻松构造出 n=1.2\times10^6。

核心思路是有两个块 [l_1,r_1],[l_2,r_2]，每块中的点距离为 1，我们可以 l_2\to r_1\to l_2+1\to r_1-1\cdots 这样跳。

现在我们需要构造块间的转移。考虑倍增两个块的距离，比如设第 i 块的左端点为 2^{i+12}（+12 是为了给块长留空间）。这保证了对于一个两个点分别在块 a,b(a<b) 的点对，和一个在块 c,d(c<d) 的点对，按 b/d 为第一关键字，a/c 为第二关键字就能比出来距离。因此我们直接枚举 i 从小到大，j 从 i-1 到 0，对块 (i,j) 往返跳即可。切换 i 或 j 时需要特殊处理一下，可以用一个距离比上一步大 1 的点中转。

现在已经可以构造出 n=6\times10^5 了。往返跳的过程还可以优化，将块内点的距离改为 k\geq4，设 mid=\frac{(l_1+r_1)}2，放两个中转点 mid+1,mid+2，就可以 l_2\to mid+1\to r_1\to mid+2\to l_2+k\cdots 这样跳。这样可以让步数多一倍。下面是不精细的实现。

#include<bits/stdc++.h>
using namespace std;
const int d=12,bn=48,blen=290;
const long long inf=1e18;
int n,m,cnt;
long long p[bn+5][blen+5];
void out(long long x){
  cout<<x<<' ';
  if(!--n)exit(0);
}
int main(){
  cin>>n>>m;
  if(n==8&&m==6)return puts("1 1 3 6 10 3 11 1"),0;
  for(int i=1;i<=bn;i++)for(int j=0;j<=blen;j++)p[i][j]=(1ll<<(i+d))+j*5-inf;
  for(int i=3;i<=bn;i++){
    for(int j=i-2;j>=1;j--){
      long long mid=(p[j][blen]+p[i][0])/2;
      out(p[i][0]);
      for(int k=1;k<=blen;k++)out(mid+1),out(p[j][blen-k+1]),out(mid+2),out(p[i][k]);
      out(2*p[i][blen]-mid-1);
    }
  }
  return 0;
}