俄罗斯套娃（JOISC 2016 Day 1）

你开了一家卖俄罗斯套娃的店。因此，你向厂家订购了 \(N\)个俄罗斯套娃，这些娃娃被编号为 \(1\) 到 \(N\)，其中第 \(i\) 个套娃是一个的直径为 \(R_i\) 高度为 \(H_i\) 的直♂柱体 。每个俄罗斯套娃都只能套高和直径严格比他小的套娃。同时只要满足条件，俄罗斯套娃可以嵌套多次。

有一天，你收到了厂家的来电，告诉你你预定的 \(N\) 个娃娃不能一次性全部做完。所以第一批只会送达直径大于等于 \(A\) 并且高度小于等于 \(B\) 的所有套娃。你需要预先安排出一个方案，使送来的套娃经过若干次嵌套后，没有被套的套娃数量最小。

由于厂家经常搞大新闻，所以他会改变 \(A\) 和 \(B\) 的值，总共 \(Q\) 次，因此你需要对每对 \((A,B)\) 都作出回答，询问之间互不干扰。

第一行有两个整数 \(N\)和 \(Q\) ，表示套娃的个数和 \((A,B)\) 的对数； 之后的 \(N\) 行，每行两个数 \(R_i\) 与 \(H_i\) 表示第$ i$ 个数的直径和高度； 之后的 \(Q\) 行，每行两个数 \(A_i\) 与 \(B_i\) 表示第 \(i\) 个询问， \(A_i\) 与 \(B_i\) 的意思如上所示。

一个整数，表示符合条件的方案个数。

这题每个套娃都是二维的，于是可以用\(xy​\)坐标轴表示所有的套娃，任意一个点只要在另一个点的右上方就可以把那点（娃娃）装进去

（横坐标为R,纵坐标为H）

这题根据人类的智慧可以得到

（直接）甩结论：最少的没被套的娃娃个数=最长的\(R\)递增，\(H\)递减的序列长度

这个可以感性理解一下，所有不在该序列上的点都必定会在一个点的右上方，所以就相当于所有多出来的点都是可以被装进另一个点中的。

知道这个后就去考虑每个询问，对于每个询问，若逐个计算每次的答案，用一个树状数组其中一维，显然要将一维进行离散。那么剩下的一位直接考虑进行离线处理，那么复杂度就被用优化成\(O((n+q)log_(n+q))\),可以开两个数组分别表示娃娃和询问，不过放一个数组里面一起排序会简单一些，不过注意在遇到询问和娃娃的两个值完全相同时，一定要先更新娃娃在回答询问（当时就被这个卡了。。。）