神奇的二分答案题

根据题目奇奇怪怪的限制，不难发现选择的行和列要连续
为了方便计算，将矩阵转置四次，每次只需考虑行要连续
二分一下ans 进行检验
对于矩阵中的mins 和maxs ，显然二者不能分在一起
根据mins ，maxs 和二分出来的ans ，贪心地确定每个值所在的分组，若不连续则不合法

问题描述：
有n个物品的重量和价值分别是 wi 和 vi。从中选出k个物品使得单位重量的价值最大。

根据定义

$$\sum_{i=1}^{k}v_{i}=x\sum_{i=1}^{k}w_{i}$$

即

$$\sum_{i=1}^{k}\left (v _{i}-xw_{i} \right )=0$$

二分一下x，每次在$\left (v _{i}-xw_{i} \right )$贪心地找前k大的
复杂度$O\left ( nlog^{2}n \right )$

感觉是至今为止做到的最难的数据结构题
什么分块，嵌套，可持久化都没有这题给人的第一感觉难
这题每个数据开一个点都开不下。
考场上见到这题基本上一脸懵逼，想了很久写了个$O\left ( q^{2}\right )$但是不能优化的算法，结果没开LL只有30分
用线段树维护每一行和最后一列，支持单点rank 和insert 两种操作
最大长度为$max\left ( n,m \right )+q$
动态开点减少内存，空间复杂度$O\left ( 4qlog\left ( max\left ( n,m \right )+q\right ) \right )$

当初考场上没有想到如何保存状态，写了个$O\left ( 2^{n} n!\right )$的，拿了70分
dp 数组记录最大深度d ，和已选点状态s
对于每个s ，枚举补集进行更新
枚举补集复杂度为$O\left ( 3^{n}\right )$，总复杂度$O\left ( n3^{n} \right )$

用并查集维护
在代表元素中保存当前段的颜色（$w$），和左右端点（$s，t$）
再用一个桶维护每种颜色的所有段
当且仅当要合并两段颜色相同时进行合并，并更新左右端点
对于每个桶用list 维护，再进行启发式合并，这里偷懒直接用了vector

区间修改，区间查询，基本可以用线段树维护，主要是方差比较难维护
将方差的计算展开

$$\frac{\sum_{i=1}^{n} \left ( a_{i}-\bar{a} \right )^{2}}{n}= \frac{\sum_{i=1}^{n} a_{i}^{2}-2\bar{a}\sum_{i=1}^{n}a_{i}+n\bar{a}^{2}}{n}= -\bar{a}^{2}+\frac{\sum_{i=1}^{n}a_{i}^{2}}{n}$$

对于区间加法

$$\sum_{i=l}^{r}\left ( a_{i}+x \right )^{2}= \sum_{i=l}^{r}a_{i}^{2}+2x\sum_{i=l}^{r}a_{i}+\left ( r-l+1 \right )*x^{2}$$

一看题目就有一种平衡树的气息。
给每本书一个val 来维护相对位置
再用一个pos 数组记录下编号为x的位置$pos[x]$

对于每个节点分别求左-右，右-左的逆序对，将较小的加入答案
原来思路：枚举个数较少的节点的每个数，二分求答案
看完题解发现可以用线段树合并。新技能get

二分答案，dp 检验
dp 不是很好想
f 记录与第一个位置相同个数的最大值
g 记录与第一个位置相同个数的最小值

优化了一下之前Splay