醒来

· · 题解

我们给所有数减去 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 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);
}