题解：P14426 [JOISC 2014] 稻草人 / Scarecrows

· · 题解

题意

平面上存在 n 个点，求满足 x_i<x_j\wedge y_i<y_j 且 i,j 两点围成的矩形内不存在其余点的点对数量。

思路

先对 x,y 离散化，考虑 cdq 分治。

先将点按照 x 排序，假设当前分治区间为 [l,r]，计算 [l,mid] 对于 [mid+1,r] 的贡献，由于事先排过序，左区间点的 x 一定小于右区间，再考虑第二维 y 的限制，不妨对左右分别按照 y 排序，那么枚举右区间的点，加入左区间中 y_i<y_j 的点即可。

再考虑第三个限制，对于左区间的点，可以用单调栈维护，当加入一个点时，弹出其左下角所有点，这些点一定是没有贡献的，然后按这个思路写了一个代码，发现样例都过不了，因为只考虑了左边点出现在矩形中的影响，而没有考虑右边的点，假设右区间存在点 i，左区间存在点 j，那么 i 对 j 有贡献还需要满足对于右区间的点，不存在 x_j<x_k<x_i\wedge y_j<y_k<y_i，去掉一些已经被限制了的条件，那么就是不存在 x_k<x_i\wedge y_j<y_k。那么可以对于右区间的点算出满足 x_k<x_i\wedge y_k<y_i 的所有点 k 中 y_k 的最大值，记为 pre_i，用树状数组容易维护。

那么限制就可以转化为找 pre_i<y_j<y_i 的点 j，这个也可以用树状数组维护，在维护单调栈的时候加点即可。

复杂度 O(n\log^2n)。

代码

注意要开 long long。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,ls[N];
long long ans=0;
struct node{
    int x,y;
}a[N];
bool cmpx(node A,node B){
    return A.x<B.x;
}
bool cmpy(node A,node B){
    return A.y<B.y;
}
struct Tree{
    int t[N];
    #define lobit(x) (x&(-x))
    void operator () (int x,int c){
        for(;x<=n;x+=lobit(x)) t[x]+=c;
    }
    int operator [] (int x){
        int ans=0;
        for(;x;x-=lobit(x)) ans+=t[x];
        return ans;
    }
    #undef lobit(x)
}T;
struct M{
    int t[N];
    #define lobit(x) (x&(-x))
    void operator () (int x,int c){
        for(;x<=n;x+=lobit(x)) if(c) t[x]=max(t[x],c); else t[x]=0;
    }
    int operator [] (int x){
        int ans=0;
        for(;x;x-=lobit(x)) ans=max(ans,t[x]);
        return ans;
    }
    #undef lobit(x)
}F;
int stk[N];
void solve(int l,int r){
    if(l==r) return;
    int mid=(l+r)>>1;
    solve(l,mid);solve(mid+1,r);
    sort(a+l,a+mid+1,cmpy);sort(a+mid+1,a+r+1,cmpy);
    int i=mid+1,j=l,top=0;
    for(;i<=r;i++){
        for(;j<=mid && a[j].y<a[i].y;j++){
            while(top && a[stk[top]].x<a[j].x) T(a[stk[top--]].y,-1);
            stk[++top]=j;
            T(a[j].y,1);
        }
        ans+=T[a[i].y]-T[F[a[i].x]];
        F(a[i].x,a[i].y);
    }
    while(top) T(a[stk[top--]].y,-1);
    for(int i=mid+1;i<=r;i++) F(a[i].x,0);
//  cout<<l<<" "<<r<<" "<<ans<<"\n";
}
signed mian(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y,ls[i]=a[i].x;
    sort(ls+1,ls+n+1);
    for(int i=1;i<=n;i++) a[i].x=lower_bound(ls+1,ls+n+1,a[i].x)-ls;
    for(int i=1;i<=n;i++) ls[i]=a[i].y;
    sort(ls+1,ls+n+1);
    for(int i=1;i<=n;i++) a[i].y=lower_bound(ls+1,ls+n+1,a[i].y)-ls;
    sort(a+1,a+n+1,cmpx);
    solve(1,n);
    cout<<ans;
    return 0;
}