P5268 [SNOI2017] 一个简单的询问 题解

不妨把每个区间表示成 \(|V|\) 维向量 \(b\) 的形式，其中 \(b[i]\) 为在区间 \([l,r]\) 中，\(i\) 出现的次数。
然后我们发现要求的实际上是 \(a \cdot b\)。
拆一下（这里用 \(g(i)\) 表示 \([1,i]\) 的向量）：
\(a \cdot b = [l_1,r_1] \cdot [l_2,r_2] = (g(r_1) - g(l_1)) \cdot (g(r_2) - g(l_2))\)
乘法分配律一下：
\(a \cdot b = g(r_1) \cdot g(r_2) - g(l_1) \cdot g(r_2) - g(r_1) \cdot g(l_2) + g(l_1) \cdot g(l_2)\)
容易发现拆成了四项，而且每项都能莫队。
代码待补