BZOJ 3083: 遥远的国度 (树剖+线段树)

解题思路

　　前两个操作都比较基础。对于第三个操作分类讨论一下，首先如果当前根不是要操作点的子树，那么就无影响，直接查询操作点的子树即可。第二种是当前根是操作点的子树，那就找到当前根到操作点这条链的顶端(也就是操作点的儿子，这个儿子为当前根的祖先)，然后将这块连续的\(dfs\)序挖掉，查询两边就行了。找这个点的时候用倍增即可。(暴力往上跳也能过)

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

using namespace std;

const int MAXN = 100005;

inline int rd(){

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

	while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}

	while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

	return f?x:-x;

}

int n,m,head[MAXN],cnt,to[MAXN<<1],nxt[MAXN<<1],w[MAXN],wt[MAXN],rt,num,g[MAXN][20];

int siz[MAXN],fa[MAXN],son[MAXN],id[MAXN],Min[MAXN<<2],tag[MAXN<<2],top[MAXN],dep[MAXN];

inline int min(int x,int y){

	return x<y?x:y;

}

inline void add(int bg,int ed){

	to[++cnt]=ed,nxt[cnt]=head[bg],head[bg]=cnt;

}

void dfs1(int x,int f,int d){

	dep[x]=d;fa[x]=f;siz[x]=1;g[x][0]=f;

	for(int i=1;i<=18;i++) g[x][i]=g[g[x][i-1]][i-1];

	int maxson=-1,u;

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

		u=to[i];if(u==f) continue;

		dfs1(u,x,d+1);siz[x]+=siz[u];

		if(siz[u]>maxson) {maxson=siz[u];son[x]=u;}

	}

}

void dfs2(int x,int topf){

	id[x]=++num;wt[num]=w[x];

	top[x]=topf;if(!son[x]) return;

	dfs2(son[x],topf);int u;

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

		u=to[i];if(u==fa[x] || u==son[x]) continue;

		dfs2(u,u);

	}

}

void build(int x,int l,int r){

	if(l==r) {Min[x]=wt[l];return;}

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

	build(x<<1,l,mid);build(x<<1|1,mid+1,r);

	Min[x]=min(Min[x<<1],Min[x<<1|1]);

}

inline void pushdown(int x){

	Min[x<<1]=tag[x];Min[x<<1|1]=tag[x];

	tag[x<<1]=tag[x];tag[x<<1|1]=tag[x];

	tag[x]=0;

}

void update(int x,int l,int r,int L,int R,int k){

	if(L<=l && r<=R) {Min[x]=k;tag[x]=k;return;}

	int mid=(l+r)>>1;if(tag[x]) pushdown(x);

	if(L<=mid) update(x<<1,l,mid,L,R,k);

	if(mid<R)  update(x<<1|1,mid+1,r,L,R,k);

	Min[x]=min(Min[x<<1],Min[x<<1|1]);

}

int query(int x,int l,int r,int L,int R){

	if(L<=l && r<=R) return Min[x];

	int mid=(l+r)>>1,ret=0x7fffffff;if(tag[x]) pushdown(x);

	if(L<=mid) ret=min(ret,query(x<<1,l,mid,L,R));

	if(mid<R)  ret=min(ret,query(x<<1|1,mid+1,r,L,R));

	return ret;

}

inline void updRange(int x,int y,int k){

	while(top[x]!=top[y]){

		if(dep[top[x]]<dep[top[y]]) swap(x,y);

		update(1,1,n,id[top[x]],id[x],k);x=fa[top[x]];

	}

	if(dep[x]>dep[y]) swap(x,y);update(1,1,n,id[x],id[y],k);

}

inline int qRange(int x,int y){

	if(fa[x]==y) return x;

	for(int i=18;i>=0;i--){

		if(fa[g[x][i]]==y) return g[x][i];

		if(dep[fa[g[x][i]]]>dep[y]) x=g[x][i];

	}

	return x;

}

inline int qSon(int x){

	if(x==rt) return query(1,1,n,1,n);

	if(id[rt]>id[x]+siz[x]-1 || id[rt]<id[x]) return query(1,1,n,id[x],id[x]+siz[x]-1);

	int point=qRange(rt,x),ret=0x7fffffff;

	if(id[point]+siz[point]<=n) ret=min(ret,query(1,1,n,id[point]+siz[point],n));

	if(id[point]-1>=1) ret=min(ret,query(1,1,n,1,id[point]-1));return ret;

}

int main(){

	n=rd(),m=rd();int x,y,op,z;

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

		x=rd(),y=rd();

		add(x,y),add(y,x);

	}

	for(int i=1;i<=n;i++) w[i]=rd();rt=rd();

	dfs1(rt,0,1);dfs2(rt,rt);build(1,1,n);

	while(m--){

		op=rd();

		if(op==1) x=rd(),rt=x;

		if(op==2){

			x=rd(),y=rd(),z=rd();

			updRange(x,y,z);

		}

		if(op==3) {x=rd();printf("%d\n",qSon(x));}

	}

	return 0;

}

巴特西

BZOJ 3083: 遥远的国度 (树剖+线段树)

解题思路

代码

最新文章

热门文章