CF1479

# Solutions

# A

人类智慧

考虑 $a_0=a_{n+1}=\texttt{INF}$ 。

那可以二分中间一个端点，若他是下降的由于最后一项是上升故后面一定有个合法答案，反之亦然。

# B

贪心。

考虑两个栈，若与栈顶有一个不同则直接放更优，否则。。。。讨论一下

# C

看到就会想到二进制分拆

考虑 $[1,2^n-1]$ 如何构造，大概是每个点表示一个二进制位，向外连的边都是 $2$ 的整次幂… 这样子。

考虑如何构造 $[1,2^n]$ 则新建一个点，朝上面那张图每个点连条为 $1$ 的边即可。

考虑如何构造 $[1,a]$ ，把 $a$ 二进制分拆一下，对于一个不为最高位的 $1$ ，形如 $100....1000$ 此类的，我们新建一个点，把上面那张图的代表这一位的点，向他连一条 $1000...$ 的边，即可连出 $100..0000 \to 100...1000$ 之间的边，由于最后可能会出现长度为 $0$ 的点，不妨把 $a$ 先减去 $1$ ，最后连接终点时再加上。

考虑构造 $[l,r]$ 就直接起点连一条 $l-1$ 边，构造一张 $[1,r-l+1]$ 的图即可。

# D

考虑模拟赛云的一个神奇东西，把颜色异或起来，剩下的不为 $0$ 就合法，这个玩意很假，随便就可以卡掉。

考虑给相同颜色赋一个一样的随机数，这就不假了。

考虑用主席树维护这个东西，在主席树上二分，每次若左边异或值不为 $0$ 则左边一定存在一组合法解，往那里递归即可。

离散化有小锅，不知为何。