#P4803. [CCO2015] 太阳能飞行

[CCO2015] 太阳能飞行

题目背景

警告:滥用本题评测将被封号

题目描述

本题译自 CCO 2015 Day1 T3「Solar Flight

航空的新纪元正在来临——第一个太阳能驱动的巨型喷气式飞机即将商用!然而,公众对前沿技术有一些在安全方面的焦虑,因为驱动飞机的阳光的光线可能会被其他在空中的物体挡住。因此,必须先进行一些统计和计算来规划第一次航行。

我们考虑一个包含 NN 个从一个城市到另外一个城市的航路组成的图。一架飞机可以被考虑成一个点。它穿过的天空可以被模型化为一个笛卡尔坐标系,其中 XX 轴表示从任意一个点向东出发的距离,YY 轴表示高度。我们只考虑 xx 值的范围在 [0,X][0,X],所有航路均为直线的部分。第 ii 架飞机从 (0,Ai)(0,A_i) 飞到 (X,Bi)(X,B_i)。所有AA值互不相同,对于BB也如此。飞机以未知的,可能是非恒定的速度沿着航路行驶,所以任意时间点,飞机可能在航路的任意位置上。然而,已知的是飞机从不与其他飞机相撞,所以如果两个航道交错,两个飞机不会同时到达交点。

每个飞机 ii 同时也有一个干扰因素值 CiC_i,表示一个飞机影响它下面飞机太阳吸收能力的强弱。

各个飞机上的太阳能板非常奇怪,那些太阳能板只能收集飞机正上方的能量。这就意味着一个飞机能吸收的阳光可能会被其他与其的 xx 值相同,但是 yy 值比他大的飞机挡住。具体来说,太阳能板吸收的太阳光减少的值为挡住它的飞机的干扰因素值之和。

根据这些信息,以及一个距离常数 KK,你要回答 QQ 个关于可能对太阳能板影响的询问。第 ii 个询问询问你在一个时刻飞机 PiP_i 的太阳能板吸收的太阳光减少的值。在任意时刻飞机的 xx 值均在 [Si,Si+K][S_i,S_i+K]之间。

输入格式

第一行四个整数 X,K,N,QX,K,N,Q,分别表示最大考虑的 xx 值,距离常数,航路总数,询问总数。

接下来 NN 行每行三个整数 Ai,Bi,Ci(1iN)A_i,B_i,C_i(1\le i \le N),表示飞机 ii 初始 yy 值,终止 yy值,干扰因素值。

接下来 QQ 行每行两个整数,Pi,Si(1iQ)P_i, S_i(1\le i \le Q),表示根据 PiP_iSiS_i 回答题目中的问题。

输出格式

输出 QQ 行,每行一个整数表示对于询问 i(1iQ)i(1\le i \le Q) 的回答。

12 4 3 3
1 4 5
2 2 3
6 3 6
2 1
1 8
3 0
11
6
0

提示

飞机的航路示意图如下图所示。

CCO2015D1T3Pic1

询问 11 是对于 22 号飞机在 [1,5][1,5] 范围内所提出的询问,当飞机在 x4x\le 4 时可能会被飞机 33 挡住,但是绝不是飞机 11。然而,但是当它的 x>4x>4 时可能会被其他所有飞机挡住,因此,该询问的答案即其他所有飞机的影响因素值之和,为 5+6=115+6=11

对于询问 22,当 x<10x<10 时飞机 11 可能会被飞机 33 挡住,并且当 x10x\geq10 时不会被任何飞机盖住,因此只可能被飞机 33 影响,即结果等于飞机 33 的影响因素值 66

对于询问 33,飞机 1,21,2 都不能在飞机 33 的正上方除非 xx 达到 1010。所以该询问的答案为0。

对于 40%40\% 的数据,Q1000Q\le 1000

对于 100%100\% 的数据,1N2000,1\le N\le 2000, 1KX,1\le K\le X, 1X,Ai,Bi,Ci109,1\le X,A_i,B_i,C_i\le 10^9, 0SiXK,0\le S_i\le X-K, 1Q8000001\le Q \le 800000