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

FS_NEO · 2025-11-12 11:50:31 · 题解

唐题，为什么别的题解写那么长。

先按照 x 排序，然后 CDQ 分治。分治中按照 y 排序，用左边贡献右边。发现左边可以按照 x 坐标维护一个单调栈，右边点能匹配的左边点数量就在单调栈上二分一下。

/*

        2025.11.11

  * Happy Zenith Noises *

*/
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef pair<int,int>P;
const int MAXN=200005,inf=0x3f3f3f3f3f3f3f3f;
int n,ans,fs[MAXN];
P a[MAXN],b[MAXN];
struct que{
    int h,t;
    P q[MAXN];
    void init(){h=0,t=1;}
    void insert(P x){
        while(h>=t&&q[h].fi<x.fi)h--;
        q[++h]=x;
    }
    int ask(int x){
        if(h<t)return 0;
        int l=t,r=h;
        while(l<r){
            int mid=(l+r)>>1;
            if(q[mid].se>=x)r=mid;
            else l=mid+1;
        }
        if(q[l].se>=x)return h-l+1;
        return 0;
    }
}st;
struct BIT{
    int f[MAXN];vector<int>gg;
    void init(){for(int i:gg)f[i]=0;gg.clear();}
    void add(int x,int t){for(;x<MAXN;x+=(x&-x))f[x]=max(f[x],t),gg.pb(x);}
    int ask(int x){int ans=0;for(;x;x-=(x&-x))ans=max(ans,f[x]);return ans;}
}tr;
void solve(int l,int r){
    if(l==r)return ;
    int mid=(l+r)>>1;
    solve(l,mid);solve(mid+1,r);
    int tl=l,tr=mid+1;
    ::tr.init();st.init();
    for(int i=l;i<=r;i++){
        if(tr==r+1||tl<=mid&&a[tl].se<a[tr].se){
            st.insert(a[tl]);
            b[i]=a[tl++];
        }
        else{
            ans+=st.ask(::tr.ask(a[tr].fi-1));
            ::tr.add(a[tr].fi,a[tr].se);b[i]=a[tr++];
        }
    }
    for(int i=l;i<=r;i++)a[i]=b[i];
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(nullptr);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i].fi>>a[i].se,a[i].fi++,a[i].se++,fs[i]=a[i].fi;
    sort(fs+1,fs+1+n);int tn=unique(fs+1,fs+1+n)-(fs+1);
    for(int i=1;i<=n;i++)a[i].fi=lower_bound(fs+1,fs+1+tn,a[i].fi)-fs;
    sort(a+1,a+1+n);
    solve(1,n);
    cout<<ans;
    return 0;
}