#P18556. Traveling in Cells 2

Traveling in Cells 2

Traveling in Cells 2

小青鱼有一位名叫绾绾的朋友。绾绾在一张很大的网格上:左下角格子的坐标为 (0,0)(0,0),右上角格子的坐标为 (106,106)(10^6,10^6)。格子的坐标均为整数。

最初有 nn 个障碍,第 ii 个障碍在 (xi(O),yi(O))(x_i^{(O)},y_i^{(O)})。所有初始障碍都不在网格边界上,即 0<xi(O),yi(O)<1060<x_i^{(O)},y_i^{(O)}<10^6。

绾绾每次只能向上移动一格,或者向右移动一格;任何时候都不能位于有障碍的格子。

形式化地,从 (xs,ys)(x_s,y_s) 到 (xt,yt)(x_t,y_t) 的合法路径为一个格子序列

P:(a1,b1),(a2,b2),…,(aℓ,bℓ),P:(a_1,b_1),(a_2,b_2),\ldots,(a_\ell,b_\ell),

满足:

  • (a1,b1)=(xs,ys)(a_1,b_1)=(x_s,y_s),(aℓ,bℓ)=(xt,yt)(a_\ell,b_\ell)=(x_t,y_t)。
  • 对每个 1≤i<ℓ1\le i<\ell,恰有以下一种情况成立:ai+1=ai, bi+1=bi+1a_{i+1}=a_i,\ b_{i+1}=b_i+1;或者 ai+1=ai+1, bi+1=bia_{i+1}=a_i+1,\ b_{i+1}=b_i。
  • 对每个 1≤i≤ℓ1\le i\le\ell,(ai,bi)(a_i,b_i) 都没有障碍。

图1:一条合法路径,红点为障碍

绾绾不能经过有障碍的格子。此外,一些原本没有障碍的格子也不会出现在任何一条合法路径上。任何无法出现在从 (0,0)(0,0) 到 (106,106)(10^6,10^6) 的任意合法路径中的格子,都会变成新的障碍。 重复这一过程,直到每个自由格子(即没有障碍的格子)都能出现在至少一条这样的合法路径中。

下图中,红点是最初的障碍,橙点是在这一过程中新增的障碍。

图2:补完所有额外障碍后的网格

补完所有额外障碍后,小青鱼要回答 qq 次行走询问。第 ii 次询问考虑从 (xi(s),yi(s))(x_i^{(s)},y_i^{(s)}) 到 (xi(t),yi(t))(x_i^{(t)},y_i^{(t)}) 的所有合法路径,求被其中至少一条路径经过的不同格子数。

形式化地,一个格子 (x,y)(x,y) 被计数,当且仅当存在一条合法路径 P:(a1,b1),…,(aℓ,bℓ)P:(a_1,b_1),\ldots,(a_\ell,b_\ell),其起点为 (xi(s),yi(s))(x_i^{(s)},y_i^{(s)}),终点为 (xi(t),yi(t))(x_i^{(t)},y_i^{(t)}),并且某个 1≤j≤ℓ1\le j\le\ell 满足 (aj,bj)=(x,y)(a_j,b_j)=(x,y)。计数包含合法的起点和终点;若不存在路径,答案为 00。所有询问都在同一张补完障碍的网格上进行,询问不会修改网格。

输入格式

第一行两个整数 n,qn,q(1≤n,q≤1051\le n,q\le10^5)。

接下来 nn 行描述初始障碍。第 ii 行两个整数 xi(O),yi(O)x_i^{(O)},y_i^{(O)}(1≤xi(O),yi(O)<1061\le x_i^{(O)},y_i^{(O)}<10^6),表示第 ii 个障碍的坐标。

接下来 qq 行描述询问。第 ii 行四个整数 xi(s),yi(s),xi(t),yi(t)x_i^{(s)},y_i^{(s)},x_i^{(t)},y_i^{(t)},满足

$$1\le x_i^{(s)}\le x_i^{(t)}<10^6,\qquad 1\le y_i^{(s)}\le y_i^{(t)}<10^6.$$

本题输入只有一组数据。原题没有给出初始障碍坐标互异的保证;重复坐标表示同一个被阻挡的格子。

输出格式

对每次询问,按输入顺序输出一行一个整数,表示答案。答案可能超过 32 位有符号整数范围。

原样例 1

3 3
2 3
3 2
4 4
1 1 5 5
3 4 5 5
3 3 4 5
20
4
0

原样例 2

8 2
2 2
2 5
3 5
4 1
5 4
6 1
7 3
8 2
1 1 9 5
5 1 8 5
28
11

样例说明

第一个样例最初有三个障碍(红点),补障碍过程又增加两个障碍(橙点)。下图从左到右对应其三个询问;蓝点表示被至少一条询问路径经过的格子。

图3:第一个样例的全部三个询问

第三次询问中,起点 (3,3)(3,3) 已被补为障碍,因此没有合法路径,答案为 00。