#include<bits/stdc++.h>
using namespace std;
const int N=110005;
int n,tree[4*N];
template<class TT>inline void read(TT &xx)
{
xx=0;char cc=getchar();bool ff=false;
while(cc<'0'||cc>'9'){if(cc=='-')ff=true;cc=getchar();}
while(cc>='0'&&cc<='9'){xx=(xx<<3)+(xx<<1)+cc-'0';cc=getchar();}
if(ff)xx=-xx;
}
int x[N],y[N];
int orix[N],oriy[N],totx,toty;
int up[N],down[N],lef[N],rig[N];
struct line
{
int type;//0表示横线,1表示竖线起点,-1表示竖线终点
int st,end,p;
bool operator <(const line qwe)
{
if(p!=qwe.p) return p<qwe.p;
else return type<qwe.type;
}
}a[N];
int cnt;
#define lowbit(as) as&(-as)
void add(int x,int num){while(x<=totx+1){tree[x]+=num,x+=lowbit(x);}}
int query(int x){int sum=0; while(x>0){sum+=tree[x];x-=lowbit(x);} return sum;}
#define J
#define F
int main()
{
#ifdef F
freopen("dot1.in","r",stdin);
#endif
read(n);
#ifdef J
printf("n=%d\n",n);
#endif
for(int i=1;i<=n;i++)
{
read(orix[i]);read(oriy[i]);
x[i]=orix[i];y[i]=oriy[i];
}
sort(orix+1,orix+n+1);totx=unique(orix+1,orix+n+1)-orix-1;
sort(oriy+1,oriy+n+1);toty=unique(oriy+1,oriy+n+1)-oriy-1;
#ifdef J
printf("totx=%d toty=%d\n",totx,toty);
#endif
for(int i=1;i<=n;i++)
{
x[i]=lower_bound(orix+1,orix+totx+1,x[i])-orix;
y[i]=lower_bound(oriy+1,oriy+toty+1,y[i])-oriy;
}
memset(down,0x3f,sizeof(down));
memset(lef,0x3f,sizeof(lef));
memset(rig,-1,sizeof(rig));
memset(up,-1,sizeof(up));
for(int i=1;i<=n;i++)
{
up[x[i]]=max(up[x[i]],y[i]);
down[x[i]]=min(down[x[i]],y[i]);
lef[y[i]]=min(lef[y[i]],x[i]);
rig[y[i]]=max(rig[y[i]],x[i]);
}
for(int i=1;i<=totx;i++)
{
#ifdef J
printf("竖着i=%d up=%d down=%d\n",i,up[i],down[i]);
#endif
if(up[i]!=down[i])
{
a[++cnt]=(line){1,i,i,down[i]};
a[++cnt]=(line){-1,i,i,up[i]};
}
}
for(int i=1;i<=toty;i++)
{
#ifdef J
printf("横着i=%d left=%d right=%d\n",i,lef[i],rig[i]);
#endif
if(lef[i]!=rig[i])
{
a[++cnt]=(line){0,lef[i],rig[i],i};
}
}
sort(a+1,a+cnt+1);
long long ans=0;
for(int i=1;i<=cnt;i++)
{
#ifdef J
printf("type=%d l=%d r=%d p=%d\n",a[i].type,a[i].st,a[i].end,a[i].p);
#endif
if(a[i].type==0) ans+=query(a[i].end-1)-query(a[i].st);
else add(a[i].st,a[i].type);
}
printf("%lld\n",ans+n);
return 0;
}
我就是用的扫描线+是树状数组,不知道哪里错了,求助/kel