自动搬运

查看原文

来自洛谷，原作者为

	dottle Cy@?g|^a

搬运于2025-08-24 22:40:06，当前版本为作者最后更新于2022-09-05 14:08:16，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

我们给所有数减去 $l\sim r$ 的按位与。因为这些位没有影响。

我们给二进制下 1 个数为奇数的数涂上黑色，其余涂上白色。设 $r$ 的最高位是 $p=2^q$。

做好准备以后，先来看看两个显然无解的情况：

1. 答案排列一定是黑白相间的，所以如果原排列中黑色点的个数与白色点相差了 $2$ 及以上，那寄。
2. 如果 $l+p> r$，那大于等于 $p$ 的和小于 $p$ 的根本连不上。

排除掉这两种情况后，其他的情况都是有解的。接下来，先介绍构造的方法，再来证明构造的充分性。

1. 答案排列可以分为两部分，左边一部分小于 $p$，右边一部分大于等于 $p$。

2. 若 $p-l$ 是奇数，则选取 $l$ 作为左边部分最后一个数，$l+p$ 作为右边部分第一个数。

   否则，选取 $r-p$ 作为左边部分最后一个数，$r$ 作为右边部分第一个数。

3. 确定好接口以后，只需解决此问题：构造 $0\sim m$ 的，以 $k$ 作为一个端点的符合要求的排列。

证明：

1. 对于 $0\sim n$ 的排列，考察其中的黑白点个数。若一样多，则任意数都可以作为端点，否则多的那一个数的任意数可以作为端点。

   充分性：仿造构造的方法归纳证明。

2. 左右只会有异色点连边，因为我们已经排除了左右无连边的情况，因此我们只会担心一种情况：

   • 仅有左侧黑色点连向右侧白色点的边，且左侧只能以白色开头，右侧只能以黑色开头。

   我们尝试说明这种情况是不存在的。

   首先考虑左右两侧数的个数，有一边是偶数的话上面已经说了不会有问题，那么考虑两边都是奇数的情况：

   我们证明此时，$(l,l+p)$ 一定满足条件：$l$ 显然可以作为左边的开头，因为 $l$ 右侧的数可以两两配对颜色不同，因此 $l$ 一定是较多的那个。不失一般性地认为 $l$ 是黑色。然后考虑对面那个白色点能否作为开头，可以，否则右边也是黑色点较多，就无解了。

3. 由上述论断，再加上 $l,l+p,r,r-p$ 这四个数一定都在 $[l,r]$ 内，我们就证明了一定可以选择个数为奇数一侧的端点作为开头。

接下来，我们给出构造 $0\sim m-1$ 的，以 $k$ 作为一个端点的符合要求的排列的方法。其充分性的归纳证明蕴含在此构造之中。

先介绍这样一个问题，构造 $0\sim M-1$ 的，$0$ 开头，$k$ 为最后一个元素的排列，其中 $M$ 是 $2$ 的次幂。设构造出的排列为 ${\rm build2^k}(M,k)$。

考虑 $k$ 与 $M/2$ 的大小关系：

1. 若 $k\ge M/2$，只需求出 ${\rm build2^k}(M/2,1)$ 和 ${\rm build2^k}(M/2,k~{\rm xor}~ (M/2+1))$，然后将后者全部异或上 $M/2+1$，然后拼接起来即可。

   例如：$M=8,k=7$

   ${\rm build2^k}(M/2,1)=\{0,2,3,1\}$

   ${\rm build2^k}(M/2,k~{\rm xor}~ (M/2+1))={\rm build2^k}(4,2)=\{0,1,3,2\}$

   ${\rm build2^k}(M,k)=\{0,2,3,1,0{~\rm xor~}5,1{~\rm xor~}5,3{~\rm xor~}5,2{~\rm xor~}5\}=\{0,2,3,1,5,4,6,7\}$

