扫描线。
cmp不要乱打。。。。。最后一个一定不要if直接return。
感谢http://hzwer.com/1836.html
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 100500 using namespace std; int n,hash[maxn],top=0,t[maxn],cnt=0; struct pnt { int x,y; }p[maxn]; struct query { int y,l,r,x,type; }q[maxn*10]; bool cmp1(pnt x,pnt y) { if (x.y!=y.y) return x.y<y.y; return x.x<y.x; } bool cmp2(pnt x,pnt y) { if (x.x!=y.x) return x.x<y.x; return x.y<y.y; } bool cmp3(query x,query y) { if (x.y!=y.y) return x.y<y.y; return x.type<y.type; } int find(int x) { return lower_bound(hash+1,hash+top+1,x)-hash; } void addq(int x,int y,int type) { if (type==0) { cnt++; q[cnt].y=p[x].y;q[cnt].type=type;q[cnt].x=0; q[cnt].l=find(p[x].x);q[cnt].r=find(p[y].x); } else { cnt++; q[cnt].y=p[x].y;q[cnt].type=type; q[cnt].x=find(p[x].x);q[cnt].l=q[cnt].r=0; } } void build_line() { sort(p+1,p+n+1,cmp1); for (int i=2;i<=n;i++) { if (p[i-1].y==p[i].y) addq(i-1,i,0); } sort(p+1,p+n+1,cmp2); for (int i=2;i<=n;i++) { if (p[i-1].x==p[i].x) { addq(i-1,0,1); addq(i,0,-1); } } sort(q+1,q+cnt+1,cmp3); } int lowbit(int x) { return (x&(-x)); } void modify(int x,int val) { for (int i=x;i<=top;i+=lowbit(i)) t[i]+=val; } int ask(int x) { int ret=0; for (int i=x;i>=1;i-=lowbit(i)) ret+=t[i]; return ret; } void get_ans() { int ans=0; for (int i=1;i<=cnt;i++) { if (q[i].type==-1) modify(q[i].x,-1); else if (q[i].type==1) modify(q[i].x,1); else ans+=ask(q[i].r-1)-ask(q[i].l); } printf("%d ",ans+n); } int main() { scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%d%d",&p[i].x,&p[i].y); hash[++top]=p[i].x; } sort(hash+1,hash+top+1);top=unique(hash+1,hash+top+1)-hash-1; build_line(); get_ans(); return 0; }