8718: 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

提示

没有写明提示

题目来源

没有写明来源