#P17833. [Ontak2022]REC

    ID: 16776 传统题 500~5000ms 512MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>计算几何扫描线数据结构树状数组CF2400差分算法基础模拟

[Ontak2022]REC

题目描述

平面像素网格上最初画有 nn 个轴平行矩形。矩形由左下角像素 (x1,y1)(x_1,y_1) 和右上角像素 (x2,y2)(x_2,y_2) 描述,端点像素包含在内。

接下来执行 mm 条移动命令,每条命令把某个原始矩形沿八个方向之一移动整数距离 dd。移动不是一次完成,而是逐单位移动;每移动一个单位,都会在新位置留下一个永久的矩形图像。原图像也保留。因此一次距离为 dd 的移动产生恰好 dd 个新矩形图像。

后续命令继续移动该原始矩形的当前位置,已经留下的残影不再移动。所有命令执行后,对 qq 个像素位置分别求它被多少个矩形图像覆盖,重合的图像分别计数。

输入格式

第一行三个整数 n,m,qn,m,q。

接下来 nn 行,每行四个整数 x1,y1,x2,y2x_1,y_1,x_2,y_2,描述一个初始矩形。

接下来 mm 行,每行三个整数 vi,xi,div_i,x_i,d_i,表示把编号为 xix_i 的原始矩形沿方向 viv_i 移动 did_i。方向编号如下:

编号 每一步的坐标变化
0 (+1,0)(+1,0)
1 (+1,+1)(+1,+1)
2 (0,+1)(0,+1)
3 (−1,+1)(-1,+1)
4 (−1,0)(-1,0)
5 (−1,−1)(-1,-1)
6 (0,−1)(0,-1)
7 (+1,−1)(+1,-1)

最后 qq 行,每行两个整数,表示一个询问像素。

输出格式

每个询问输出一行覆盖次数。

数据范围

1≤n,q≤2500001\le n,q\le250000,0≤m≤2500000\le m\le250000;矩形满足 1≤x1≤x2≤2500001\le x_1\le x_2\le250000、1≤y1≤y2≤2500001\le y_1\le y_2\le250000;0≤vi≤70\le v_i\le7,1≤xi≤n1\le x_i\le n,1≤di≤2500001\le d_i\le250000;询问坐标在 [1,250000][1,250000] 内。

保证移动过程中所有矩形始终处于上述坐标范围内。答案需要使用64位整数。

子任务

子任务 附加限制 分值
1 n≤100,m=0 8
2 m=0
3 m≤100 11
4 所有方向编号为偶数 13
5 每个矩形退化为单个像素 12
6 无额外限制 48

样例 1

输入:

1 8 3
2 1 2 1
0 1 1
1 1 1
2 1 1
3 1 1
4 1 1
5 1 1
6 1 1
7 1 1
1 1
2 1
4 2

输出:

0
2
1

样例 2

输入:

2 0 3
3 3 7 7
4 4 6 6
5 5
3 7
8 8

输出:

2
1
0