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

· · 题解

经典分治题，好像看到有人拿分块过了，拿分块过这题的这辈子有了。

平面上考虑按照长边拆开，处理坐标跨过中点的部分，例如按照 y 拆开：

容易发现两点可以匹配当且仅当上部是 \min，下部是 \max，单调栈+BIT 可以维护。

这道题保证了 x,y 坐标互不相等，所以不用按照长边拆开，直接拆一维即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll1;
#define fir first
#define sec second
#define pii pair<int,int>
#define mkp make_pair
const int N=2e5+5;
const int inf=1e9+7;
ll1 Ans=0;
vector<pii>a;
int XS[N],YS[N];
void dsc(vector<pii>&p){
    int tot=0;
    for(auto [x,y]:p)++tot,XS[tot]=x,YS[tot]=y;
    sort(XS+1,XS+1+tot),sort(YS+1,YS+1+tot);
    for(int i=0;i<p.size();i++){
        p[i].fir=lower_bound(XS+1,XS+1+tot,p[i].fir)-XS;
        p[i].sec=lower_bound(YS+1,YS+1+tot,p[i].sec)-YS;
    }
    sort(p.begin(),p.end());
}
#define lowbit(x) (x&-x)
namespace BIT{
    int bit[N],ALL;
    void init(int len){ALL=len;for(int i=1;i<=len;i++)bit[i]=0;}
    void add(int x,int y){for(;x<=ALL;x+=lowbit(x))bit[x]+=y;}
    int qry(int x){int res=0;for(;x;x-=lowbit(x))res+=bit[x];return res;}
}
#undef lowbit
pii stkup[N];
int tu;
pii stkdn[N];
int td;
void solve(vector<pii> p){
    if(p.size()==1)return;
    int ymd=(p.size()+1)>>1;
    {//Ypart
        tu=td=0;
        stkup[0]=mkp(0,0),stkdn[0]=mkp(0,inf);
        dsc(p);
        vector<pii>lp,rp;
        int n=p.size();BIT::init(n);
        for(int i=1;i<=n;i++){
            auto [x,y]=p[i-1];
            if(y<=ymd){
                while(stkdn[td].sec<y)
                    BIT::add(stkdn[td].fir,-1),td--;
                stkdn[++td]=p[i-1],BIT::add(x,1);
                lp.emplace_back(p[i-1]);
            }else{
                while(stkup[tu].sec>y)tu--;
                Ans+=BIT::qry(x)-BIT::qry(stkup[tu].fir);
                stkup[++tu]=p[i-1];
                rp.emplace_back(p[i-1]);
            }
        }
        solve(lp),solve(rp);
    }
}
int n;
int main(){
    scanf("%d",&n);
    for(int i=1,x,y;i<=n;i++)
        scanf("%d%d",&x,&y),a.emplace_back(mkp(x,y));
    solve(a);
    printf("%lld\n",Ans);
    return 0;
}