BZOJ_1818_[Cqoi2010]内部白点 _扫描线+树状数组

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 300050
int n,V[N],c[N];
struct P {
	int x,y;
}a[N];
inline bool cmp1(const P &x,const P &y) {return x.x==y.x?x.y<y.y:x.x<y.x;}
inline bool cmp2(const P &x,const P &y) {return x.y==y.y?x.x<y.x:x.y<y.y;}
struct A {
	int x,y,z,opt,pri;
	bool operator < (const A &u) const {
		return x==u.x?pri<u.pri:x<u.x;
	}
}q[N];
void fix(int x,int v) {for(;x<=n;x+=x&(-x)) c[x]+=v;}
int inq(int x) {int re=0;for(;x;x-=x&(-x)) re+=c[x]; return re;}
int main() {
	scanf("%d",&n);
	int i,cnt=0;
	for(i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y),V[i]=a[i].y;
	sort(V+1,V+n+1);
	int ww=unique(V+1,V+n+1)-V-1;
	for(i=1;i<=n;i++) a[i].y=lower_bound(V+1,V+ww+1,a[i].y)-V;
	sort(a+1,a+n+1,cmp1);
	for(i=1;i<=n;i++) {
		int j=i;
		for(;i<n&&a[i+1].x==a[j].x;i++);
		q[++cnt]=(A){a[j].x,a[j].y,a[i].y,1,2};
	}
	sort(a+1,a+n+1,cmp2);
	for(i=1;i<=n;i++) {
		int j=i;
		for(;i<n&&a[i+1].y==a[j].y;i++);
		q[++cnt]=(A){a[j].x,a[j].y,1,0,1};
		q[++cnt]=(A){a[i].x,a[j].y,-1,0,3};
	}
	sort(q+1,q+cnt+1);
	int ans=0;
	for(i=1;i<=cnt;i++) {
		if(q[i].opt==0) fix(q[i].y,q[i].z);
		else {
			ans+=inq(q[i].z)-inq(q[i].y-1);
		}
	}
	printf("%d\n",ans);
}