\(\mathcal{Description}\)

Link. 做题原因：题目名。

给定一个长度 \(n-1\) 的序列 \(\{a_2,a_3,\cdots,a_n\}\)，其描述了一棵 \(n\) 个点的有根树—— \(1\) 为根节点，\(i~(i\in(1,n])\) 结点的父亲是 \(a_i~(a_i\in[1,i))\)。接下来有 \(q\) 次操作：

给定 \(l,r,x\)，\(\forall i\in[l,r],~a_i\leftarrow \max\{a_i-x,1\}\)；
给定 \(u,v\)，求 \(u,v\) 在当前树上的 LCA。

\(n,q\le10^5\)。

\(\mathcal{Solution}\)

树是阿绫给的，操作是天依说的，所以题是一定会做的。

首先明确一点：这是到题如其名的树题还是一道序列题。

鉴于随便修改几下就可以把树拍得面目全非，前者可以叉掉，这就是道序列题。

接着，思考 LCA 维护的形式，倍增太离谱了，考虑类似树剖维护 top 的方法——我们并不需要让 top 做到如树剖那样 \(\log\) 级别的优秀，这样才能应对灵活的修改。

唠半天啦，这道题就是一道分块维护序列的题。

首先根号分块，定义一个关键的 \(\operatorname{top}(u)\) 表示当前树上 \(u\) 的祖先中，不与 \(u\) 在同一块中的编号最大的结点，若不存在，则 \(\operatorname{top}(u)=1\)。发现美妙性质：跳 \(\operatorname{top}\) 链是 \(\mathcal O(\sqrt n)\) 的，收束前文提到的树剖思想；且暴力计算 \(\operatorname{top}(u)\) 是 \(\mathcal O(n)\) 的，非常方便。接了来只需要尝试维护这一信息。

对于修改，散点暴力扫即可（注意一定是从左到右更新）。对于整块，我们似乎还是需要 \(\mathcal O(\sqrt n)\) 去重新更新 \(\operatorname{top}\)？

答案是肯定的，但不完全——若一个整块被修改次数超过块的大小，则必然有 \(\operatorname{top}(u)=a_u\)。表明我们确实需要对于 \(\mathcal O(\sqrt n)\) 个块中的每一个，以 \(\mathcal O(\sqrt n)\) 的时间暴力处理其前 \(\operatorname O(\sqrt n)\) 次修改，不多不少，\(\mathcal O(n\sqrt n)\)，此后直接对于整块记录减法标记即可。

对于询问，亦类似树剖求 LCA：

若 \(u,v\) 不属于同一块，\(u\leftarrow \operatorname{top}(u),v\leftarrow\operatorname{top}(v)\)；
否则若 \(\operatorname{top}(u)\not=\operatorname{top}(v)\)，令 \(\operatorname{top}\) 较大的结点为其 \(\operatorname{top}\)；
否则，令较深结点为其父亲。

跳 \(\operatorname{top}\) 至多 \(\mathcal O(\sqrt n)\) 下；跳父亲只会在同块时跳 \(\mathcal O(\sqrt n)\) 次（然后必然结束询问），所以单次查询是 \(\mathcal O(\sqrt n)\) 的。

综上，复杂度 \(\mathcal O((n+q)\sqrt n)\)，让天依满意啦~

\(\mathcal{Code}\)

/* Clearink */

#include <cmath>

#include <cstdio>

#define rep( i, l, r ) for ( int i = l, repEnd##i = r; i <= repEnd##i; ++i )

#define per( i, r, l ) for ( int i = r, repEnd##i = l; i >= repEnd##i; --i )

inline int rint() {

	int x = 0, f = 1, s = getchar();

	for ( ; s < '0' || '9' < s; s = getchar() ) f = s == '-' ? -f : f;

	for ( ; '0' <= s && s <= '9'; s = getchar() ) x = x * 10 + ( s ^ '0' );

	return x * f;

}

template<typename Tp>

inline void wint( Tp x ) {

	if ( x < 0 ) putchar( '-' ), x = -x;

	if ( 9 < x ) wint( x / 10 );

	putchar( x % 10 ^ '0' );

}

inline int imin( const int a, const int b ) { return a < b ? a : b; }

inline int imax( const int a, const int b ) { return a < b ? b : a; }

const int MAXN = 1e5, MAXSN = 317;

int n, q, par[MAXN + 5];

int bsiz, bel[MAXN + 5], top[MAXN + 5], mcnt[MAXSN + 5], tag[MAXSN + 5];

#define utop( i ) ( top[i] = bel[par[i]] != bel[i] ? par[i] : top[par[i]] )

#define gpar( i ) ( pushdn( bel[i] ), par[i] )

#define gtop( i ) ( mcnt[bel[i]] >= bsiz ? pushdn( bel[i] ), par[i] : top[i] )

inline void init() {

	bsiz = sqrt( 1. * n ), bel[1] = 1, bel[n + 1] = -1;

	rep ( i, 2, n ) bel[i] = ( i - 1 ) / bsiz + 1, utop( i );

}

inline void pushdn( const int i ) {

	if ( !tag[i] ) return ;

	int bl = ( i - 1 ) * bsiz + 1, br = imin( i * bsiz, n );

	rep ( j, bl, br ) par[j] = imax( par[j] - tag[i], 1 );

	// top[] is meaningless for this block.

	tag[i] = 0;

}

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

	pushdn( bel[l] );

	for ( int i = l; bel[i] == bel[l]; ++i ) {

		if ( i <= r ) par[i] = imax( par[i] - x, 1 );

		utop( i );

	}

	if ( bel[l] == bel[r] ) return ;

	rep ( i, bel[l] + 1, bel[r] - 1 ) {

		if ( mcnt[i] >= bsiz ) { tag[i] += x; continue; }

		++mcnt[i];

		int bl = ( i - 1 ) * bsiz + 1, br = imin( i * bsiz, n );

		rep ( j, bl, br ) par[j] = imax( par[j] - x, 1 ), utop( j );

	}

	pushdn( bel[r] );

	for ( int i = ( bel[r] - 1 ) * bsiz + 1; bel[i] == bel[r]; ++i ) {

		if ( i <= r ) par[i] = imax( par[i] - x, 1 );

		utop( i );

	}

}

inline int query( int u, int v ) {

	while ( u != v ) {

		int tu = gtop( u ), tv = gtop( v );

		if ( bel[u] != bel[v] ) bel[u] > bel[v] ? u = tu : v = tv;

		else if ( tu != tv ) u = tu, v = tv;

		else u > v ? u = gpar( u ) : v = gpar( v );

	}

	return u;

}

int main() {

	n = rint(), q = rint(), par[1] = 1;

	rep ( i, 2, n ) par[i] = rint();

	init();

	for ( int op, u, v; q--; ) {

		op = rint(), u = rint(), v = rint();

		if ( op & 1 ) modify( u, v, rint() );

		else wint( query( u, v ) ), putchar( '\n' );

	}

	return 0;

}

巴特西

Solution -「CF 1491H」Yuezheng Ling and Dynamic Tree

\(\mathcal{Description}\)

\(\mathcal{Solution}\)

\(\mathcal{Code}\)

最新文章

热门文章