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

心态被搞崩了……

# [I love max and multiply](https://acm.hdu.edu.cn/showproblem.php?pid=6971)

## 题意

给定长度为 $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](https://acm.hdu.edu.cn/showproblem.php?pid=6964)

## 题意

给定长度为 $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](https://acm.hdu.edu.cn/showproblem.php?pid=6967)

<del>待补……</del>

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

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

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

# [I love permutation](https://acm.hdu.edu.cn/showproblem.php?pid=6970)

待补……

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