#P13094. [FJCPC 2025] 帕累托前沿

[FJCPC 2025] 帕累托前沿

题目描述

给出 nn 个二元组 (xi,yi)(x_i,y_i),你需要回答 qq 个询问,每个询问给出闭区间 [l,r][l,r],请回答满足以下条件的整数 jj 数量:

  • ljrl\leq j\leq r

  • 不存在 lkr,kjl\leq k\leq r, k\neq j,使得 xkxjx_k\geq x_jykyjy_k\geq y_j

输入格式

第一行两个正整数 n,qn,q1n,q1061\leq n,q\leq 10^6),分别表示二元组数量和询问数量。

第二行 nn 个非负整数 x1,x2,,xnx_1,x_2,\dots,x_n0xi1060\le x_i\le 10^6)。

第三行 nn 个非负整数 y1,y2,,yny_1,y_2,\dots,y_n0yi1060\le y_i\le 10^6)。

接下来 qq 行,每行两个正整数 l,rl,r1lrn1\leq l\leq r\leq n),表示询问的区间。

输出格式

对于每个询问,输出一行一个整数表示答案。

8 7
1 9 7 8 0 7 2 3
19 20 5 6 1 14 9 5
1 8
3 7
2 6
4 4
5 7
3 8
6 7
1
2
1
1
1
2
1

提示

对于询问 11,满足条件的整数为 22

对于询问 22,满足条件的整数为 4466

对于询问 33,满足条件的整数为 22

对于询问 44,满足条件的整数为 44

对于询问 55,满足条件的整数为 66

对于询问 66,满足条件的整数为 4466

对于询问 77,满足条件的整数为 66