CF1824D
考虑如何快速计算 \(g(i,j)\)，设 \(nxt_i\) 表示 \(i\) 后面第一个等于 \(i\) 的数，那答案显然是最大的 \(p\) 满足不存在 \(k \in [i,p-1],nxt_k>j\)。
从大到小扫描 \(i\) 这一维，问题变成区间覆盖，区间求历史最值和，显然可以直接上线段树，但是需要卡常。
同时也可以使用颜色段均摊将区间覆盖转化成区间加，这样会难写一些，不过无需卡常。
CF1552G
首先需要发现一个结论：对于所有序列合法等价于对于所有 \(\verb!01!\) 序列合法。
证明：对于所有序列，考虑将 \(\le x\) 的数设为 \(0\)，\(>x\) 的数设为 \(1\)，那么若 \(x\) 取遍所有值生成的 \(\verb!01!\) 序列均合法，原序列显然合法。
但是现在依然只能做到 \(\Theta(2^n)\) 的复杂度，考虑优化。
优化的思路是当我使用过第 \(i\) 次操作后，被第 \(i\) 次操作包含的那些位置一定是前面一些 \(0\)，后面一些 \(1\)。
那么考虑对操作搜索，若一个位置还没有被操作覆盖，我们设它为 \(\verb!?!\)，那么对于当前搜到的操作，它包含的位置一定是一些 \(\verb!0/1!\) 和一些 \(\verb!?!\)，注意到 \(\verb!0/1!\) 是在之前的枚举中确定的，而 \(\verb!?!\) 我们只关心它们之间有几个 \(\verb!0!\) 几个 \(\verb!1!\)，那么复杂度就是每层的 \(\verb!?!\) 个数乘积，显然是 \(\Theta((\dfrac{n}{k}+1)^k)\)
标签：题目,复杂度,笔记,合法,区间,Part2,verb,序列,操作 From： https://www.cnblogs.com/tx-lcy/p/18228912