~{→看不见LaTex格式的Dalao们请刷新本页Thanks♪(･ω･)ﾉ←}~
2019寒假集训题
#.Ball
题面
$N$ ladies attend the ball in the King’s palace. Every lady can be
described with three values: beauty, intellect and richness. King’s Master of Ceremonies knows that ladies are very special creatures. If some lady understands that there is other lady at the ball which is more beautiful, smarter and more rich, she can jump out of the window. He knows values of all ladies and wants to find out how many probable self-murderers will be on the ball. Lets denote beauty of the $i$-th lady by $B_i$ , her intellect by $I_i$ and her richness by $R_i$ . Then $i$-th lady is a probable self-murderer if there is some $j$-th lady that $B_i<B_j,I_i<I_j,R_i<R_j$ . Find the number of probable self-murderers.
简要翻译
有N个女士去参加舞会。每个女士有三个值a[i],b[i],c[i]。如果一位女士发现有其它女士的这三个值都比自己高的话就会去跳楼.求有多少跳楼的女士。
Input
第一行包含一个整数$N$。
第二行包含$N$个整数$B_i$。
第三行包含$N$个整数$I_i$。
第四行包含$N$个整数$R_i$。
Output
输出一个整数表示答案。
Sample Input
3
1 4 2
4 3 2
2 5 3
Sample Output
1
Hint
$1\leq N\leq 500,000,0\leq B_i,I_i,R_i\leq 10^9$。
这题相当于给了你$n$个三元组，我们先将一维离散化乘线段树的下标，然后对剩下两维中的一维降序排序，最后用线段树来处理剩下一维。就非常ok了！
Code
1 |