Solution. LG3863 序列
Description
给定长度为 $n$ 的序列,$q$ 次操作,操作有两种:
- 区间加减;
- 查询某个位置上的数在多少个历史版本中 $\ge k$。
$2\le n,q\le 10^5$
给定长度为 $n$ 的序列,$q$ 次操作,操作有两种:
$2\le n,q\le 10^5$
在 $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$
关于树上背包的上下界优化,当时 fz 推荐我读的是 ouuan 的文章(cnblogs github pages),但是,我现在认为那里面的复杂度证明存在问题。
给定一个大小为 $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$