Codeforces Round #452 (Div. 2) 899E E. Segments Removal

题

　　OvO http://codeforces.com/contest/899/problem/E

　　Codeforces Round #452 (Div. 2) - e

　　899E

解

　　用两个并查集（记为fa和ma），

　　fa用于更新可以合并在一起的段，维护每个段的左端点，右端点，中间有多少个相同的值，和这个段的值得是什么，

　　ma用于跳跃，　

　　具体来说

　　例如

　　这组数据

　　标上序号（第三行是序号）

　　1.那么首先合并4个5（10-13），显然9所在的段和14所在的段不能合并

　　　那么把13指向9( ma[13]=9 ) 然后把10指向14( ma[10]=14 )

　　2.然后合并3个4( 7-9 )，判断合并的两个位置记为a和b，首先a=6，b本来等于10，然后通过并查集ma更改b=14，显然不能合并

　　　那么同样 ma[7]=10, ma[9]=6

　　3.然后合并3个6( 14-16 )，判断合并的位置是 a=13 和 b=17 ，通过并查集ma更改a=6

　　　显然 a 所在段的值和 b 所在段的值是一样的，而且a和b所在段都未处理过，通过fa并查集处理 a 和 b 找到 a ,b在fa并查集的祖先，就可以合并a和b所在段。

　　对于寻找哪个段最长的话，通过一个保存段长度的优先队列来查找

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <queue>

using namespace std;

const int M=2e5+44;

struct Node

{

	int id,num,li,ri,cnt;

	friend bool operator<(Node x,Node y)

	{

		if(x.cnt==y.cnt) return x.id>y.id;

		return x.cnt<y.cnt;

	}

} p[M];

priority_queue<Node> que;

int n,fa[M],ma[M];

int fff(int rt)

{

	if(fa[rt]==rt)

		return rt;

	return fa[rt]=fff(fa[rt]);

}

int emm(int rt)

{

	if(ma[rt]==rt)

		return rt;

	return ma[rt]=emm(ma[rt]);

}

void merge(int a,int b,int flag)

{

	if(a<1 || b>n)

		return ;

	int qa=emm(a),qb=emm(b);

	int qqa=fff(qa),qqb=fff(qb);

	if(p[qa].num!=p[qb].num || p[qqa].cnt==-1 || p[qqb].cnt==-1)

	{

		int xa=a+1,xb=b-1;

		ma[xb]=a; ma[xa]=b;

		return ;

	}

	int pa=qqa,pb=qqb;

	fa[pb]=pa;

	p[pa].cnt+=p[pb].cnt,p[pa].li=min(p[pa].li,p[pb].li),p[pa].ri=max(p[pa].ri,p[pb].ri);

	p[pb].cnt=-1;

	if(flag)

		que.push(p[pa]);

}

int main()

{

	Node now;

	int nowid,ans;

	scanf("%d",&n);

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

	{

		scanf("%d",&p[i].num);

		p[i].id=i; p[i].li=p[i].ri=i; p[i].cnt=1;

		fa[i]=i; ma[i]=i;

	}

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

		if(p[i].num==p[i-1].num)

			merge(i-1,i,0);

	while(!que.empty())

		que.pop();

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

		if(p[i].cnt!=-1)

			que.push(p[i]);

	ans=0;

	while(!que.empty())

	{

		now=que.top(); que.pop();

		nowid=now.id;

		if(p[nowid].cnt!=now.cnt) continue;

//		cout<<p[nowid].li<<' '<<p[nowid].ri<<' '<<p[nowid].num<<endl;

		ans++; p[nowid].cnt=-1;

		merge(now.li-1,now.ri+1,1);

	}

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

	return 0;

}

/*

19

1  1  2  2  3  3  4  4  4  5  5  5  5  6  6  6  3  2  1

*/

巴特西

Codeforces Round #452 (Div. 2) 899E E. Segments Removal

最新文章

热门文章