题解：CF1866F Freak Joker Process
yinianxingkong
·
·
题解
CF1866F
前言
本题解本质上是官解翻译+自己的一点理解，您认为官解更好理解当然可以直接看官解，链接。
阅读理解启动。
解法分析
题意：给 n 个二元组 (A_i,B_i)，求：
RankA(i)=1+\sum_{A_i<A_j} 1
RankB(i)=1+\sum_{B_i<B_j} 1
RankOverall(i)=1+\sum_{RankA(j)+RankB(j)<RankA(i)+RankB(i)} 1
支持对 A,B 单点加减 1，单点查 RankOverall。
使用操作分块。排名显然就是维护大于某数的个数，我们对值域维护 biggerA,biggerB 表示大于某数的个数。
转移到值域上以后发现，把一个数加减一只会影响一个值，换到下标就是相同值的所有位置。根据操作分块的套路，先将值域和下标在块内会被修改的值标记。
通过值域和下标的标记关系，可以将块内的点分成 4 种类型：
- 蓝点，下标值域都有标记。
- 橙点，A,B 值域皆有标记。
- 黄点，仅一个权的值域有标记。
- 白点，无标记。
显然值域标记、非白点不超过块长个。
需要预处理一部分信息：
$cnt_{i,j}$：将值域标记模成数组，$A,B$ 权分别为第 $i,j$ 个标记的橙点个数。
对黄点的处理相对容易，先预处理出没变的权并根据它排序即可。橙点最多更新块长个，用 $cnt$ 更新即可。
对于查询，判断：
- 蓝点，直接加。
- 橙白，$smallerOverall$ 预处理了。
- 黄色，二分答案判断即可。
复杂度 $O(n\sqrt{n\log n})$，精细实现优化二分可以 $O(n\sqrt n)$。
That's all.