- 搬题人
- 青鱼和序列：p_b_p_b
- 青鱼和怪兽：Qingyu
- 青鱼和区间：alpha1022
- 青鱼和游戏：ShanLunjiaJian
- 组题人：Qingyu
- 题解：alpha1022, Qingyu, ShanLunjiaJian, p_b_p_b
青鱼和序列
来源：
- 2022 China Collegiate Programming Contest (CCPC) Guilin Site， Problem C
- https://codeforces.com/gym/104008/problem/C
Tutorial by p_b_p_b.
注意到使用操作二会使得序列变成回文串，于是接下来使用操作一和操作二就没有任何区别了。
因此直接枚举第一次使用操作二是在第几轮，以及特判每次都用操作一的情况，即可得到答案。
事实上还可以注意到，只要用过操作二，无论操作序列如何，最终答案都相等，所以枚举也可以省去。
复杂度 $O(n+\log m)$ 。
青鱼和怪兽
来源：
- Petrozavodsk Summer 2014. Day 4. Moscow SU SG Contest, Problem J
TBD
青鱼还在咕，来帮青鱼补一下。
本题难点显然在于打不动了可以重开，因此无脑 dp 会成环。
有环的 dp 的一般解决方案是用未知数把环上的一个点替代掉，然后用未知数把其他所有状态的 dp 值表示出来。
如果设 $dp_{n,m}=x$ ，根据转移方程不难发现，每个状态的 dp 值都可以写成一大堆关于 $x$ 的一次函数取 $\min$ ，且 $x$ 的系数应当都 $\le 1$ 。
一次函数取 $\min$ 会得到一个凸壳，第一条边的斜率 $=1$ ，后续的斜率都 $\le 1$ 。只要暴力维护分段函数，得到 $dp_{n,m}$ 的分段函数 $f(x)$ ，那么答案就是 $x=f(x)$ 的最大的解。之所以要最大是因为 $(n,m)\to (n,m)$ 的转移是不存在的。
直接维护这个分段函数大概是过不去的。但是通过以上的分析不难发现可以二分答案 $x$ ，做一遍 dp ，判断是否有 $dp_{n,m}\le x$ ，如果有就 $ans\le x$ ，否则 $ans>x$ 。这样就做完了。
青鱼和区间
来源：
- CSAcademy Round #35, Counting Quests
- https://csacademy.com/contest/round-35/task/counting-quests/
Tutorial by alpha1022.
题意就是要求用询问区间区分出每道题目。
记覆盖 $i$ 的区间集合为 $S_i$，则所求即 $S_i$ 互不相同，但这并不好直接计算。
接下来我们注意到一个重要性质：对于任意方案，不会存在 $i_1 < i_2 < j_1 < j_2$ 使得 $S_{i_1} = S_{j_1} \ne S_{i_2} = S_{j_2}$。
这个性质使我们联想到括号序列。因此，考虑如下的构造：维护指针 $i$，初始时 $i=1$，每次取 $\max \{ j \mid S_i = S_j \}$，并令 $i=j+1$。注意到，所有区间要么是在某个 $[i+1, j-1]$ 内部，要么是以某个 $i$ 为左端点，某个 $j$ 为右端点。并且，我们至少可以保证可以将每个数区分到某个区间中。
注意到，若确定了分段方案 $[i_1, j_1], [i_2, j_2], \dots, [i_k, j_k]$，则段内的区间可以任意选取，而跨过段的区间选择的方案数就是我们所要求的答案：选择若干 $[1, k]$ 的子区间区分出所有 $k$ 道题的方案数。
因此我们考虑一个容斥：用 $2^{\binom{k+1}2}$ 减去不能区分出所有题目的方案数，同时维护一个背包数组用来计量分段的方案数，由此即可递推得到答案。时间复杂度 $O(n^3)$。
这还是一个生成函数的复合方程，借助拉格朗日反演可以做到 $O(n \log n)$。
青鱼和游戏
来源：
- Polish Olympiad in Informatics 2016, Not Nim
- https://szkopul.edu.pl/problemset/problem/M5CruI5eCu8elnNFHuiXBrvV/site/
Tutorial by ShanLunjiaJian.
算法0
显然青鱼的每一步都会清空一堆。
我们计算青鱼的步数$x$，那么答案就是$2x-1$。
首先考虑一下这个游戏会如何进行。青鱼一旦操作一堆$(x,y)\rightarrow (x,0)$，缺头鱼必然跟着把这一对摊平成$(\lfloor\frac{x}{2}\rfloor,\lceil\frac{x}{2}\rceil)$。如果一对堆都空了，缺头鱼不得不把一步用到别的某对堆$x^\prime,y^\prime$，那么假设$x^\prime\leq y^\prime$，他必然会把这对堆变成$x^\prime+1,y^\prime-1$。
我们将青鱼把一对中大的拿走这个操作称为拿，缺头鱼把一对中有一个$0$的摊平称为摊，缺头鱼把两堆大小相同的一对搞的不同称为炸。如果只有拿和摊，可以发现答案就是$2\sum\limits_i(\lg a_i+1)-1$。炸可能减少步数，并且可以发现如果减少了只可能是减少一步。
看看二进制，设一对是$a,a$，如果$a$的二进制表示全$1$，那么一轮炸-拿-摊可以把$a$的长度减少$1$，如此一直进行$a$的长度次就能在这一对上减少一步，但一旦中断就不可能再减少一步了。如果$a$中有$0$，那么先使用若干轮拿-摊直到全$1$，此时仍然可能减少一步，因此这样做必然不劣。
于是青鱼在一开始会把每一对都搞成全$1$的形状，然后两鱼每次都会选择最长的那一对操作，缺头鱼如此选择是因为最长的最不容易产生作用，青鱼则要逼缺头鱼往短的上走，这个还是比较自然的。青鱼一旦先手操作一堆就会操作干净，因为它上面不可能再省下步数了，而缺头鱼先手操作一堆会让这一堆长度减少$1$。最后每一堆长$1$的都能贡献，不过如果青鱼先手则有一堆不行。
此时我们可以对于每个前缀连续$1$个数求出它的出现次数，然后对着这个数组模拟，复杂度$O(q(n+\log v))$。结合两个答案只跟区间长度相关的特殊性质，可以通过前$6$个测试点。
算法1
当然可以用数据结构维护这个出现次数！前缀和可以通过测试点$7,8$，BiT简单卡卡常可以通过测试点$9,10,11$。
这个做法空间是$O(n\log v)$的，为了砍掉这个$\log v$，我们对底层按$\log v$大小分块，维护块间的BiT，时间复杂度不变而空间变为线性，可以通过$12,13,14$，提交记录，卡卡常大概能过$15,16$。使用avx可能可以直接草过去。
算法2
观察模拟的代码。这是搬题人写的一份代码 :
const int B=40;
inline int query(int l,int r)
{
int c[B+1]={0},p[B+1]=0,g=0;
for(int i=l;i<=r;i++) c[__builtin_clzll(~(a[i]<<__builtin_clzll(a[i])))-1]++,g+=(65-__builtin_clzll(a[i]));
for(int i=B;i>0;i--) c[i-1]+=(c[i]+p[i])/2,p[i-1]=p[i]^(c[i]&1);
return 2*(g-(c[0]-!p[0]))-1;
}其中$c_i$表示前缀连续$1$个数为$i-1$的数的个数；$p_i=0/1$表示进行到$c_i$中的对时的青鱼是先/后手，$g$是不考虑炸的答案。可以发现这里如果把循环各轮的$c,p$分别倒过来组成一个二进制数，我们就是计算了$c$和$p$的和，不过$c$的每一位可以$>1$，并且进到$B$位就停止。接下来使用这个定义的$c,p$(也就是说它们都是倒过来的)。
继续考虑$p$是什么，可以发现它就是$c+p$上"经过"每一位的值的奇偶性的前缀和，也就是说如果向第$i$位发生了一次进位，对$p_{j\geq i}$的贡献就是$\operatorname{xor}$上一个$1$。注意到如果$c$的某位值$\geq 2$则必然向下一位进位，考虑一下发现我们在$c$上做完这些进位，做法就是直接加起来，最后再跑一遍上面的模拟即可。用BiT支持单点修改区间求和，复杂度$O(q(\log n+\log v))$。提交记录。
算法2.5
怎么砍$\log v$?下面这个做法由 hehezhou 发现。喝喝粥好闪，拜谢喝喝粥！
考虑扫过某个$c_i=1$的$i$时会发生什么，发生进位当且仅当$p_i=1$，否则这一位保留$1$，$p_{i+1}$变成$1$。如果$p_i=1$，那么$p_{i+1}=0$，于是$c_{i+1}=1$的话它得到$i$的进位而继续进位，否则它必然不会进位。于是我们知道经过连续的一段$1$之后$p$又变回$1$，而类似$1111$这样的东西它的$c+p$是$00001$。也就是说它不会改变第一个$1$，而在经过第一个$1$之后它的效果就是把每个$1$连续段清空并把连续段后一位赋为$1$。
我们只关心$c_B-\operatorname{not}p_B$(不考虑$B$及以上位的初值)。讨论一下 :
如果$c$全$0$，那么$c_B=p_B=0$。
如果$c_{B-1}=0$，那么$c_B=0,p_B=1$。
如果$c_{B-1}=1,p_{B-1}=0$，那么$c_B=0,p_B=1$。
如果$c_{B-1}=1,p_{B-1}=1$，那么$c_B=1,p_B=0$。
只有第一个case的结果是$1$，所以我们知道$c_B-\operatorname{not}p_B=1$当且仅当$c$全$0$。这样就$O(1)$了。提交记录。
