cmll02's blog

A

对于 $i\ge 2$ 令 $a_i=a_{i+1}-(n-i)$，然后检验序列是否合法。

B

$k$ 奇数时对奇偶位置分别排序，否则直接排序。

C

一直减 lowbit 直到 $x=2^k$，然后一直减去 $\frac x 2$。

D

显然操作方式是唯一的：从上到下扫每一行，操作这行当前所有的 $1$ 位置。

操作完之后可以维护 $l(i,j),r(i,j)$ 表示这个位置是否是一个形状的左/右端点。

E

a
暴力方法是枚举 $(a_i,a_j)$，两人从 $or$ 的高位到低位遍历，如果 $or$ 的这位是 $1$ 但是当前操作的这个人手上这位是 $0$ 他就可以直接确定自己小了；否则他会说不知道并给另一人。此时另一人收到“对方这一位是 $1$”的信息，于是如果他是 $0$ 可以直接报告；否则开始处理下一个 $or$ 中的 $1$ 位。比如说：

Alice：11011
Bob：11001
Or：11111
（第4位）Alice：不知道（Alice：我第4位是1）
（第4位Bob是1，于是处理第3位）Bob：不知道（Bob：我第三位是1）
（第3位Alice是1，于是处理第1位）Alice：不知道（Alice：我第一位是1）
（第1位Bob是0，Bob确信a>b）Bob：知道

这样就 $n^2\log w$ 了，注意到这个东西可以搬上字典树。建字典树后对每个数计算 $a=x$ 的贡献。

// x：a
// d：第几位
// r：轮到谁
// o：当前字典树结点
void calc(int x,int d,int r,int o=1)
{
	if(d==-1)return;
	if(o==0)return;
	if(x>>d&1)
	{
		R+=sz[c[o][0]];
		R+=sz[c[o][1]];
		calc(x,d-1,r^1,c[o][1]);
	}
	else
	{
		calc(x,d-1,r,c[o][0]);
	}
}

F

对于一个序列，我们怎么计算他的答案？

一定是每次全局减去最小值，然后删除最小值的位置（删除后两边不连续），然后依次处理剩下的连续段。

我们考虑只在一次操作区间的左端点统计答案。如果对于一个位置 $x$，上一个和他相同的位置是 $y$，那么当 $l\le a_x \le r$ 且 $l\le \max\limits_{y\le i\le x,a_i<a_x}a_i$ 的时候会对答案贡献。二维数点即可。

H

放在另一篇博客了。