题意
在一个二维平面上，给定点集 $S$，求所有满足
- \large{x_i\lt x_j} ；
- \large{y_i\lt y_j} ；
- \large{\forall k\in S\cap\{i,j\}} ，有 \large{x_k\notin[x_i,x_j] , y_k\notin [y_i , y_j]} ；
的点对 (i,j) 的数量。
Solution
发现对于一个点 i 而言，对答案的贡献应为在它右上方的点所形成的凸包的大小。即其右上方 x 最接近于 x_i 和 y 最接近于 y_i 的两个点之间形成的类下凸包大小。令二者分别为 pre_i 和 r_i 。
形式化地， \forall k\in T_i ，有 x_i\lt x_k,y_i\lt y_k 。
则 pre_i \in T_i ， \forall k \in T_i ，有 \lvert x_{pre_{j}}-x_i\lvert \leq \lvert x_k-x_i\lvert 。
同样地，有 r_i \in T_i ， \forall k \in T_i ，有 \lvert y_{r_{j}}-y_i\lvert \leq \lvert y_k-y_i\lvert 。
则对答案可以产生贡献的点集为 pre_i,a_1,\cdots,a_p,r_i ，满足 a_i\in T_i ， x_{a_{i-1}}\lt x_{a_i}\lt x_{a_{i+1}} ，且 y_{a_{i-1}}\lt y_{a_i}\lt y_{a_{i+1}} 。
对于每个数，单调栈维护类下凸包即可，时间复杂度为 \mathcal{O}(n^2) 。
考虑优化，发现不必要对于每个点重新计算答案，考虑对于 x 或 y 区间分治并合并答案。以分治 x 坐标为例，从 y_{max} 向下不断枚举。对于 [mid+1,right] 区间，维护一个类下凸包，每个点满足在前一个点的右下方。对于 [left,mid] 区间，也维护一个类下凸包，每个点满足在前一个点的左下方，对于新加入的点 i ，在类下凸包中的前一个点对 i 对答案贡献的影响最大，即前文提到的 pre_i 。在右区间的类下凸包中，所有 y\ge y_{pre_{i}} 的点都不产生贡献了，可以在右区间的单调栈中二分找到分界。
时间复杂度为 \mathcal{O}(n\log^2n) ，可以通过本题。
code
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int res=0,flag=1;
char ch=getchar();
while(!isalnum(ch)) (ch=='-')?flag=-1:1,ch=getchar();
while(isalnum(ch)) res=res*10+ch-'0',ch=getchar();
return res*flag;
}
struct Stack
{
int head;
std::pair<int,int> val[200010];
void push(pair<int,int> value)
{
val[++head]=value;
return ;
}
void pop() { head--; return ; }
pair<int,int> top() { return val[head]; }
bool empty() { return !head; }
void clear() { head=0; return ; }
int solve(int pos)
{
int left=1,right=head,res=head+1;
while(left<=right)
{
int mid=(left+right)>>1;
if(val[mid].second<pos)
res=mid,right=mid-1;
else
left=mid+1;
}
if(res==head+1)
return 0;
return head-res+1;
}
};
struct Stack a,b;
int n;
long long ans;
void solve(int left,int right,vector<pair<int,int> > val)
{
b.push(make_pair(0x3f3f3f3f,0x3f3f3f3f));
if(left==right)
{
ans+=val.size()-1;
return ;
}
int mid=(left+right)>>1;
vector<pair<int,int> > l,r;
l.clear(),r.clear();
for(auto i=val.begin();i!=val.end();i++)
{
if(i->first<=mid)
{
l.push_back(*i);
while(b.empty()==false&&b.top().first<i->first)
b.pop();
ans+=a.solve(b.top().second);
b.push(*i);
}
if(i->first>mid)
{
r.push_back(*i);
while(a.empty()==false&&a.top().first>=i->first)
a.pop();
a.push(*i);
}
}
a.clear(),b.clear();
if(l.size()>=1) solve(left,mid,l);
if(r.size()>=1) solve(mid+1,right,r);
return ;
}
int main(int argc,const char *argv[])
{
n=read();
int left=INT_MAX,right=0;
vector<pair<int,int> > val;
for(int i=1;i<=n;i++)
{
int x=read(),y=read();
val.push_back(make_pair(x,y));
left=std::min(left,x);
right=std::max(right,x);
}
std::sort(val.begin(),val.end(),[](pair<int,int> a,pair<int,int> b){return (a.second==b.second)?(a.first>b.first):(a.second>b.second);});
solve(left,right,val);
printf("%lld\n",ans);
return 0;
}