P7290 「EZEC-5」暴力出奇迹

# 滥用本题评测将封号！

给定一个平面，有 $n$ 个竖直线段，第 $i$ 条的端点是 $(i,a_i)$ 和 $(i,b_i)$。 有 $m$ 次查询，每次查询给定 $l,r,x,y$，查询对所有 $(x,i)$ 和 $(y,i)$ 连接成的水平线段，满足 $l\le i\le r$，其最多能与多少竖直线段相交，定义端点为 $(i,a_1)$ 和 $(i,a_2)$ 的竖直线段与端点为 $(b_1,j)$ 和 $(b_2,j)$ 的水平线段相交，当且仅当 $a_1\le j\le a_2$ 且 $b_1\le i\le b_2$，注意当线段两端点重合时，如果有其他线段经过这个重合点，仍然算作相交。

第一行一个数表示 $n$。 之后 $n$ 行，第 $i$ 行两个数 $a_i,b_i$ 表示 第 $i$ 条竖直线段的两个端点，保证 $a_i \le b_i$。 之后一行一个数表示 $m$。 之后 $m$ 行，每行四个数表示一次询问的 $l,r,x,y$。

对于每次询问，输出一行一个数表示答案。

注意：本题采用**捆绑测试**，只有当你通过一个 subtask 中的所有测试点后，你才能拿到这个 subtask 的分数。 对于 $100\%$ 的数据，$1\le n\le 5\times 10^5,1\le m\le 9\times 10^5$，$1\le l,r,x,y,a_i,b_i\le n$。 --- ## 以下为旧数据范围 对于其中 $5\%$ 的数据，为样例 1。 对于另外 $14\%$ 的数据，$m=1$。 对于另外 $5\%$ 的数据，$n,m\leq 500$。 对于另外 $14\%$ 的数据，$n\leq 500$。 对于另外 $19\%$ 的数据，$n,m\leq 2000$。 对于另外 $19\%$ 的数据，$n\leq 20000$。 对于 $100\%$ 的数据，$1\le n\le 5\times 10^4,1\le m\le 5\times 10^5$，$1\le l,r,x,y,a_i,b_i\le n$。