「JOISC 2014 Day3」稻草人

题意

给你平面上 $N$ 个点，任意两个点的横坐标都不相同，任意两个点的纵坐标都不相同。问你有多少对点满足，以这两点分别为左下角和右上角的矩形内部无其它点。如下图四个点中有三对点满足条件：

$1\le N \le 2\times 10^5 ,0\le X_i,Y_i\le 10^9,X_i\text{互不相同},Y_i\text{互不相同}$

题解

考虑CDQ分治，每个点先按 $X_i$ 排序，（还有把 $Y_i$ 离散化一下），开始CDQ分治，考虑如何计算 $[l,mid]$ 对 $[mid+1,r]$ 的贡献。题目保证不会有相同的横坐标，纵坐标，直接单关键字排序就行了。

两点对可行（假设 $i$ 点左下， $j$ 点右上），要保证 $X_i\lt X_j,Y_i\lt Y_j$ 且不存在点 $k$ ， $X_i\lt X_k \lt X_j ,Y_i\lt Y_k\lt Y_j$ 。

之前的按 $X$ 排序保证 $[l,mid]$ 的点横坐标都比 $[mid+1,r]$ 小，按照 CDQ分治的套路，再将 $Y$ 从小到大排序。从迪到高枚举右边的点 $i\in[mid+1,r]$ ，高度小于 $i$ 的左边的点 $j\in[l,mid]$ 都可以用来更新答案，双指针即可。

考虑到并不是 $X_i\lt X_j,Y_i\lt Y_j$ 就可以了，还要保证没有 “中间点” $k$ 在 $i,j$ 构成的矩形中。

如上图，现在处理 $[1,5],[6,10]$ 对答案的贡献，对于左边的点，枚举到 $j(6,3)$ ，它就会把 $(2,1),(3,0)$ 挡住，故之后就不用管它们的贡献了。具体的：

因为此时右边的点 $i$ ，新枚举了左边的点 $j$ 一定满足 $X_j\lt X_i,Y_j\lt Y_i$ ,对于左边的点 $k(X_k,Y_k)$ 若 $X_k\lt X_j,Y_k\lt Y_j$ ，则这个 $j$ 成了 “中间点” ， $k$ 在之后永远会被挡住，考虑 $Y_k\lt Y_j$ ， $k$ 一定在 $j$ 之前枚举到，故对左边的点维护一个 $X$ 坐标单调递减的单调栈即可。

再考虑右边每个点如何统计合法点对，看点 $(18,10)$ ，此时左边单调栈中元素应为 $(6,3),(0,8)$ ，但 $(18,10)$ 并不能都配对，因为 $(6,3)$ 被 $(16,4)$ “挡” 着。具体的：

现在枚举到右边的点 $i$ ，存在某右边的点 $p$ ， $X_p\lt X_i,Y_p\lt Y_i$ 挡住了左边所有 $X_j\lt X_p,Y_j\lt Y_p$ 的点也就是左边所有纵坐标小于 $Y_p$ 的点。那点 $i$ 只能管那些纵坐标在 $(Y_p,Y_i]$ 之间的左边的合法点。但若 $X_i\lt X_p$ 那便没有 $Y_p$ 的限制。于是我们对与右边的点维护 $X$ 坐标单调递减的栈。便可以知道纵坐标最高的横坐标比自己小的点。

还需对左边栈中的点维护纵坐标在什么范围有多少个点，树状数组即可。

CODE

~~代码其实挺短的，主要一开始想naive了，调了半天~~

#include <bits/stdc++.h>
#define _max(x,y) ((x>y)?x:y)
#define _min(x,y) ((x<y)?x:y)
using namespace std;
typedef long long ll;
template<typename T>
inline void red(T &x) {
    x=0;bool fg=0;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') fg^=1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(T)(ch^48),ch=getchar();
    if(fg) x=-x;
}
template<typename T> bool umax(T &x,T y) {return (x<y)?(x=y,true):(false);}
template<typename T> bool umin(T &x,T y) {return (x>y)?(x=y,true):(false);}
const int N = 200010;
typedef long long ll;
struct pt{
    int x,y;
    pt(){}
    pt(int _x,int _y){x=_x,y=_y;}
}p[N],tp[N];
int n,b[N],tot;ll ans;
bool cmpx(pt a,pt b) {return (a.x<b.x);}
bool cmpy(pt a,pt b) {return (a.y<b.y);}
struct trearr {
    int t[N],st[N],top;
    void add(int x,int v) {for(;x<=n;x+=x&-x) t[x]+=v;}
    int sum(int x) {int r=0;for(;x>0;x-=x&-x) r+=t[x];return r;}
}t;
void solve(int l,int r) {
    if(l==r) return ;
    int mid=(l+r)>>1;
    solve(l,mid);solve(mid+1,r);
    sort(p+l,p+mid+1,cmpy);sort(p+mid+1,p+r+1,cmpy);
    int cntl=-1,cntr=-1,j=l,lst=-1;
    for(int i=mid+1;i<=r;i++) {
        while(j<=mid&&p[j].y<p[i].y) {
            while(cntl>-1&&tp[l+cntl].x<p[j].x) {
                t.add(tp[l+cntl].y,-1);
                cntl--;
            }
            cntl++;tp[l+cntl]=p[j];
            t.add(p[j].y,1);
            j++;
        }
        while(cntr>-1&&tp[mid+1+cntr].x>p[i].x) cntr--;
        if(cntr>-1) ans+=t.sum(p[i].y)-t.sum(tp[mid+1+cntr].y);
        else ans+=t.sum(p[i].y);
        cntr++;tp[mid+1+cntr]=p[i];
    }
    for(int i=l;i<=l+cntl;i++) t.add(tp[i].y,-1);
}
int main() {
    red(n);
    for(int i=1;i<=n;i++) {
        red(p[i].x);red(p[i].y);
        b[++tot]=p[i].y;
    }
    sort(b+1,b+tot+1);
    for(int i=1;i<=n;i++) {
        p[i].y=lower_bound(b+1,b+tot+1,p[i].y)-b;
    }
    sort(p+1,p+n+1,cmpx);
    solve(1,n);
    printf("%lld\n",ans);
    return 0;
}