# CF1554

被思维题教育了，B 除了思维做法，还是有 FWT 做法的，而且 FWT 最近刚学，竟然还是没有想到。

题意：

求

$\max_{1\le l<r\le n}(\max_{i=l}^ra_i\times \min_{i=l}^r a_i)$

$n\le 2e5$

题解：

不难发现答案是连续两个乘积的最大值。考虑我们选出的最优 $\min,\max$ 中间还夹了数字 $x$ ，假如 $x > \min$ ，不难发现答案区间延伸到 $x$ 就行，不必延伸到 $\min$ ，这样能使答案更优；假如 $x<\min$ ，因为 $\min$ 的定义，这样是不合法的。

题意：

求

$\max(i\times j - k\times (a_i|a_j))$

$n\le 1e5, k\le100$

题解：

外国人怎么这么贪阿。

考虑 $i\times j$ 的取值，一定是 $[2,n(n-1)]$

而 $k\times (a_i|a_j)$ ，是 $[0,2kn]$ ，发现当 $n$ 大了后将会原大于要减去的。

一系列不等式推导后可得出最大 $i,j$ 取值 $[n-2k,n]$

好像也可以 \texttt{FWT_or} 做，记录一个最大次大值。

题意：

给定 $n,m$ ，求出 $\texttt{n xor 0}$ 到 $\texttt{n xor m}$ 的 \texttt

$n,m\le 1e9$

题解；

由 $a ⊕ b = c$ 可得 $a⊕c = b$ ，所以我们要算出最小的 $b$ 使得 $n ⊕ b \ge m + 1$ ，按二进制位模拟一下就好。

题意：

构造一个长度为 $n$ 的字符串使得所有子串出现次数为奇数。

题解：

考虑由一个字符组成的字符串长度为 $len$ ，若长度为奇数，则其中长度为奇数的子串出现也为奇数，长度为偶数也为偶数；若长度为偶数，则恰恰相反。所以我们只要在中间夹一个没出现过的字符就行。

题意：

一棵树，删掉一个点 $u$ 使得 $a_u$ 等于所有与 $u$ 相连且没被删掉的点的数量，对于每个 $k\in[1,n]$ 求出合法的删点次序使得 $\gcd(a_1,a_2...a_n) = k$

题解：

题意可转化为给每条边定向，每个点的权值就是他的入度。由于最多 $n-1$ 条边，每条边对 $\sum a$ 的贡献为 $1$ ，所以只有 $k|n-1$ 才有可能有方案。

设 $f_i$ 为 $\gcd$ 为 $i$ 的倍数的答案， $f_1$ 等于 2^

如何判断，直接自下往上的给每条边定向，若一个点 $u$ 的儿子们指向它的点数 $cnt\equiv0\pmod k $ ，那直接指向父亲；若 $cnt+1\equiv 0\pmod k$ 则指向自己。

然后对于每个 $f_i$ 容斥一下即可。