线段树记录系数维护动态信息：ZR2612

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132255084

http://zhengruioi.com/problem/2612

$a_i+b_j\ge 0$ => $a_i\ge -b_j$

因此考虑把 $b$ 去负， $a_i\ge b_j$

也就是一个区间 $a$ 最小值大于 $b$ 最大值

套路1 （大小关系转不同）

对于此类只需判断不同东西的大小关系（即没有反向 $b_j\ge a_i$ 的关系），可以通过排序和离散化是的 $a,b$ 互不相同

套路2 （大小贡献转值域分治）

化为互不相同后，相当于求一类大于另一类的总数，支持修改

显然可以把区间数对应到值域上，然后进行分治。每次只需算左区间对右区间的贡献即可（也可以理解成线段树）

$f_i$ 表示 $a_x=i$ 的区间数， $g_i$ 表示 $b_x=i$ 的区间数，分治时就相当于是 $\sum_{l<r}g_l\times f_r$

套路3（线段树记录系数维护动态信息）

可以发现 $f$ 和 $g$ 是动态变化的（左端点定，右端点动），但 $f$ 必然可以表示成 $kn+b$ ， $g$ 同理为 $km+b$
b
而统计答案的最高次数最多为 $nm$ ，同时相邻间满足可加性

只需要维护4个信息 $a,b,c,d$ 表示常数项， $n$ ， $m$ ， $nm$ 的系数，转移时维护加和乘的情况

乘法过程：

实现可以用欧冠重载运算符：