Description

给出一个长度为 $n$ 的数组 $A$ 和长度为 $m$ 的数组 $B$，你需要在一个 $n\times m$ 的网格图上从 $(1,1)$ 走到 $(n,m)$，每次可以移动一个 $(1,0)$、$(0,1)$ 或 $(1,1)$ 的向量，需要保证途径的所有点 $(i,j)$ 都同时满足 $A_i>B_j$ 或同时满足 $A_i<B_j$，问是否存在这样的路径。共 $q$ 次询问。

Read More

Description

给定长度为 $n$ 的序列，$q$ 次操作，操作有两种：

• 区间加减；
• 查询某个位置上的数在多少个历史版本中 $\ge k$。

$2\le n,q\le 10^5$

Read More

CF838C Future Failure

这个游戏性质非常好，因为两个操作其实是独立的，无论进行哪种操作都不会使游戏局面发生太大的变动。

Read More

Description

在 $T\times T$ 的正方形网格上（左下角格点坐标为 $(0,0)$，右上角为 $(T,T)$，共 $(T+1)^2$ 个格点），给定 $n$ 个关键点，保证横纵坐标都互不相同。要求选出尽可能多的关键点，使其按横坐标从小到大排序后，纵坐标也单调增。在此基础上，最小化以相邻两点为对角线的长方形面积总和。

$1\le n\le 2\times 10^5,1\le T\le 10^6$

Read More

Description

给定一个大小为 $n$ 的 multiset $\{a_1,a_2,\dots,a_n\}$，每次取出两个数 $x,y$ 将其删去然后插入 $\dfrac{x+y}{2}$，最终剩下两个数 $A,B$，试最大化 $|A-B|$。

$2\le n\le 10^6,0\le a\le 10^9$

Read More