BZOJ 1818 Cqoi2010 內部白點 樹狀數組

BZOJ 1818 Cqoi2010 內部白點 樹狀數組

題目大意：給定平面上的一些黑點，其它位置都是白點，一個白點如果上下左右都有黑點就會變成黑點，求最終會有多少個黑點

語文題？

總之我們現在得到了一些橫向和縱向的線段(注意線段不能包含兩端點！)，求出交點數後+n就是答案

我們可以將橫向線段看做修改，縱向線段看做詢問，那麼一個詢問可以拆成兩個

然後我們離線做，將詢問按y坐標排序，對於每個詢問將y坐標小於等於這個詢問的修改都加入樹狀數組，然後查詢這個詢問的x坐標即可

懶得離散化，第一次嘗試用Hash表寫樹狀數組，效果還不錯= =

時間復雜度O(nlogn)

#include 
#include 
#include 
#include 
#define M 100100
using namespace std;
struct Point{
	int x,y;
	friend istream& operator >> (istream &_,Point &p)
	{
		scanf("%d%d",&p.x,&p.y);
		p.x+=1000000007;
		p.y+=1000000007;
		return _;
	}
}points[M];
struct Interval{
	int l,r,y;
	Interval() {}
	Interval(int _,int __,int ___):
		l(_),r(__),y(___) {}
	bool operator < (const Interval &i) const
	{
		return y < i.y;
	}
}intervals[M],*I=intervals;
struct Query:Point{
	int flag;
	Query() {}
	Query(int _,int __,int ___):flag(___)
	{
		x=_;y=__;
	}
}queries[M<<1],*Q=queries;
int n;
long long ans;
bool Compare1(const Point &p1,const Point &p2)
{
	if(p1.x!=p2.x)
		return p1.xnext)
				if(temp->hash==hash)
					return temp->val;
			return (head[pos]=new List(hash,head[pos]))->val;
		}
	}c;
	void Update(int x,int y)
	{
		for(;x;x-=x&-x)
			c[x]+=y;
	}
	int Get_Ans(long long x)
	{
		int re=0;
		for(;x<=2000000007;x+=x&-x)
			re+=c[x];
		return re;
	}
}
int main()
{
	using namespace BIT;
	int i;
	cin>>n;
	for(i=1;i<=n;i++)
		cin>>points[i];
	sort(points+1,points+n+1,Compare2);
	for(i=2;i<=n;i++)
		if(points[i].y==points[i-1].y&&points[i].x>=points[i-1].x+2)
			new (I++)Interval(points[i-1].x+1,points[i].x-1,points[i].y);
	sort(points+1,points+n+1,Compare1);
	for(i=2;i<=n;i++)
		if(points[i].x==points[i-1].x&&points[i].y>=points[i-1].y+2)
		{
			new (Q++)Query(points[i].x,points[i-1].y,-1);
			new (Q++)Query(points[i].x,points[i].y-1,1);
		}
	sort(intervals,I);
	sort(queries,Q,Compare2);
	Interval *_i=intervals;
	Query *_q=queries;
	for(;_qy<=_q->y;_i++)
			Update(_i->l-1,-1),Update(_i->r,1);
		ans+=Get_Ans(_q->x)*_q->flag;
	}
	cout<