【BZOJ4237】稻草人 [分治][单调栈]

稻草人

Time Limit: 40 Sec Memory Limit: 256 MB
[Submit][Status][Discuss]

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

HINT

　　1<=N<=2*10^5

　　0<=Xi<=10^9(1<=i<=N), Xi(1<=i<=N)互不相同。

　　0<=Yi<=10^9(1<=i<=N), Yi(1<=i<=N)互不相同。

Solution

　　O(n^2)做法很显然，既然这样，我们就使用惯用套路，我们先对 y 进行分治，将上面的点视为右上角的点，下面的视为左下角的点，统计答案。
　　首先把两部分的点分别按照 x 升序排序。
　　然后枚举上面的每个点。
　　显然，约束到它拓展的是 在它左下方最接近的点。
　　同时，下面的点最近的右上方点约束到点的拓展。

　　那我们对于上面维护一个 y 递增的单调栈，对下面维护一个 y 递减的单调栈。
　　枚举到上面的点的时候，把 x 小于它的下面的点加入下面的那个单调栈，然后二分一下可行的位置就可以了。
　　（显然，只有当下面的x > 上面单调栈倒数第二个点的 x 的时候才可以被加入答案）

　　（middle写成了mid调了一个小时！好气呀(╯‵□′)╯︵┻━┻）

Code

 #include<iostream>

 #include<string>

 #include<algorithm>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<queue>

 using namespace std;

 typedef long long s64;

 const int ONE = ;

 int get()

 {

         int res = , Q = ; char c;

         while( (c = getchar()) <  || c > )

             if(c == '-') Q = -;

         if(Q) res = c - ;

         while( (c = getchar()) >=  && c <= )

             res = res *  + c - ;

         return res * Q;

 }

 int n;

 struct point

 {

         int x, y;

 }a[ONE];

 bool cmpx(const point &a, const point &b) {return a.x < b.x;}

 bool cmpy(const point &a, const point &b) {return a.y < b.y;}

 int Stk_down[ONE], Stk_up[ONE];

 s64 Ans;

 void Solve(int l, int r)

 {

         if(l >= r) return;

         int mid = l + r >> ;

         sort(a + l, a + r + , cmpy);

         sort(a + l, a + mid + , cmpx);

         sort(a + mid + , a + r + , cmpx);

         int top_up = , top_down = ;

         int now = l;

         for(int i = mid + ; i <= r; i++)

         {

             while(top_up >  && a[Stk_up[top_up]].y >= a[i].y) top_up--;

             Stk_up[++top_up] = i;

             while(now <= mid && a[now].x <= a[i].x)

             {

                 while(top_down >  && a[Stk_down[top_down]].y <= a[now].y) top_down--;

                 Stk_down[++top_down] = now;

                 now++;

             }

             int left = , right = top_down, pos = ;

             int lx = top_up -  >  ? a[Stk_up[top_up - ]].x : -;

             while(left < right - )

             {

                 int middle = left + right >> ;

                 if(a[Stk_down[middle]].x >= lx)

                     right = middle;

                 else

                     left = middle;

             }

             if(a[Stk_down[left]].x >= lx) pos = left;

             else

             if(a[Stk_down[right]].x >= lx) pos = right;

             if(pos) Ans += top_down - pos + ;

         }

         Solve(l, mid), Solve(mid + , r);

 }

 int main()

 {

         n = get();

         for(int i = ; i <= n; i++)

             a[i].x = get(), a[i].y = get();

         Solve(, n);

         printf("%lld", Ans);

 }

秒客网