Codeforces 1491H - Yuezheng Ling and Dynamic Tree（分块）

Codeforces 题目传送门 & 洛谷题目传送门

*3400 的毒瘤 H 题，特意写个题解纪念一下（

首先对于这种数据结构不太好直接维护的东东可以考虑分块。然鹅我除了分块其他啥也没想到

我们设一个阈值 \(B\)，每 \(B\) 个元素分为一块。

我们知道两点之间的 LCA 的大体思想肯定是暴力跳祖先，直到两点重合为止。不过由于此题修改操作的特殊性，什么倍增、树剖都萎掉了。

于是我们考虑一个大致思路：整块暴力跳，散块直接找祖先。

具体来说，我们设 \(pre_i\) 为 \(i\) 的祖先中最大的满足 \(j\) 与 \(i\) 不在同一块中的 \(j\)。

假设我们已经维护好了 \(pre_i\)，那么找两点 \(u,v\) 之间的 LCA 这样实现：

如果 \(u,v\) 两点不在同一块，那我们就将较靠后的元素（不妨设为 \(u\)）跳到 \(pre_u\)
如果 \(u,v\) 两点在同一块，且 \(pre_u\ne pre_v\)，那我们就令 \(u=pre_u,v=pre_v\)。
如果 \(u,v\) 两点在同一块，且 \(pre_u=pre_v\)，那我们就令 \(u,v\) 的较大者（不妨设为 \(u\)）跳到其父亲为止。

正确性显然，如果你对树剖比较熟应该会理解得深刻一些。这部分复杂度 \(qB+\dfrac{qn}{B}\)。

接下来考虑修改操作，对于边角块，直接暴力修改其 \(a_i\) 值，然后对整块进行重构即可，这样最多只会重构两块，故这部分复杂度为单次询问 \(\mathcal O(B)\)。

对于整块，直接维护比较困难，不过注意到一个性质，那就是进行 \(B\) 次操作之后每个点的 \(fa\) 值都不会属于这个块，也就是说如果某个块的修改次数 \(\geq B\)，那么 \(pre_i=fa_i\)，故我们维护一个 \(cnt_i\) 表示每个块总共被改了多少次，如果 \(cnt_i\leq B\) 还是暴力重构整个块，否则打一个 \(+x\) 的标记，然后查询某个点的 \(pre\) 值时就返回 \(\max(1,pre_i-tag_i)\)，其中 \(tag_i\) 为 \(i\) 所在的块打的标记大小。这部分复杂度为 \(B·\dfrac{n}{B}·B=nB\)

根据均值不等式可知 \(B=\sqrt{n}\) 时最优，总复杂度 \(n\sqrt{n}+q\sqrt{n}\)。

还有一些细节需注意，具体见代码罢：

#include <bits/stdc++.h>

using namespace std;

#define fi first

#define se second

#define fill0(a) memset(a,0,sizeof(a))

#define fill1(a) memset(a,-1,sizeof(a))

#define fillbig(a) memset(a,63,sizeof(a))

#define pb push_back

#define ppb pop_back

#define mp make_pair

template<typename T1,typename T2> void chkmin(T1 &x,T2 y){if(x>y) x=y;}

template<typename T1,typename T2> void chkmax(T1 &x,T2 y){if(x<y) x=y;}

typedef pair<int,int> pii;

typedef long long ll;

typedef unsigned int u32;

typedef unsigned long long u64;

namespace fastio{

	#define FILE_SIZE 1<<23

	char rbuf[FILE_SIZE],*p1=rbuf,*p2=rbuf,wbuf[FILE_SIZE],*p3=wbuf;

	inline char getc(){return p1==p2&&(p2=(p1=rbuf)+fread(rbuf,1,FILE_SIZE,stdin),p1==p2)?-1:*p1++;}

	inline void putc(char x){(*p3++=x);}

	template<typename T> void read(T &x){

		x=0;char c=getchar();T neg=0;

		while(!isdigit(c)) neg|=!(c^'-'),c=getchar();

		while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();

		if(neg) x=(~x)+1;

	}

	template<typename T> void recursive_print(T x){if(!x) return;recursive_print(x/10);putc(x%10^48);}

	template<typename T> void print(T x){if(!x) putc('0');if(x<0) putc('-'),x=~x+1;recursive_print(x);}

	void print_final(){fwrite(wbuf,1,p3-wbuf,stdout);}

}

const int MAXN=1e5;

const int SQRT=316;

int n,qu,fa[MAXN+5],pre[MAXN+5];

int blk_sz,blk,L[SQRT+5],R[SQRT+5],bel[MAXN+5];

int tag[SQRT+5],sum[SQRT+5];

void update(int x){

	for(int i=L[x];i<=R[x];i++) fa[i]=max(1,fa[i]-tag[x]);

	tag[x]=0;

	for(int i=L[x];i<=R[x];i++){

		if(fa[i]<L[x]) pre[i]=fa[i];

		else pre[i]=pre[fa[i]];

	}

}

int getpre(int x){return max(pre[x]-tag[bel[x]],1);}

int getfa(int x){return max(fa[x]-tag[bel[x]],1);}

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

	if(bel[l]==bel[r]){

		for(int i=l;i<=r;i++) fa[i]=max(1,fa[i]-x);

		update(bel[l]);return;

	}

	for(int i=l;i<=R[bel[l]];i++) fa[i]=max(1,fa[i]-x);

	for(int i=L[bel[r]];i<=r;i++) fa[i]=max(1,fa[i]-x);

	update(bel[l]);update(bel[r]);

	for(int i=bel[l]+1;i<=bel[r]-1;i++){

		tag[i]=min(n,tag[i]+x);sum[i]++;

		if(sum[i]<=R[i]-L[i]+1) update(i);

	}

}

int getlca(int u,int v){

	while(u!=v){

		if(bel[u]<bel[v]) swap(u,v);

		if(bel[u]>bel[v]) u=getpre(u);

		else{

			if(getpre(u)==getpre(v)){

				while(u!=v){

					if(u<v) swap(u,v);

					u=getfa(u);

				}

			} else {

				u=getpre(u);v=getpre(v);

			}

		}

	} return u;

}

int main(){

	scanf("%d%d",&n,&qu);blk_sz=(int)pow(n,0.5);blk=(n-1)/blk_sz+1;

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

		L[i]=(i-1)*blk_sz+1;R[i]=min(i*blk_sz,n);

		for(int j=L[i];j<=R[i];j++) bel[j]=i;

	}

	for(int i=2;i<=n;i++) scanf("%d",&fa[i]);

	for(int i=1;i<=blk;i++) update(i);

	while(qu--){

		int opt;scanf("%d",&opt);

		if(opt==1){int l,r,x;scanf("%d%d%d",&l,&r,&x);modify(l,r,x);}

		else{int u,v;scanf("%d%d",&u,&v);printf("%d\n",getlca(u,v));}

	}

	return 0;

}

巴特西

Codeforces 1491H - Yuezheng Ling and Dynamic Tree（分块）

最新文章

热门文章