牛客挑战赛40 VMware和基站 set 二分启发式合并区间覆盖

LINK：VMware和基站

一道做法并不常见的题目看起来很难写其实set维护线段就可以解决了。

容易想到第二个操作借用启发式合并可以得到一个很不错的复杂度不过利用线段树维护这个东西在区间覆盖的时候并不能很好的维护。

一个想法是分块不过操作比较ex.

第一个操作和第二个操作连在一起会非常的难以处理。

这里给出的做法是：使用set来维护整段的线段这样在第一个区间覆盖的情况下每次区间至多增加两个或者可能减少.

在第一步中就是logn的时间内可以维护了.不过细节较多我分类讨论了好几种情况。

考虑第二步不妨每个基站都开一个set 利用启发式合并来做。

不过不存在操作1的时候启发式合并的总复杂度为nlog^2 存在操作1的时候容易发现每次区间最多增加两个那么均摊到启发式合并上也是Qlog的时间。

对于第三步直接在set中二分分类讨论在左边还是右边即可.

挺难写的三个函数都出了锅第一个是少考虑了情况第二个是没有对s进行修改第三个则是答案的情况存在小细节问题写死我了.

const int MAXN=100010,G=3;

int n,Q;

struct wy

{

	int l,r,id;

	wy(int x,int y,int z){l=x;r=y;id=z;}

	inline bool operator <(wy a)const {return l<a.l;}

};

set<wy>s;set<pii>g[MAXN];

set<wy>::iterator it;

set<pii>::iterator itt;

char a[10];

int f[MAXN];

inline void cover(int l,int r,int x)

{

	it=s.upper_bound(wy(l,r,x));--it;

	if((*it).l!=l)

	{

		int id=(*it).id;int L=(*it).l;int R=(*it).r;

		g[id].erase(mk(L,R));g[id].insert(mk(L,l-1));

		s.erase(it);s.insert(wy(L,l-1,id));

		g[x].insert(mk(l,r));

		s.insert(wy(l,r,x));it=s.find(wy(l,r,x));

		if(R>r)

		{

			g[id].insert(mk(r+1,R));

			s.insert(wy(r+1,R,id));

			return;

		}

		if(R==r)return;++it;

		while(it!=s.end())

		{

			R=(*it).r;

			if(R<=r)

			{

				g[(*it).id].erase(mk((*it).l,(*it).r));

				s.erase(it);it=s.find(wy(l,r,x));++it;

				if(R==r)break;

			}

			else

			{

				id=(*it).id;

				g[id].erase(mk((*it).l,R));

				g[id].insert(mk(r+1,R));

				s.erase(it);s.insert(wy(r+1,R,id));

				break;

			}

		}

	}

	else

	{

		int id=(*it).id;int R=(*it).r;

		//cout<<id<<endl;

		g[id].erase(mk(l,(*it).r));

		s.erase(it);s.insert(wy(l,r,x));it=s.find(wy(l,r,x));

		g[x].insert(mk(l,r));

		if(R>r)

		{

			g[id].insert(mk(r+1,R));

			s.insert(wy(r+1,R,id));

			return;

		}

		if(R==r)return;++it;

		while(it!=s.end())

		{

			R=(*it).r;

			//cout<<R<<endl;

			if(R<=r)

			{

				g[(*it).id].erase(mk((*it).l,(*it).r));

				s.erase(it);it=s.find(wy(l,r,x));++it;

				if(R==r)break;

			}

			else

			{

				id=(*it).id;

				g[id].erase(mk((*it).l,R));

				g[id].insert(mk(r+1,R));

				s.erase(it);s.insert(wy(r+1,R,id));

				break;

			}

		}

	}

}

inline void replace(int &x,int &y)

{

	if(x==y)return;

	if(g[x].size()>g[y].size())swap(x,y);

	itt=g[x].begin();

	while(itt!=g[x].end())

	{

		it=s.find(wy((*itt).F,(*itt).S,x));

		s.erase(it);

		s.insert(wy((*itt).F,(*itt).S,y));

		g[y].insert(*itt);

		++itt;

	}

	g[x].clear();

}

inline int ask(int D,int L,int R,int id)

{

	if(!g[id].size())return -1;

	int ans=-1;

	itt=g[id].lower_bound(mk(L,0));

	if(itt!=g[id].end()&&(*itt).F<=R)ans=max(ans,abs(D-(*itt).F));

	if(itt!=g[id].begin())

	{

		--itt;

		//cout<<(*itt).F<<' '<<(*itt).S<<endl;

		if((*itt).F<=L&&(*itt).S>=L)ans=max(ans,abs(D-L));

	}

	itt=g[id].upper_bound(mk(R,n+1));

	if(itt!=g[id].begin())

	{

		--itt;

		if((*itt).F<=R&&(*itt).S>=R)ans=max(ans,abs(D-R));

		if((*itt).S<=R&&(*itt).S>=L)ans=max(ans,abs(D-(*itt).S));

		//cout<<(*itt).S<<' '<<(*itt).F<<endl;

	}

	return ans;

}

int main()

{

	//freopen("1.in","r",stdin);

	gt(n);gt(Q);

	rep(1,n,i)g[i].insert(mk(i,i)),s.insert(wy(i,i,i)),f[i]=i;

	rep(1,Q,i)

	{

		int x,y,z;

		gc(a);gt(x);gt(y);

		if(a[1]=='c')gt(z),cover(x,y,f[z]);

		if(a[1]=='r')replace(f[x],f[y]);

		if(a[1]=='f')gt(z),put(ask(x,max(x-y,1),min(x+y,n),f[z]));

	}

	return 0;

}

巴特西

牛客挑战赛40 VMware和基站 set 二分启发式合并区间覆盖

最新文章

热门文章

巴特西

牛客挑战赛40 VMware和基站 set 二分 启发式合并 区间覆盖

最新文章

热门文章

牛客挑战赛40 VMware和基站 set 二分启发式合并区间覆盖