树分块小结

其实就是一个简单的trick。网上我只找到了两道例题。

P6177 Count on a tree II/【模板】树分块

P3603 雪辉

说句闲话:我因为一个傻逼错误第一题从9:00调到11:45吃饭,12:00THUPC初赛。于是我非常困地开始了比赛,罚了我们队200min而且0输出。希望队友原谅我吧/kel

P6177 Count on a tree II/【模板】树分块

直接放题吧。强制在线树上路径数颜色。

我们考虑往树上撒关键点点。随机撒 \(\sqrt n\) 个期望是对的,但是有确定性做法(Orz mrsrz):

如果一个点往上 \(S\) 个点都没有关键点,那么这个点就标记成关键点。

显然一个点标记之后至少 \(S\) 个点不会被标记,那么总点数是 \(\dfrac{n}{S}\) 级别的。

如果直接这样实现是 \(O(nS)\) 的,虽然没啥问题,可是其实是可以 \(O(n)\) 的。

我们把这个东西转化成:对于一个点 \(u\) ,如果存在一条从 \(u\) 往下的路径,长度 \(> S\) ,那么 \(u\) 就是关键点。

这样我们维护每一个点往下的最长非关键点路径长度即可。

接下去我们维护任意两个关键点间的信息。比如这题可以直接用 bitset ,把颜色离散化后开到值域上。

如果我们暴力把 \(\dfrac{n}{S}\) 个点拿出来dfs一遍就是 \(\dfrac{n^2}{S}\times \dfrac{n}{\omega}\) 的了。

但是有 \(O(\dfrac{n^2}{S^2}\times\dfrac{n}{\omega}+\dfrac{n^2}{S})\) 的做法:

对于每一个关键点记录它上方的关键点是什么,先 \(O(S)\) 跳出相邻关键点间的信息,然后暴力往上跳关键点,bitset 的话直接或起来就好了。

总共不会超过 \((\dfrac{n}{S})^2\) 对点,所以复杂度就是上面那玩意。

这些信息我们都预处理掉就可以快速处理询问了。

设我们询问 \(x,y\) 间的颜色数, \(lca\) 是 \(x,y\) 的最近公共祖先。

那么可以把路径拆成 \(6\) 段:

\(x\) 到 \(x\) 上方第一个关键点 \(x'\); \(x'\) 到 \(lca\) 下方最高在 \(x\to lca\) 路径上最高的的关键点 \(x''\) ;\(x''\) 到 \(lca\)
\(y\) 到 \(y\) 上方第一个关键点 \(y'\); \(y'\) 到 \(lca\) 下方最高在 \(y\to lca\) 路径上最高的的关键点 \(y''\) ;\(y''\) 到 \(lca\)

颜色全部或起来就好了。

可以发现左右两边的 \(4\) 条都是 \(O(S)\) 的,中间两条是 \(O(\dfrac{n}{\omega}+\dfrac{n}{S})\) ,而且大多都跑不满。

这题完结了。

不过值得一提,这东西的时空复杂度都有点鬼畜,这里不建议直接把 \(S\) 当成 \(\sqrt n\) ,这个参数活动性很大。

根据上面的分析,时间复杂度上限是 \(O(\dfrac{n^2}{S}+\dfrac{n^3}{S^2\omega}+\dfrac{nm}{\omega}+\dfrac{nm}{S}+mS)\),空间复杂度是 \(O(\dfrac{n^3}{S^2\omega})\),但是如果这棵树长得并不那么像链是严重不满的,这东西大概在序列上才会被卡满。

可见这东西复杂度并不友善,各方面都要平衡到。所以这东西是不是没啥用啊

不过显然的一点,\(\color{black}{\texttt{F}}\color{red}{\texttt{ever_Pursuit}}\) 说分块都是这样的,\(S\) 线性增加,空间平方减少。所以空间一定要算过,块长一般尽量开小(因为实现的时候时间复杂度里那个 \(mS\) 是暴力往上找最高大关键点产生的,常数很小,而且显然 \(\dfrac{n^3}{\omega S^2}\) 最容易成为瓶颈)

一个显著的空间优化

如果预处理bitset的时候合并这么写:bs[x][y]=bs[x][z]|bs[z][y] ,会MLE成*。

但是这么写就没事:(bs[x][y]=bs[x][z])|=bs[z][y]

因为上面那种写法会新开一个bitset,很费空间,申请空间也很费时间。

//Orz cyn2006
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mkp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define sz(v) (int)v.size()
typedef long long LL;
typedef double db;
template<class T>bool ckmax(T&x,T y){return x<y?x=y,1:0;}
template<class T>bool ckmin(T&x,T y){return x>y?x=y,1:0;}
#define rep(i,x,y) for(int i=x,i##end=y;i<=i##end;++i)
#define per(i,x,y) for(int i=x,i##end=y;i>=i##end;--i)
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=0;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return f?x:-x;
}
const int N=40005;
const int S=800;
int n,m,lsh[N],len,a[N],lastans;
int top[N],fa[N],dep[N],siz[N],son[N];
int id[N],tot,mxd[N],up[N];
bitset<N>bs[N/S+5][N/S+5];
int hed[N],et;
struct edge{int nx,to;}e[N<<1];
void adde(int u,int v){e[++et].nx=hed[u],e[et].to=v,hed[u]=et;}
void dfs1(int u,int ft){
	siz[u]=1,mxd[u]=dep[u];
	for(int i=hed[u];i;i=e[i].nx){
		int v=e[i].to;if(v==ft)continue;
		dep[v]=dep[u]+1,dfs1(v,u),siz[u]+=siz[v],fa[v]=u;
		ckmax(mxd[u],mxd[v]);
		if(siz[v]>siz[son[u]])son[u]=v;
	}
	if(u==1||mxd[u]-dep[u]>S)mxd[u]=dep[u],id[u]=++tot;
}
void dfs2(int u,int tp){
	top[u]=tp;
	if(son[u])dfs2(son[u],tp);
	for(int i=hed[u];i;i=e[i].nx){
		int v=e[i].to;if(v==fa[u]||v==son[u])continue;
		dfs2(v,v);
	}
}
void dfs(int u,int ft,int lst){
	for(int i=hed[u];i;i=e[i].nx){
		int v=e[i].to;if(v==ft)continue;
		if(id[u]){
			up[u]=lst,bs[id[u]][id[u]].set(a[u]);
			int now=u;
			while(now!=fa[lst])bs[id[u]][id[lst]].set(a[now]),now=fa[now];
			now=up[lst];
			while(now)(bs[id[u]][id[now]]|=bs[id[u]][id[lst]])|=bs[id[lst]][id[now]],now=up[now];
			dfs(v,u,u);
		}else dfs(v,u,lst);
	}
}
int LCA(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])x^=y^=x^=y;
		x=fa[top[x]];
	}
	return dep[x]<dep[y]?x:y;
}
signed main(){
	n=read(),m=read();
	rep(i,1,n)a[i]=lsh[++len]=read();
	sort(lsh+1,lsh+len+1),len=unique(lsh+1,lsh+len+1)-lsh-1;
	rep(i,1,n)a[i]=lower_bound(lsh+1,lsh+len+1,a[i])-lsh;
	rep(i,2,n){
		int x=read(),y=read();
		adde(x,y),adde(y,x);
	}
	dep[1]=1,dfs1(1,0),dfs2(1,1),dfs(1,0,0);
	while(m--){
		static bitset<N>ans;
		int x=read()^lastans,y=read(),lca=LCA(x,y);
		ans.reset(),ans.set(a[lca]);
		while(!id[x]&&x!=lca)ans.set(a[x]),x=fa[x];
		while(!id[y]&&y!=lca)ans.set(a[y]),y=fa[y];
		if(x!=lca){
			int now=x;
			while(up[now]&&dep[up[now]]>dep[lca])now=up[now];
			ans|=bs[id[x]][id[now]];
			while(now!=lca)ans.set(a[now]),now=fa[now]; 
		}
		if(y!=lca){
			int now=y;
			while(up[now]&&dep[up[now]]>dep[lca])now=up[now];
			ans|=bs[id[y]][id[now]];
			while(now!=lca)ans.set(a[now]),now=fa[now];
		}
		printf("%d\n",lastans=ans.count());
	}
}

P3603 雪辉

有了上一题,这题应该非常基础了。

链上数颜色和上一题一样搞,链并就把bitset或起来。

求mex手写一个bitset就好了

//Orz cyn2006
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mkp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define sz(v) (int)v.size()
typedef long long LL;
typedef double db;
template<class T>bool ckmax(T&x,T y){return x<y?x=y,1:0;}
template<class T>bool ckmin(T&x,T y){return x>y?x=y,1:0;}
#define rep(i,x,y) for(int i=x,i##end=y;i<=i##end;++i)
#define per(i,x,y) for(int i=x,i##end=y;i>=i##end;--i)
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=0;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return f?x:-x;
}
const int N=100005;
const int M=30005;
const int S=600;
template<int N>struct Bitset{

typedef unsigned long long ull;
static const int O=(N-1)/64+1;
static const ull ULL_MAX=18446744073709551615ull;
ull a[O];
Bitset(){memset(a,0,sizeof(a));}
void reset(){memset(a,0,sizeof(a));}
void set(int x){a[(x>>6)]|=1ull<<(x&63);}
Bitset&operator |= (const Bitset&t){
	for(int i=0;i<O;++i)a[i]|=t.a[i];
	return *this;
}
Bitset operator | (const Bitset&t){
	Bitset res;
	for(int i=0;i<O;++i)res.a[i]=a[i]|t.a[i];
	return res;
}
int count(){
	int res=0;
	for(int i=0;i<O;++i)res+=__builtin_popcountll(a[i]);
	return res;
}
int mex(){
	for(int i=0;i<O;++i)if(a[i]<ULL_MAX)
		for(int j=0;j<64;++j)if(!(a[i]>>j&1ull))return (i<<6)|j;
	return N+1;
}

};
Bitset<M>bs[N/S+5][N/S+5];
int n,m,f,lastans,a[N];
int siz[N],fa[N],top[N],son[N],dep[N],mxd[N];
int id[N],tot,up[N];
int et,hed[N];
struct edge{int nx,to;}e[N<<1]; 
void adde(int u,int v){e[++et].nx=hed[u],e[et].to=v,hed[u]=et;}
void dfs1(int u,int ft){
	mxd[u]=dep[u],siz[u]=1;
	for(int i=hed[u];i;i=e[i].nx){
		int v=e[i].to;if(v==ft)continue;
		dep[v]=dep[u]+1,dfs1(v,u);
		fa[v]=u,siz[u]+=siz[v];
		ckmax(mxd[u],mxd[v]);
		if(siz[v]>siz[son[u]])son[u]=v;
	}
	if(u==1||mxd[u]-dep[u]>S)id[u]=++tot,mxd[u]=dep[u];
}
void dfs2(int u,int tp){
	top[u]=tp;
	if(son[u])dfs2(son[u],tp);
	for(int i=hed[u];i;i=e[i].nx){
		int v=e[i].to;
		if(v==fa[u]||v==son[u])continue;
		dfs2(v,v);
	}
}
void dfs(int u,int ft,int lst){
	for(int i=hed[u];i;i=e[i].nx){
		int v=e[i].to;if(v==ft)continue;
		if(id[u]){
			up[u]=lst,bs[id[u]][id[u]].set(a[u]);
			if(lst){
				int now=u;
				while(now!=lst)bs[id[u]][id[lst]].set(a[now]),now=fa[now];
				now=up[lst];
				while(now)(bs[id[u]][id[now]]=bs[id[u]][id[lst]])|=bs[id[lst]][id[now]],now=up[now];
			}
			dfs(v,u,u);
		}else dfs(v,u,lst);
	}
}
int LCA(int x,int y){
	while(top[x]!=top[y])dep[top[x]]>dep[top[y]]?x=fa[top[x]]:y=fa[top[y]];
	return dep[x]<dep[y]?x:y;
}
signed main(){
	n=read(),m=read(),f=read();
	rep(i,1,n)a[i]=read();
	rep(i,2,n){
		int x=read(),y=read();
		adde(x,y),adde(y,x);
	}
	dep[1]=1,dfs1(1,0),dfs2(1,1),dfs(1,0,0);
	while(m--){
		int q=read(),mex,sum;
		static Bitset<M>ans;
		ans.reset();
		rep(i,1,q){
			int x=read(),y=read();
			if(f)x^=lastans,y^=lastans;
			int lca=LCA(x,y);
			ans.set(a[lca]);
			while(!id[x]&&x!=lca)ans.set(a[x]),x=fa[x];
			while(!id[y]&&y!=lca)ans.set(a[y]),y=fa[y];
			if(x!=lca){
				int now=x;
				while(dep[up[now]]>=dep[lca])now=up[now];
				ans|=bs[id[x]][id[now]];
				while(now!=lca)ans.set(a[now]),now=fa[now];
			}
			if(y!=lca){
				int now=y;
				while(dep[up[now]]>=dep[lca])now=up[now];
				ans|=bs[id[y]][id[now]];
				while(now!=lca)ans.set(a[now]),now=fa[now];
			}
		}
		lastans=(sum=ans.count())+(mex=ans.mex()),printf("%d %d\n",sum,mex); 
	}
}
上一篇:SpringBoot之旅第六篇-启动原理及自定义starter


下一篇:P4281 [AHOI2008]紧急集合 / 聚会