洛谷6621 [省选联考 2020 A 卷]魔法商店
Luogu LOJ 分析 根据拟阵的相关理论可以知道：$A$ 是权值最小的基当且仅当 $\forall u\in A,v\notin A$，只要 $(A\backslash\{u\})\cup\{v\}$ 是基，则 $v_u\leq v_v$；权值最大的基的情况同理。这样子就把原题中最小值、最大值的限制转化成了若干组偏序关系。 现在的问题即为 $p=2$ 时的保序回归问题。根据论文中的理论，...
Luogu LOJ 分析 根据拟阵的相关理论可以知道：$A$ 是权值最小的基当且仅当 $\forall u\in A,v\notin A$，只要 $(A\backslash\{u\})\cup\{v\}$ 是基，则 $v_u\leq v_v$；权值最大的基的情况同理。这样子就把原题中最小值、最大值的限制转化成了若干组偏序关系。 现在的问题即为 $p=2$ 时的保序回归问题。根据论文中的理论，...
Luogu 分析 没想到差分 /ll 根据要求的东西，不难想到线性基。现在既然有一个区间询问，而且线性基还很好合并，那么可以想到在外面套一层线段树。 问题是区间修改时一个线性基如何整体异或一个值。考虑差分，变成单点修改，直接把叶节点线性基清空然后 pushup 上去即可。 可以证明 $a_{l..r}$ 的线性基和 $a_l\cup(a_i-a_{i-1})_{l+1..r}$ 的线性基是相...