#BZOJ4718. 梯形阵

梯形阵

题目描述

小Q最近喜欢上了一款游戏,名为《舰队connection》,在游戏中,小Q指挥强大的舰队南征北战,从而成为了一名
dalao。在战斗中,布阵往往是决定胜败的关键,其中梯形阵捉摸不定的攻守能力深受小Q喜爱。
【题意描述】
小Q的舰队有n艘船在海上航行,每艘船都拥有自己的坐标(xi,yi)。我们规定x表示行,y表示列,x从上到下增加,
y从左到右增加,左上角为(1,1),右下角为(Xmax, Ymax)。梯形阵由舰队中的至少4艘船构成,阵中的所有船只都
在一条直线上,且刚好与坐标轴夹角为45度。阵型中所有船只组成的线段上不能有其他的船只,但延长线上可以有
其他船只。例如,在以下阵列中(.表示海,*表示船)
.*.**.
*.***.
.*.*..
**..*.
*..*.*
....*.
存在6种梯形阵,其中3种如下(被X标注的为阵中的船只):
.*.**..*.X*..*.*X.
X.***.*.X**.*.*X*.
.X.*...X.*...*.*..
**..*.X*..*.*X..*.
*..X.**..*.*X..*.*
....X.....*.....*.
另外的3种均在同一条直线上,但它们被视为不同的梯形阵,如下:
.X.**..*.**..X.**.
*.X**.*.X**.*.X**.
.*.X...*.X...*.X..
**..X.**..X.**..X.
*..*.**..*.X*..*.X
....*.....*.....*.
需要注意的是,以下三种不被认为是梯形阵,因为它们所在线段上包含了其他船只。
(X表示选出的船只,#表示不合法的其他船只)
.X.**..X.**..X.**.
*.#**.*.X**.*.X**.
.*.X...*.#...*.X..
**..X.**..X.**..#.
*..*.X*..*.X*..*.X
....*.....*.....*.
小Q会不断给出两种询问(type, L, R, k)
询问1:在L<=xi<=R的所有船中,至少由1/k的船组成的梯形阵有多少种
询问2:在L<=yi<=R的所有船中,至少由1/k的船组成的梯形阵有多少种
例如,在上图的舰队中:
.*.**.
*.***.
.*.*..
**..*.
*..*.*
....*.
对于询问(1,1,5,3)来说,1~5行共计15艘船,至少由其中1/3的船即5艘船组成的梯形阵只有1种。
对于询问(1,1,5,4)来说,至少由1/4的船,即15/4艘船组成的梯形阵,由于船必须是整数艘
也即至少4艘船组成,有5种。
对于询问(2,2,5,6)来说,2~5列共计12艘船,至少由1/6的船组成,即至少由2艘船组成
但是梯形阵至少要由4艘船组成,所以只有1种。

输入格式

第一行三个数,n, Xmax, Ymax,空格分隔,表示船数和最大坐标。
接下来n行,每行两个数Xi, Yi,空格分隔,表示每艘船的位置。
接下来1行,一个数q,表示任务2的询问个数。
接下来q行,每行4个数type, L, R, k,空格分隔,描述一个询问。
n<=200000,1<=Xmax<=500000,1<=Ymax<=500000,1<=q<=100000,1<=k<=n
所有询问k之和不超过200000

输出格式

共计q行,每行一个数,表示每个询问的答案。

16 6 6 1 2 1 4 1 5 2 1 2 3 2 4 2 5 3 2 3 4 4 1 4 2 4 5 5 1 5 4 5 6 6 5 3 1 1 5 3 1 1 5 4 2 2 5 6
1 5 1