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

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