UOJ NOI Round 7

Day1 A. 那些你不要的

这放 T1？这放 T1？这放 T1？这放 T1？这放 T1？这放 T1？这放 T1？这放 T1？这放 T1？

首先一眼取中位数，然后被叉掉了．

发现最后剩下的那一个数只能在奇数位置上，于是取奇数位置上的中位数即可．

Day1 B. 比特迷宫

非常好题目，可惜我不会做．

10 ~ 30 pts

考虑一个乱搞，发现当 $b = 2^k - 1$ 时，会构成全 $1$ 的连续段．把连续段按照 $2$ 的整数次幂拆分，可以减少操作次数．

然而这样做上界和暴力一样，那不是寄了吗！考虑上界何时达到，发现形如 $\texttt{0101\dots0101}$ 的序列可以把我们卡满，然而 $b = 2^k$ 时形成的恰好是这样的序列，判掉一些之后可以拿到 30 pts．

97 pts

视奸 u 群的时候看到了一种 乱搞，感觉很厉害！

结合上面的连续段 $\log$ 的做法，能够拿下 97 pts．

100 pts

TODO

Day1 C. 璀璨宝石

只会暴力．

TODO

Day2 A. 火星式选拔

shaber 人想的 shaber 做法．

50 pts

暴力是容易的，考虑如何拿 Subtask 3 的分数．

对于 $k = 1$，经过手玩可以发现，我们要找的是区间 $[l, r]$ 内的第一个 $i$，使得 $b_i > \max\limits_{i < j \le r} a_j$．

考虑离线，扫描询问右端点，过程中维护所有满足条件的 $i$，回答询问的时候二分一下．

考虑 $r - 1 \rightarrow r$ 时造成的影响，其对后缀最大值的影响形如一个区间覆盖，也就是说对于在这个区间内的原本满足条件的 $i$ 需要被重新判定．

显然我们不能暴力判定．这个时候观察到一个性质，对于两个相邻的满足条件的位置 $i, j$，有 $b_i > a_j$，又题目中给出了 $a_i \ge b_i$ 这一条件，那么有 $b_i > b_j$，也就是说满足条件的 $b_i$ 构成的序列单调不升，那么每次被踹掉的位置形如一个后缀．弄一个单调栈处理对 $a_i$ 后缀最值的影响区间，再弄一个栈维护满足条件的 $i$ 就行．

这个 shaber 做法一点扩展性都没有，和正解可以说是一点不沾边．

upd：貌似能做 $k = 1$ 的做法就能弄正解？那还是有点用的！

upd：能做是能做，但是会有一种脱裤子放屁的美感．

100 pts

首先抛弃掉上面那个没有前途的做法．

记 $f_i$ 表示 $i$ 之后第一个能顶掉它的元素位置，这个可以二分简单求得，然后对 $f_i$ 做个倍增就能过掉 $k = 1$ 的部分．

通过手玩样例可以发现，区间内 $b_i$ 前 $k - 1$ 大的元素都会出现在最后的答案中，我们只需要针对第 $k$ 大的元素调整答案．

只有在区间前 $k$ 大的元素都被考虑过后，第 $k$ 大的元素才有可能被顶掉．那么我们找到前 $k$ 大的数中最靠后的那一个，然后找到其后第一个可以顶掉第 $k$ 大的元素的位置，对这个位置倍增查询即可．

静态区间 $k$ 大信息可以通过主席树查询．

Day2 B. 反重：求熵

TODO

Day2 C. 鸽子收费站

TODO