#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct data
{
int x,y,k,r;
}a[];
struct dat
{
int x,y;
}b[];
bool cmp(dat a1,dat a2)
{
if(a1.x==a2.x)
return a1.y<a2.y;
return a1.x<a2.x;
}
int n,h[],h1[],shu[],cnt,ans;
void jia1(int a1,int a2)
{
cnt++;
a[cnt].x=lower_bound(h+,h+h[]+,b[a1].x)-h;
a[cnt].y=b[a1].y;
a[cnt].k=;
cnt++;
a[cnt].x=a[cnt-].x;
a[cnt].y=b[a2].y;
a[cnt].k=-;
}
bool cmp1(dat a1,dat a2)
{
if(a1.y==a2.y)
return a1.x<a2.x;
return a1.y<a2.y;
}
void jia2(int a1,int a2)
{
cnt++;
a[cnt].y=b[a1].y;
a[cnt].x=lower_bound(h+,h+h[]+,b[a1].x)-h;
a[cnt].r=lower_bound(h+,h+h[]+,b[a2].x)-h;
}
bool cmp2(data a1,data a2)
{
if(a1.y==a2.y)
return a1.k<a2.k;
return a1.y<a2.y;
}
int zhao(int a1)
{
int sum=;
for(;a1;a1-=a1&-a1)
sum+=shu[a1];
return sum;
}
void gai(int a1,int a2)
{
for(;a1<=h[];a1+=a1&-a1)
shu[a1]+=a2;
return;
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d%d",&b[i].x,&b[i].y);
for(int i=;i<=n;i++)
h1[i]=b[i].x;
sort(h1+,h1++n);
h[]=h1[];
h[]=;
for(int i=;i<=n;i++)
if(h1[i]!=h1[i-])
{
h[]++;
h[h[]]=h1[i];
}
sort(b+,b+n+,cmp);
for(int i=;i<=n;i++)
if(b[i].x==b[i-].x)
jia1(i-,i);
sort(b+,b+n+,cmp1);
for(int i=;i<=n;i++)
if(b[i].y==b[i-].y)
jia2(i-,i);
sort(a+,a+cnt+,cmp2);
for(int i=;i<=cnt;i++)
if(a[i].k==)
ans+=zhao(a[i].r-)-zhao(a[i].x);
else
gai(a[i].x,a[i].k);
printf("%d",ans+n);
return ;
}
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct data
{
int x,y,k,r;
}a[];
struct dat
{
int x,y;
}b[];
bool cmp(dat a1,dat a2)
{
if(a1.x==a2.x)
return a1.y<a2.y;
return a1.x<a2.x;
}
int n,h[],h1[],shu[],cnt,ans;
void jia1(int a1,int a2)
{
cnt++;
a[cnt].x=lower_bound(h+,h+h[]+,b[a1].x)-h;
a[cnt].y=b[a1].y;
a[cnt].k=;
cnt++;
a[cnt].x=a[cnt-].x;
a[cnt].y=b[a2].y;
a[cnt].k=-;
}
bool cmp1(dat a1,dat a2)
{
if(a1.y==a2.y)
return a1.x<a2.x;
return a1.y<a2.y;
}
void jia2(int a1,int a2)
{
cnt++;
a[cnt].y=b[a1].y;
a[cnt].x=lower_bound(h+,h+h[]+,b[a1].x)-h;
a[cnt].r=lower_bound(h+,h+h[]+,b[a2].x)-h;
}
bool cmp2(data a1,data a2)
{
if(a1.y==a2.y)
return a1.k<a2.k;
return a1.y<a2.y;
}
int zhao(int a1)
{
int sum=;
for(;a1;a1-=a1&-a1)
sum+=shu[a1];
return sum;
}
void gai(int a1,int a2)
{
for(;a1<=h[];a1+=a1&-a1)
shu[a1]+=a2;
return;
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d%d",&b[i].x,&b[i].y);
for(int i=;i<=n;i++)
h1[i]=b[i].x;
sort(h1+,h1++n);
h[]=h1[];
h[]=;
for(int i=;i<=n;i++)
if(h1[i]!=h1[i-])
{
h[]++;
h[h[]]=h1[i];
}
sort(b+,b+n+,cmp);
for(int i=;i<=n;i++)
if(b[i].x==b[i-].x)
jia1(i-,i);
sort(b+,b+n+,cmp1);
for(int i=;i<=n;i++)
if(b[i].y==b[i-].y)
jia2(i-,i);
sort(a+,a+cnt+,cmp2);
for(int i=;i<=cnt;i++)
if(a[i].k==)
ans+=zhao(a[i].r-)-zhao(a[i].x);
else
gai(a[i].x,a[i].k);
printf("%d",ans+n);
return ;
}
将点拆成横线与点，用树状数组维护。