BZOJ 1818: [Cqoi2010]内部白点(树状数组)

解题思路

　　首先一定不可能有\(-1\)的情况，因为新产生的黑点不会造成任何贡献，它的各个方面都是不优的。那么只需要统计一遍答案，首先要将横坐标相同的两个点看成一条竖线，纵坐标相同的点看成一条横线，然后从下往上扫描，遇到竖线的下端点时，在树状数组里\(+1\)，遇到竖线上端点时，\(-1\)，然后遇到横线时就统计答案。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=100005;

inline int rd(){

	int x=0,f=1;char ch=getchar();

	while(!isdigit(ch)) f=ch=='-'?0:1,ch=getchar();

	while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

	return f?x:-x;

}

int n,a[N],ans,cnt,f[N],u;

struct Node{

	int x,y;

}node[N];	

struct Data{

	int x,y,k,z;

	friend bool operator<(const Data A,const Data B){

		return A.y==B.y?A.k>B.k:A.y<B.y;

	}

}data[N<<2];

inline bool cmp1(Node A,Node B){

	return A.x==B.x?A.y<B.y:A.x<B.x;

}

inline bool cmp2(Node A,Node B){

	return A.y==B.y?A.x<B.x:A.y<B.y;

}

inline void Insert(int x,int l,int r,int k){

	if(!k) {data[++cnt].x=l; data[cnt].z=r; data[cnt].y=x;}

	else {

		data[++cnt].x=x; data[cnt].y=l; data[cnt].k=1;

		data[++cnt].x=x; data[cnt].y=r; data[cnt].k=-1;

	}

}	

inline void build(){

	sort(node+1,node+1+n,cmp1);

	for(int i=2;i<=n;i++)

		if(node[i].x==node[i-1].x)

			Insert(node[i].x,node[i-1].y,node[i].y,1);

	sort(node+1,node+1+n,cmp2);

	for(int i=2;i<=n;i++)

		if(node[i].y==node[i-1].y)

			Insert(node[i].y,node[i-1].x,node[i].x,0);

}

inline void update(int x,int y){

	for(;x<=u;x+=x&-x) f[x]+=y;

}

inline int query(int x){

	int ret=0;

	for(;x;x-=x&-x) ret+=f[x];

	return ret;

}

inline void work(){

	sort(data+1,data+1+cnt);

	for(int i=1;i<=cnt;i++){

		if(!data[i].k) ans+=query(data[i].z-1)-query(data[i].x);

		else update(data[i].x,data[i].k);

	}

}

int main(){

	n=rd(); ans=n; int x,y;

	for(int i=1;i<=n;i++){

		x=rd(),y=rd(); a[i]=x;

		node[i].x=x,node[i].y=y;

	}

	sort(a+1,a+1+n); u=unique(a+1,a+1+n)-a-1;

	for(int i=1;i<=n;i++)

		node[i].x=lower_bound(a+1,a+1+u,node[i].x)-a;

	build(); work();

	printf("%d\n",ans);

	return 0;

}

巴特西

BZOJ 1818: [Cqoi2010]内部白点(树状数组)

解题思路

代码

最新文章

热门文章