P5482 [JLOI2011] 不等式组

这道题比板子还是难不少，因为有大量的分类讨论。

看到题就可以考虑平衡树了。

\(ax+b>c\iff ax>c-b\)，根据不等式乘除法的变号规则分类。

1. \(a>0\)，不等号方向不变，\(x>\dfrac{c-b}{a}\)。
2. \(a<0\)，不等号方向改变，\(x<\dfrac{c-b}{a}\)。
3. \(a=0\)，\(0>c-b\iff b>c\)，特判。

对于情况3，我们考虑如果开始时就不满足就不管了（因为它没有贡献，删不删除无所谓）；如果满足，那么记录它是第三类，在删除时更新答案（对于可能重复删除的问题，开个数组记录一下；再弄两个数组，一个 all 表示是不是情况3，t 表示是不是情况1、2，比较简单）。

我们处理完了情况3，接下来看1、2。

由于用分数在转换成小数的时候很麻烦（当然你可以直接把分数放到平衡树里，但是板子要进行很大的改动），又考虑到查询时 \(x\) 的取值均为整数，我们就可以考虑将分数等价为整数。

首先如果分数恰好整除，就不管。

比如 \(x>\dfrac{1}{2}\)，发现当 \(x=1\) 时成立，当 \(x=0\) 时不成立，而 \(x>0\) 时条件恰好等价于此，于是发现了当 \(x>?\) 这样的不等式，如果结果为分数，可以对其向下取整。

再举个小于号的例子。

比如 \(x<\dfrac{1}{2}\)，发现当 \(x=1\) 时不成立，当 \(x=0\) 时成立，而 \(x<1\) 时条件恰好等价于此，于是发现了当 \(x<?\) 这样的不等式，如果结果为分数，可以对其向上取整。（当然可以对称理解）

然后由于 C++ 的整除是向零取整，于是我们得自己搞一个。

首先如果是整数，特判；

其次，如果二者同号，结果为正，用一般的除法（此时 C++ 相当于向下取整），向上取整结果 \(+1\)。

如果异号，结果为负，用一般的除法（此时 C++ 相当于向上取整），向下取整结果 \(-1\)。

至此，搞定了条件转换。

然后我们考虑满足条件的要求。

用数轴进行理解。

对于大于条件，我们发现就是查询平衡树中小于 \(x\) 的数的个数，这个就是排名减去一。

对于小于条件，我们发现就是查询平衡树中大于 \(x\) 的数的个数，这个就是 \(tot-(rank_{x+1}-1)\)个数，\(tot\) 表示平衡树中数的个数，\((rank_{x+1}-1)\) 恰好是平衡树中 \(\le x\) 的数的个数。

至此，问题就变成了两棵平衡树，分别在它们中插入、删除，然后每次询问给定的数在两棵平衡树中的排名。

复杂度 \(O(n\log n)\)。