2. 若 $k<M/2$，只需求出 ${\rm build2^k}(M/2,k)$，然后 $a_1,a_1+M/2,a_2+M/2,a_2,\dots$ 这样拼起来即可。

   例如：$M=8,k=2$

   ${\rm build2^k}(M/2,k)=\{0,1,3,2\}$

   ${\rm build2^k}(M,k)=\{0,0+4,1+4,1,3,3+4,2+4,2\}=\{0,4,5,1,3,7,6,2\}$。

设构造出的排列为 ${\rm build}(m,k)$，此排列的第一个元素是 $k$。

考虑 $m-1$ 的最高位 $p=2^q$，分类讨论：

1. 若 $k\ge p$，先求出 $A={\rm build}(m-p,k-p)$，然后再求出 $B={\rm build2^k}(p,1)$，然后根据 $A$ 另一个端点的值 $x$，给 $B$ 全部异或上 $x$，再给 $A$ 全部加上 $p$，就可以了。

   例如：$m=6,k=4$

   $A={\rm build}(2,0)=\{0,1\}$

   $B={\rm build2^k}(4,1)=\{0,2,3,1\}$

   ${\rm build}(m,k)=\{0+4,1+4,0{~\rm xor~}1,2{~\rm xor~}1,3{~\rm xor~}1,1{~\rm xor~}1\}=\{4,5,1,3,2,0\}$

2. 若 $k<p$，设一个 01 变量 $o$。先求 $k$ 的黑白情况，如果是白色（$0$ 也是白色），那就令 $o=1$；否则 $o=0$。 求 ${\rm build2^k(p,k{~\rm xor~ }o)}$ 和 ${\rm build}(m-p,o)$ ，将前者异或上 $o$，后者加上 $p$，拼在一起即可。就不举例子了。

时间复杂度 $O(n)$。

#include<bits/stdc++.h>
using namespace std;
using vi=basic_string<int>;
#define rev(A) reverse(A.begin(),A.end())
void no(){cout<<"No"<<endl;exit(0);}
int l,r,n;
void yes(vi a){
	cout<<"Yes"<<endl;
	cout<<a[0]<<' ';
	string res;
	for(int i=1;i<a.size();i++)
		res+=(char)('a'+(int)log2(a[i]^a[i-1]));
    cout<<res;
	exit(0);
}

vi operator ^ (vi a,int b){for(auto&i:a)i^=b;return a;}

vi build(int n,int k){
	if(n==1)return {0};
	if(n==2)return {0,1};
	int _n=n>>1;
	if(k&_n)
		return build(_n,1)+(build(_n,k^_n^1)^_n^1);
	else{
		vi a=build(_n,k),res;
		for(int i=0;i<_n;i++)
			res+=a[i]^((i&1)*_n),res+=a[i]^((i+1&1)*_n);
		return res;
	}
}

vi buildn(int n,int k){
	int t=log2(n),_t=1<<t;
	if(_t==n)return build(n,1)^k;
	if(k&_t){
		vi x=buildn(n-_t,k-_t),y=build(_t,1);
		y=y^x.back();x=x^_t;
		return x+y;
	}else{
		int p=!(__builtin_popcount(k)&1);
		vi y=build(_t,k^p);y=y^p;rev(y);
		return y+(buildn(n-_t,p)^_t);
	}
}

int main(){
	cin>>l>>r;
	n=r-l+1;
	if(l==r)yes({l});
	
	int yu=~0;
	for(int i=l;i<=r;i++)yu&=i;
	l-=yu,r-=yu;
	int m=1<<(int)log2(r);
	
	int c=0;for(int i=l;i<=r;i++)c+=__builtin_popcount(i)&1;
	if(n<m||abs(c-(n-c))>1)no();
	
	int L=m-l,R=r-m+1,X;
	if((m-l)&1)X=l;else X=r-m;
	vi resA=buildn(L,m-1-X),resB=buildn(R,X);
	rev(resA);for(auto&x:resA)x=m-1-x;
	yes((resA+(resB^m))^yu);
}