CF853C Boredom
题目描述
### 题意
给定一个$\ n*n(1\leq n\leq 200,000)\ $的矩阵$A$，矩阵所在的直角坐标系以向上、向右为正方向。
从 $A$ 的第 $i$ 行中选出第$s_i$个格子标记为黑色,保证被选中的 $n$ 个格子不在同一列
再给定该矩阵的一个子矩阵 $B$
$B$ 的**左、右**边界横坐标分别为$l,r$,**下、上**边界纵坐标分别为$d,u(1\leq l\leq r\leq n,1\leq d\leq u\leq n)$.
请你回答:有几个好的矩阵与 $B$ 相交？
会有 $T(1\leq T\leq 200,000)$ 组离线询问.
我们称一个矩阵为好的矩阵，当且仅当该矩阵至少存在一条对角线使其两个端点上的格子为黑色格子。
输入格式
无
输出格式
无
说明/提示
The first sample test has one beautiful rectangle that occupies the whole grid, therefore the answer to any query is 1.
In the second sample test the first query rectangle intersects 3 beautiful rectangles, as shown on the picture below:
There are 5 beautiful rectangles that intersect the second query rectangle, as shown on the following picture:
