题解 CF600E 【Lomsat gelral】

没有多少人用莫队做吗？

蒟蒻水一波莫队

这是一道树上莫队好题。

时间复杂度（\(n\sqrt{n}logn\))

蒟蒻过菜，不会去掉logn的做法qaq

思路很简单：

1.dfs跑一下树上点的dfs序。

2.将树上点按dfs序进行\(\sqrt{n}\) 分块。

3.对每个点按左端点的块序号和右端点的大小排序。

inline int cmp(Node aa,Node bb)

{

	return aa.ls==bb.ls?aa.r<bb.r:aa.ls<bb.ls;

}

4.开始莫队，用num[x]数组统计出现x次的颜色的序号和。转移时将原先的减去，再加上现在的。

inline void add(int x)

{

	int xx=coll[x];

	if(num[xx])

	add(num[xx],-xx,1);

	num[xx]++;

	add(num[xx],xx,1);

}

inline void del(int x)

{

	int xx=coll[x];

	add(num[xx],-xx,1);

	num[xx]--;

	if(num[xx])

	add(num[xx],xx,1);

}

5.将num用线段树维护最大值。

6.查找num[x]中使num[x]！=0的x最大值，并num[x]为答案。（用线段树维护）

p.s.程序理论上时间复杂度爆了，但是经过我在考场上拍的时候没有多少数据可以卡掉，并且可以卡掉这个程序的数据第二次试的时候就不会爆，所以这个程序只要评测机高兴，就不会挂。

上代码（预警，代码中含有大量无用数组）

码长：3000B

当当当当

#pragma GCC optimize(2)

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define ll long long

using namespace std;

inline ll read()

{

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

	while(ch<'0'||ch>'9')

	{

		if(ch=='-')x=-1;ch=getchar();

	}

	while(ch>='0'&&ch<='9')f=(f<<1)+(f<<3)+ch-'0',ch=getchar();

	return f*x;

}

ll n,col[100009],siz,cnt=0,head[100009],dfn[100009],

	l[100009],r[100009],num[100009],ans=0,maxx=0,anss[100009],

	coll[100009];

struct edge

{

	ll to,nxt;

}e[200009];

struct Node

{

	ll l,r,id,bh,col,ls,rs;

}a[100009];

struct segtree

{

	ll l,r,w;

}tree[400009];

inline void adde(int a,int b)

{

	cnt++;

	e[cnt].nxt=head[a];

	e[cnt].to=b;

	head[a]=cnt;

}

inline void dfs(int x,int fa)

{

	dfn[x]=++cnt;

	l[cnt]=x;coll[cnt]=col[x];

	a[cnt].id=x;a[cnt].l=cnt;a[cnt].col=col[x];

	for(int i=head[x];~i;i=e[i].nxt){

		int v=e[i].to;

		if(v==fa)continue;

		dfs(v,x);

	}

	r[x]=cnt;

	a[dfn[x]].r=cnt;

}

inline int cmp(Node aa,Node bb)

{

	return aa.ls==bb.ls?aa.r<bb.r:aa.ls<bb.ls;

}

inline void build(int l,int r,int p)

{

	tree[p].l=l;tree[p].r=r;

	if(l==r)

	return ;

	int mid=(l+r)>>1;

	build(l,mid,p*2);build(mid+1,r,p*2+1);

}

inline void add(int x,int xx,int p)

{

	if(tree[p].l==tree[p].r)

	{

		tree[p].w+=xx;

		//printf("%d %d %d\n",tree[p].l,tree[p].r,tree[p].w);

		return ;

	}

	int mid=(tree[p].l+tree[p].r)>>1;

	if(x<=mid)add(x,xx,p*2);

	else add(x,xx,p*2+1);

	tree[p].w=tree[p*2].w+tree[p*2+1].w;

	//printf("%d %d %d %d\n",tree[p].l,tree[p].r,tree[p].w,xx);

}

inline void add(int x)

{

	int xx=coll[x];

	//ans[num[xx]]-=x;

	if(num[xx])

	add(num[xx],-xx,1);

	num[xx]++;

	add(num[xx],xx,1);

	//printf("!!!%d %d %d\n",x,xx,a[x].id);

	//ans[num[xx]]+=x

	//if(num[x]==maxx)ans+=x;

}

inline void del(int x)

{

	int xx=coll[x];

	add(num[xx],-xx,1);

	num[xx]--;

	//printf("!!!%d %d %d\n",x,xx,a[x].id);

	if(num[xx])

	add(num[xx],xx,1);

}

inline void find(int l,int r,int p)

{

	if(ans)return ;

	if(l<=tree[p].l&&r>=tree[p].r){

		int mid=(tree[p].l+tree[p].r)>>1;

		if(tree[p].l==tree[p].r){

			ans=max(ans,tree[p].w);return ;

		}

		if(tree[p*2+1].w)find(l,r,p*2+1);

		else if(tree[p*2].w)find(l,r,p*2);

		return ;

	}

	int mid=(tree[p].l+tree[p].r)>>1;

	if(r>mid)find(l,r,p*2+1);

	if(l<=mid)find(l,r,p*2);

}

int main()

{

	n=read();siz=sqrt(n);

	build(1,n,1);

	memset(head,-1,sizeof(head));

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

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

		col[i]=read();

	}

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

		int a=read(),b=read();

		adde(a,b);adde(b,a);

	}

	cnt=0;

	dfs(1,1);

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

	{

		a[i].ls=(a[i].l+siz-1)/siz;

	}

	sort(a+1,a+n+1,cmp);

	int l=1,r=0;

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

	{

		ans=0;

		while(r<a[i].r)add(++r);

		while(r>a[i].r)del(r--);

		while(l<a[i].l)del(l++);

		while(l>a[i].l)add(--l);

		find(1,n,1);

		anss[a[i].id]=ans;

		//printf("ans %d %d %d %d\n",a[i].l,a[i].r,a[i].id,ans);

	}

	for(int i=1;i<=n;i++)printf("%lld ",anss[i]);

	return 0;

}

巴特西

题解 CF600E 【Lomsat gelral】

最新文章

热门文章