【BZOJ4237】稻草人
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)
0<=Yi<=10^9(1<=i<=N)
Xi(1<=i<=N)互不相同。
Yi(1<=i<=N)互不相同。
题解：这种题能否想到cdq分治是重点。
既然用cdq分治就一定要排序，那么怎么排呢？我们发现：第一维按x从小到大排序，第二位按y从大到小排序，可以便于我们进一步的处理。（反正就4种排序方法，自己挨个试一试就知道了~）
所以我们将所有点按x分治，左右两边分别按y从大到小排序，我们想找的就是左下角在[l,mid]，右上角在[mid+1,r]中的矩形。发现，如果[l,mid]中的一个点i可以跟[mid+1,r]中的一些j1,j2...jk组成矩形，那么假设y[j1]>y[j2]>...>y[jk]，一定满足x[j1]<x[j2]<..<x[jk]。反过来，每个j对应的i1,i2...ik也是有规律的。所以我们想到给左右两边都维护一个单调栈，那么思考该维护两个怎样的单调栈。
经过尝试发现（也就4种，一个一个试~），令左边的单调栈中的x单调递减，右边的x单调递增，可以便于我们进一步处理。我们对于[l,mid]中的i，设k是[l,mid]中满足x[k]>x[i]，y[k]>y[i]且y值最小的点。那么i只能与[mid+1,r]中y值在[y[i],y[k]]中的点组成矩形。并且，如果这些点的y值递减，这些点的x值是递增的（也就是说都在单调栈里）。那么我们直接在右边的单调栈中二分统计一下y值符合条件的个数就行了。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=200010;
typedef long long ll;
ll ans;
int n,t1,t2;
int x[maxn],y[maxn],p[maxn],s1[maxn],s2[maxn];
int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
bool cmpx(int a,int b)
{
return (x[a]==x[b])?(y[a]>y[b]):(x[a]<x[b]);
}
bool cmpy(int a,int b)
{
return (y[a]==y[b])?(x[a]<x[b]):(y[a]>y[b]);
}
void solve(int l,int r)
{
if(l==r) return ;
int i,j,mid=l+r>>1,last,L,R,MID;
sort(p+l,p+mid+1,cmpy),sort(p+mid+1,p+r+1,cmpy);
for(i=l,j=mid+1,t1=t2=0;i<=mid;i++)
{
for(;y[p[j]]>=y[p[i]]&&j<=r;j++)
{
while(t2&&x[s2[t2]]>x[p[j]]) t2--;
s2[++t2]=p[j];
}
while(t1&&x[s1[t1]]<x[p[i]]) t1--;
last=y[s1[t1]],s1[++t1]=p[i];
L=1,R=t2+1;
while(L<R)
{
MID=L+R>>1;
if(y[s2[MID]]<=last) R=MID;
else L=MID+1;
}
ans+=t2-R+1;
}
sort(p+l,p+r+1,cmpx);
solve(l,mid),solve(mid+1,r);
}
int main()
{
x[0]=0,y[0]=1<<30;
n=rd();
int i;
for(i=1;i<=n;i++) x[i]=rd(),y[i]=rd(),p[i]=i;
sort(p+1,p+n+1,cmpx);
solve(1,n);
printf("%lld",ans);
return 0;
}