【问题描述】

JOI村有一片荒地，上面竖着N个稻草人，村民们每年多次在稻草人们的周围举行祭典。

有一次，JOI村的村长听到了稻草人们的启示，计划在荒地中开垦一片田地。和启示中的一样，田地需要满足以下条件：

田地的形状是边平行于坐标轴的长方形；

左下角和右上角各有一个稻草人；

田地的内部(不包括边界)没有稻草人。

给出每个稻草人的坐标，请你求出有多少遵从启示的田地的个数

【输入格式】

第一行一个正整数N，代表稻草人的个数

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

【输出格式】

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

【输入样例】

4

0 0

2 2

3 4

4 3

【输出样例】

3

【数据范围】

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)互不相同。

 

正解：cdq分治+二分栈

 

解题报告：思想很简单，直接上代码

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #define File(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)#define RG register#define ll long longconst int N = 200500;using namespace std;int gi(){ char ch=getchar();int x=0; while(ch<'0' || ch>'9')ch=getchar(); while (ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();} return x;}int n;ll ans;struct date{ int x,y;}f[N],a1[N],a2[N],q1[N],q2[N];int cmp(date a,date b){ return a.x
              
               >1; if (q2[mid].y
               
                =r) return; int mid=(l+r)>>1,b1=0,b2=0,top1=0,top2=0;RG int i,j,t=0; q1[0]=(date){n+1,n+1}; cdq(l,mid),cdq(mid+1,r); for (i=l,j=mid+1; i<=mid; i++){ a1[++b1]=f[i]; while(j<=r && f[j].y>f[i].y){ a2[++b2]=f[j]; while(top2 && f[j].x
                
                 q1[top1].x) top1--; q1[++top1]=f[i]; ans+=top2-find(q1[top1-1].y,top2); } while(j<=r) a2[++b2]=f[j++]; i=1,j=1,t=l; while(i<=b1 && j<=b2) if (a1[i].y>a2[j].y) f[t++]=a1[i++]; else f[t++]=a2[j++]; while(i<=b1) f[t++]=a1[i++]; while(j<=b2) f[t++]=a2[j++]; return;}int main(){ File("4237"); RG int i;n=gi(); for (i=1; i<=n; i++) f[i]=(date){gi()+1,gi()+1}; sort(f+1,f+n+1,cop); for (i=1; i<=n; i++) f[i].y=i; sort(f+1,f+n+1,cmp); for (i=1; i<=n; i++) f[i].x=i; cdq(1,n); printf("%lld",ans); return 0;}