jzoj4918. 【GDOI2017模拟12.9】最近公共祖先（树链剖分+线段树）

题面

题解

首先，点变黑的过程是不可逆的，黑化了就再也洗不白了

其次，对于\(v\)的祖先\(rt\)，\(rt\)能用来更新答案当且仅当\(sz_{rt}>sz_{x}\)，其中\(sz\)表示子树中黑点的个数，\(x\)表示\(rt\)走到\(v\)的路径上的第二个节点

每一次染黑一个新的点\(u\)之后，我们要让它所有祖先的\(sz+1\)，那么我们可以考虑树链剖分+线段树

再回过头来康康树链剖分的过程啊……我们跳着跳着跳到了\(u\)，那么对于\([top[u],u]\)之间的点的\(sz\)全都要\(+1\)，所以每一次都是重链的\(top\)到下面某个节点区间加……

那么这么说来这次之后\(son[u]\)的\(sz\)不是绝对小于\(u\)的\(sz\)了么？！

然后我们惊喜的发现，如果有一个点\(v\)从下面往上找根节点的时候既经过\(son[u]\)又经过\(u\)，\(u\)节点就可以用来更新答案了！

那么我们每一次染黑节点跳树剖的时候，每一次跳到一个\(u\)，就把\(top[u]\)到\(u\)的区间的\(sz\)区间加。我们顺便在线段树上记一个\(mx\)表示区间最大值，一开始所有节点的\(mx\)都是\(-1\)，每一次都把\(u\)节点对应的值单点修改成它自己的值。那么查询的时候只要在跳树剖查询\([top[u],fa[u]]\)这个区间的\(mx\)就行了

然而如果父亲与儿子是在不同的重链中该怎么办呢？直接单点查询两个点的\(sz\)然后暴力判断就行了

复杂度\(O(n\log^2n)\)

//minamoto

#include<bits/stdc++.h>

#define R register

#define ls (p<<1)

#define rs (p<<1|1)

#define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)

#define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i)

#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)

template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}

using namespace std;

char buf[1<<21],*p1=buf,*p2=buf;

inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}

int read(){

    R int res,f=1;R char ch;

    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);

    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');

    return res*f;

}

inline char getop(){R char ch;while((ch=getc())!='M'&&ch!='Q');return ch;}

char sr[1<<21],z[20];int C=-1,Z=0;

inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}

void print(R int x){

    if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;

    while(z[++Z]=x%10+48,x/=10);

    while(sr[++C]=z[Z],--Z);sr[++C]='\n';

}

const int N=2e5+5;

struct eg{int v,nx;}e[N<<1];int head[N],tot;

inline void add(R int u,R int v){e[++tot]={v,head[u]},head[u]=tot;}

int top[N],dfn[N],sz[N],son[N],fa[N],rk[N],a[N],ok[N],dep[N];

int vis[N<<2],mx[N<<2],tag[N<<2],val[N<<2];

int n,m,res,cnt,x,y,u,v;char ch;

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

	val[p]=mx[p]=-1;

	if(l==r)return mx[p]=rk[l],void();

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

	build(ls,l,mid),build(rs,mid+1,r);

	mx[p]=max(mx[ls],mx[rs]);

}

void change(int p,int l,int r,int x){

	if(vis[p])return;if(l==r)return vis[p]=1,val[p]=mx[p],void();

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

	x<=mid?change(ls,l,mid,x):change(rs,mid+1,r,x);

	val[p]=max(val[ls],val[rs]),vis[p]=vis[ls]&vis[rs];

}

void update(int p,int l,int r,int ql,int qr){

	if(ql<=l&&qr>=r)return ++tag[p],void();

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

	if(ql<=mid)update(ls,l,mid,ql,qr);

	if(qr>mid)update(rs,mid+1,r,ql,qr);

}

void qmax(int p,int l,int r,int ql,int qr){

	if(ql<=l&&qr>=r)return cmax(res,val[p]),void();

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

	if(ql<=mid)qmax(ls,l,mid,ql,qr);

	if(qr>mid)qmax(rs,mid+1,r,ql,qr);

}

int query(int p,int l,int r,int x,int t){

	if(l==r)return t+tag[p];

	int mid=(l+r)>>1;t+=tag[p];

	return x<=mid?query(ls,l,mid,x,t):query(rs,mid+1,r,x,t);

}

void dfs1(int u){

	sz[u]=1,dep[u]=dep[fa[u]]+1;

	go(u)if(v!=fa[u]){

		fa[v]=u,dfs1(v),sz[u]+=sz[v];

		sz[v]>sz[son[u]]?son[u]=v:0;

	}

}

void dfs2(int u,int t){

	top[u]=t,dfn[u]=++cnt,rk[cnt]=a[u];

	if(!son[u])return;

	dfs2(son[u],t);

	go(u)if(!top[v])dfs2(v,v);

}

void qwq(int u){

	res=-1;

	x=query(1,1,n,dfn[u],0);

	x?res=a[u]:0;

	while(u){

		if(u!=top[u])qmax(1,1,n,dfn[top[u]],dfn[fa[u]]);

		x=query(1,1,n,dfn[top[u]],0);

		y=query(1,1,n,dfn[fa[top[u]]],0);

		y>x?cmax(res,a[fa[top[u]]]):0;

		u=fa[top[u]];

	}

	print(res);

}

void mdzz(int u){

	if(ok[u])return;

	ok[u]=1;

	while(u){

		update(1,1,n,dfn[top[u]],dfn[u]);

		change(1,1,n,dfn[u]);

		u=fa[top[u]];

	}

}

int main(){

	freopen("lca.in","r",stdin);

	freopen("lca.out","w",stdout);

	n=read(),m=read();

	fp(i,1,n)a[i]=read();

	fp(i,1,n-1)u=read(),v=read(),add(u,v),add(v,u);

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

	while(m--){

		ch=getop(),u=read();

		ch=='M'?mdzz(u):qwq(u);

	}

	return Ot(),0;

}

巴特西

jzoj4918. 【GDOI2017模拟12.9】最近公共祖先（树链剖分+线段树）

题面

题解

最新文章

热门文章

巴特西

jzoj4918. 【GDOI2017模拟12.9】最近公共祖先 （树链剖分+线段树）

题面

题解

最新文章

热门文章

jzoj4918. 【GDOI2017模拟12.9】最近公共祖先（树链剖分+线段树）