+++ date = "2021-07-22T20:20:00+08:00" draft = false tags = [] title = "2021 杭电多校 (“中超联赛”) 第二场" authors = ["xry111"] +++

心态被搞崩了……

I love max and multiply

题意

给定长度为 $n$ 的序列 $a$ 和 $b$，让你对于 $k = 0, 1, \cdots, n - 1$ 算 $$c(k) = \max_{i \cap j \geq k} a(i) b(j)$$

做法

把二进制数看成集合，发现 $i \cap j \geq k$ 的一个充分条件是 $i$ 和 $j$ 都是 $k$ 的超集。这个东西不是必要条件，但不用管它， 先直接把它当充要条件最后强行做一次后缀 max 就行了……

然后就对 $a$ 和 $b$ 做个超集 max，因为有负数还得做个超集 min。 最后要分 $4$ 类讨论才行，因为 amax 和 bmin 相乘或者 amin 和 bmax 相乘是可能得到最大值的，一开始以为一定是 amax 乘 bmax 或者 amin 乘 bmin， 结果 WA 了对拍才发现这地方错了。

I love counting

题意

给定长度为 $n$ 的序列 $c$，$m$ 次询问，每次给出 $l, r, a, b$，问 $[l, r]$ 中本质不同，且异或 $a$ 以后不超过 $b$ 的 $c$ 值有多少。

做法

如果没有区间询问，就直接用 trie 树就行了。

加了区间询问和本质不同以后，就跟昨天的某个题差不多，对询问按 $l$ 倒序以后用树状数组套 trie 好像就行了。然后一算需要开个 $300$ MB 的数组， 内存限制才 $256$ MB。想了 $114514$ 种卡空间方法 (连位段都试了) 以后实在没办法了，只好开始强行写，赛后才写完。

结果交上去居然过了…… 才用了 $100$ MB 内存，原因我暂且蒙在鼓里。

据说正解是 cdq，又事我不会的东西。

I love data structure

待补……

就是个线段树上用矩阵当 lazy 标记的裸题，都不想写了……

为啥比赛的时候要自闭上面那个题不开这个……

已补，用 -fsanitize=undefined 找出了 $1919$ 个溢出。

I love permutation

待补……

俩队友互相演了半天没过，但场上过了 $114$ 个人。