Description

JOI村有一片荒地,上面竖着N个稻草人,村民们每年多次在稻草人们的周围举行祭典。
有一次,JOI村的村长听到了稻草人们的启示,计划在荒地中开垦一片田地。和启示中的一样,田地需要满足以下条件:
田地的形状是边平行于坐标轴的长方形;
左下角和右上角各有一个稻草人;
田地的内部(不包括边界)没有稻草人。
给出每个稻草人的坐标,请你求出有多少遵从启示的田地的个数

Input

第一行一个正整数N,代表稻草人的个数
接下来N行,第i行(1<=i<=N)包含2个由空格分隔的整数Xi和Yi,表示第i个稻草人的坐标

Output

输出一行一个正整数,代表遵从启示的田地的个数

Sample Input

4
0 0
2 2
3 4
4 3

Sample Output

3

HINT

所有满足要求的田地由下图所示:
 
1<=N<=2*10^5
0<=Xi<=10^9(1<=i<=N)
0<=Yi<=10^9(1<=i<=N)
Xi(1<=i<=N)互不相同。
Yi(1<=i<=N)互不相同。

Source

JOI 2013~2014 春季training合宿 竞技3 By PoPoQQQ

cdq分治

考虑没有中间那个不能有稻草人的限制直接cdq求偏序即可

考虑有了这样的限制之后我们仍然将y从小到大排序然后每次做的时候先c递归处理左右两边 然后考虑合并两边的答案

先将两边各自按照x排序 然后针对左边按照y维护递降单调队列

右边维护y递升单调队列 然后每次相当于是做右边的时候取单调队列里前一个的x然后去左边单调队列二分找到第一个大的即可 那么左边单调队列那个位置到队尾都是可以算答案的 具体画图感受

 


elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论