[HDU6765] Count on a Tree II Striking Back

一、题目

点此看题（校内 \(\tt OJ\) 进不去别看我）

给定一棵 \(n\) 个点的树，每个点有颜色 \(c_i\)，有 \(m\) 次操作：

  • 修改某个点的颜色。
  • 给出两条链 \(a\sim b\) 和 \(c\sim d\)，询问这两条链上哪条颜色更多。

\(n\leq 10^5,m\leq 10^4\)，多组数据，强制在线，保证两条链上的颜色数量至少差一倍。

二、解法

考虑充分利用题目性质，首先本题只要求判断大小关系，其次大小关系差距很大。这告诉我们可以用一些玄学算法来模糊地描述大小关系，可以多随机几次来提高正确率。

考虑对每种颜色均匀随机一个 \([0,2^{60})\) 之间的权值，定义链的权值为链上颜色的最小权值，那么拥有更多颜色的链期望拥有更小的权值，我们可以通过权值的大小关系来判断颜色数量的大小关系。

具体来说我们用 \(30\) 个不同版本的随机数，得到权值总和更小的就判定为拥有颜色数更多。

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int M = 500005;
const int N = 32;
#define ll long long
#define zz __int128
const ll inf = (1ll<<60)-1;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int T,n,m,k,s[M][N],a[M],b[N],t[M<<2][N],id[M];
int cnt,num[M],top[M],fa[M],dep[M],siz[M],son[M];
vector g[M];
void dfs1(int u,int p)
{
	siz[u]=1;fa[u]=p;
	dep[u]=dep[p]+1;
	for(int v:g[u]) if(v^p)
	{
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>siz[son[u]]) son[u]=v;
	}
}
void dfs2(int u,int tp)
{
	top[u]=tp;num[u]=++cnt;id[cnt]=u;
	if(son[u]) dfs2(son[u],tp);
	for(int v:g[u]) if(v^fa[u] && v^son[u])
		dfs2(v,v);
}
void merge(int *a,int *b,int *c)
{
	static int r[32]={};
	for(int i=1;i<=k;i++) r[i]=min(b[i],c[i]);
	for(int i=1;i<=k;i++) a[i]=r[i];
}
void build(int i,int l,int r)
{
	if(l==r)
	{
		for(int j=1;j<=k;j++)
			t[i][j]=s[a[id[l]]][j];
		return ;
	}
	int mid=(l+r)>>1;
	build(i<<1,l,mid);
	build(i<<1|1,mid+1,r);
	merge(t[i],t[i<<1],t[i<<1|1]);
}
void ins(int i,int l,int r,int p)
{
	if(l==r)
	{
		for(int j=1;j<=k;j++)
			t[i][j]=s[a[id[l]]][j];
		return ;
	}
	int mid=(l+r)>>1;
	if(mid>=p) ins(i<<1,l,mid,p);
	else ins(i<<1|1,mid+1,r,p);
	merge(t[i],t[i<<1],t[i<<1|1]);
}
void ask(int i,int l,int r,int L,int R)
{
	if(L>r || l>R) return ;
	if(L<=l && r<=R) {merge(b,b,t[i]);return ;}
	int mid=(l+r)>>1;
	ask(i<<1,l,mid,L,R);
	ask(i<<1|1,mid+1,r,L,R);
}
zz qry(int u,int v)
{
	zz res=0;
	for(int i=1;i<=k;i++) b[i]=inf;
	while(top[u]^top[v])
	{
		if(dep[top[u]]
树-树链剖分其它-随机化数学-概率相关

相关

标签