考虑特殊性质 B。
限制相当于钦定一些位置的值，其他位置无限制。可以发现性质：无限制的位置上填的值是单调不减的。
证明：设得到的最优序列为 \(A\)，对于无限制的位置 \(i,j\)，若 \(A_i>A_j\)，交换 \(i,j\) 后逆序对个数必然减小。
根据改性质，只需考虑每个位置对已经确定位置的位置的贡献。可以用权值线段树维护。
考虑特殊性质 C。
对于限制 \(L,R,V\)，有限制 \(A_i\ge V,\forall i\in[L,R]\)。同时，\([L,R]\) 中必定有位置等于 \(V\)。发现对 \([L,R]\) 内的数排序是不劣的。故可以钦定 \(A_L=V\)，并且不用考虑该区间内互相产生贡献。发现继续使用 \(B\) 的做法：从左到右考虑未确定值的位置 \(i\)，设其受到考虑限制为 \(A_i\ge k_i\)，只考虑所有已确定值的位置的贡献（包含所有 \(i\) 前的数和 \(i\) 后被钦定的数），在权值线段树上查找 \(\ge k_i\) 的最优解是正确的。
证明：设用以上方法得到 \(A_i=x\)，权值线段树上找出的贡献（即已确定的数产生的贡献）为 \(V\)，未被考虑的贡献为 \(v\)。若存在更优解 \(A_i=y\)，做以下讨论：
- 若 \(y>x\)。根据我们的做法，\(y\) 在权值线段树上找出的贡献 \(V'\ge V\)。对于剩余位置，\(A_i\) 越大可能的贡献越多，故 \(v'\ge v\)。有 \(V+v\le V'+v'\)，矛盾。
- 若 \(y<x\)。假设这种填法得到了最优序列 \(B\)，对 \(B\) 做如下调整：\(\forall j\ge i\) 且 \(y\le B_j <x\)，将 \(B_j\) 更改为 \(x\)，得到新序列 \(B'\)。考虑逆序对数目的变化量。显然，被修改的位置不互相产生贡献，故一定不劣于原本情况。被修改的位置对于 \(B_j>x\) 的位置的贡献不发生改变。故只需考虑被修改的位置对于原本确定的位置的贡献的变化量。对于被修改的位置 \(t\)，其贡献为
\(\sum_{j=1}^{t-1} [B_j>B_t]+\sum_{j=t+1}^n [B_j<B_t]\) 即 \(\sum_{j=1}^{i-1} [B_j>B_t]+\sum_{j=i}^{t-1} [B_j>B_t]+\sum_{j=i+1}^n [B_j<B_t]-\sum_{j=i+1}^t [B_j<B_t]\) 因为 \(B_t\le B_i\)，可写作 \(\sum_{j=1}^{i-1} [B_j>B_t]+\sum_{j=i+1}^n [B_j<B_t]+\sum_{j=i}^{t} ([B_j>B_t]-[B_j<B_t])\) 根据我们选取 \(x\) 的方式 \(\sum_{j=1}^{i-1} [B_j>B_t]+\sum_{j=i+1}^n [B_j<B_t]>\sum_{j=1}^{i-1} [x>B_t]+\sum_{j=i+1}^n [x<B_t]\)，又因为 \(x>B_t\)，\(\sum_{j=i}^{t} ([B_j>B_t]-[B_j<B_t])\le\sum_{j=i}^{t} ([B_j>x]-[B_j<x])\)。 综上，\(t\) 的总贡献减小。故 \(B'\) 中逆序对数小于 \(B\)，矛盾。