稻草人
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
0 0
2 2
3 4
4 3
Sample Output
3
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);
}