位运算太有趣辣！

Luogu P7442 「EZEC-7」维护序列

你需要维护一个序列。

这个序列开始时有 2n个数，下标从 0 开始。第 i 个数初始值为 i，需要支持以下三种操作：

0定义 a 为所有下标为偶数的数组成的子序列，b 为所有下标为奇数的数组成的子序列，将 a,b 连接，构成新的序列。

1. 定义 a 为所有下标为奇数的数组成的子序列，b 为所有下标为偶数的数组成的子序列，将 a,b 连接，构成新的序列。

2. 查询下标为 x 的数。

总共将进行 m 次操作。

1≤n≤32，1≤m≤10⁶

（虽然是橙题，但还是想了很久）

一看数据规模就是O(1)找规律啦，但是无脑暴力列表好像是看不出任何结果的（不信可以试试）

我们首先看看操作的本质，设序列中原来位于x的数，进行操作后，到了位置y（从0编号）（注意，这里与题目的查询操作相反）

则y等于    x 在奇数/偶数中的排名 加上 0 或 n（奇数/偶数取决于x本身 , 0还是n取决于操作是0还是1）（n即为序列长度的一半） 

　　那么列出柿子 ：y = (x>>1) + n * (x&1^op)    op表示操作种类，x>>1表示在奇数/偶数中的排名

显然出现了位运算的意思！

感性观察一下，因为0<=x<=(1<

那么对于二进制表示的 x ，上式表示将 x 右移一位，并把消掉的那一位（并上1再异或上op）后补到最左边

每次操作，仅与当前 x 的最低位有关， 且只会影响最高位，那么op的影响是以位计算的

由于异或的可结合性，同一位进行多次操作后，等效于将作用在这一位上的op全部异或起来，再与该位进行运算

并且，对于任意的 x，op的影响是等效的

接下来准备实现了！

　　①我们维护一个变量cnt，表示到当前进行的操作次数，以决定原数要右移多少位到达当前的待操作数

　　　　具体地，令 cnt%=n ，将 x 右侧的 cnt 位移至左侧，再将 x 右移 cnt 位

　　②维护一个操作变量 val ，存储每一位上的操作的异或和，并在操作后同时进行移位

最后 x^val 即得到这些操作后 x 的位置

但是，题目要求位置为 pos 的数是什么（完蛋，看错题了）

不急，我们设 x 经过操作后得到 pos ,并设①的函数为f(x);

　　则要求 x，满足 f(x) ^ val = pos

　　由异或运算性质 x = f ^-1(pos^val)

　　因为 f(x) 是位移函数，所以  f ^-1(x) 很好求，反过来位移就行了

小细节：1<<32 会爆 ull ！注意特判！

code：

uLL n,m,val,cnt,a; 
int main(){
    n=read();m=read();
    for(rint i=1;i<=m;i++){
       uLL op=read(),x=read();
       if(op==1){
          val^=(x<<cnt);
          if((++cnt)==n)cnt=0;
       }
       else{
          uLL k=x&((1<<(n-cnt))-1);
          if((n-cnt)==32)k=x&(((1<<32)-1));
          x=(k<>(n-cnt));
          write(x^val);
       }
    }
}

CF1508B Almost Sorted

题意翻译

如果一个长度为 n 的排列 a 满足对于任意整数 i∈[1,n?1] 都有 a_i+1?≥a_i??1，我们就说这个排列是“几乎有序的”。

给定 n,k，求所有长度为 n 的“几乎有序的”排列中，字典序第 k 小的那个。特别的，如果这样的排列不存在，输出 ?1。T 组数据。

1≤T≤10³;  1≤n,∑n≤10⁵;  1≤k≤10¹⁸;

这题实在是有思维难度，先挂一个dalao的blog（自己讲不清楚）

就是，当发现方案总数为 2^k 时，就可以马上考虑位运算了。

然后凭感觉手推找规律基本能找出来。

CF1491D Zookeeper and The Infinite Zoo

大意：若 x&y=y ，则 x 可以变成 x+y ,询问 u 能否经过若干次变化变成 v 

　　首先一个数肯定是越变越大的，先把 u > v 情况排除掉。

　　我们把变化理解成从 u 中挑选若干个 1 位给 u 加上，可以发现低位不会被高位影响，但低位加上后会引起高位进位变化，

　　所以我们考虑从低位向高位把 u , v 进行匹配 。

　　假如对于其中一段，u 的 1 比 v 多，我们可以加上一些 1 把 u 中多出的 1 消掉，留下 v 中为 1 的位置；也可以加上一段 1 把这些 1 移动到高位；

　　对于其中一段，v 的 1 比 u 少，那只能指望低位挪一些 1 过来。

CF1270C Make Good

深井冰脑筋急转弯

题面：给你一串数字，让你在其中插入最多3个数字(可以不插入)，使得这些数字的总和等于异或的2倍，只要给出任何一种方案即可

　　看到题解的我差点骂出来。。

　　首先加入一个原来的异或和，然后异或和就变成 0 了。。。

　　然后就想怎么搞怎么搞。。。

其实遇到这种奇怪的构造题并不是没有办法

可以自己YY一个模拟程序，然后随便插入一些数字，不断二进制输出异或和和总和，讲不定就能YY出来