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

/*

		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;
}