首页 > 代码库 > bzoj3123: [Sdoi2013]森林

bzoj3123: [Sdoi2013]森林

题面传送门


 

复出的第一道题.. md就遇到坑了..

简单来说就是可持久化线段树+启发式合并啊..

感觉启发式合并好神奇好想学

每一次建边就暴力合并,每一个节点维护从根到它的权值线段树

按照题面的话最省空间的做法就是垃圾回收,但是实在是太慢了..

而且这题有坑,题面说的是多组数据其实只有一组 而且是$T>1$的一组..

 

然后看给了512MB就不需要垃圾回收,而且很多预处理都tm不用了呢!wqnmdsy

 

#include <cstdio>#include <cstring>#include <cstdlib>#include <algorithm>using namespace std;const int Maxn = 80010;const int lg = 18;struct node {	int y, next;}a[Maxn*2]; int first[Maxn], len;void ins ( int x, int y ){	len ++;	a[len].y = y;	a[len].next = first[x]; first[x] = len;}int n, m, t;int sum[Maxn*lg*lg], lc[Maxn*lg*lg], rc[Maxn*lg*lg], tot;int rt[Maxn];int na[Maxn], b[Maxn], bl;int fa[Maxn][lg], dep[Maxn];int faa[Maxn], gs[Maxn];int ff ( int x ){	if ( faa[x] == x ) return x;	return faa[x] = ff (faa[x]);}void merge ( int &now, int fnow, int l, int r, int x ){	if ( !now ) now = ++tot;	sum[now] = sum[fnow]+1;	if ( l == r ) return;	int mid = ( l + r ) >> 1;	if ( x <= mid ) merge ( lc[now], lc[fnow], l, mid, x ), rc[now] = rc[fnow];	else merge ( rc[now], rc[fnow], mid+1, r, x ), lc[now] = lc[fnow];}void dfs1 ( int x, int f ){	rt[x] = 0;	merge ( rt[x], rt[fa[x][0]], 1, bl, na[x] );	for ( int i = 1; i <= 17; i ++ ) fa[x][i] = fa[fa[x][i-1]][i-1];	for ( int k = first[x]; k; k = a[k].next ){		int y = a[k].y;		if ( y == f ) continue;		fa[y][0] = x; dep[y] = dep[x]+1;		dfs1 ( y, x );	}}void change ( int &now, int l, int r, int x ){	if ( !now ) now = ++tot;	sum[now] ++;	if ( l == r ) return;	int mid = ( l + r ) >> 1;	if ( x <= mid ) change ( lc[now], l, mid, x );	else change ( rc[now], mid+1, r, x );}int getlca ( int x, int y ){	if ( dep[x] < dep[y] ) swap ( x, y );	for ( int i = 17; i >= 0; i -- ){		if ( dep[fa[x][i]] >= dep[y] ){			x = fa[x][i];		}	}	if ( x == y ) return x;	for ( int i = 17; i >= 0; i -- ){		if ( fa[x][i] != fa[y][i] ){			x = fa[x][i]; y = fa[y][i];		}	}	return fa[x][0];}int getrank ( int now1, int now2, int now3, int p, int l, int r, int k ){	if ( l == r ) return b[l];	int mid = ( l + r ) >> 1;	int ls = sum[lc[now1]]+sum[lc[now2]]-2*sum[lc[now3]];	if ( na[p] <= mid && na[p] >= l ) ls --;	if ( ls >= k ) return getrank ( lc[now1], lc[now2], lc[now3], p, l, mid, k );	else return getrank ( rc[now1], rc[now2], rc[now3], p, mid+1, r, k-ls );}void read ( int &x ){	char c = getchar ();	for ( ; c > ‘9‘ || c < ‘0‘; c = getchar () );	x = 0;	for ( ; c <= ‘9‘ && c >= ‘0‘; c = getchar () ) x = x*10+c-‘0‘;}int main (){	int i, j, k, T;	read (T);	tot = 0;	while ( T -- ){		len = 0; memset ( first, 0, sizeof (first) );		read (n); read (m); read (t);		for ( i = 1; i <= n; i ++ ) rt[i] = 0, faa[i] = i, gs[i] = 1, dep[i] = 1;		for ( i = 1; i <= n; i ++ ){			read (na[i]);			b[i] = na[i];		}		sort ( b+1, b+n+1 );		bl = unique ( b+1, b+n+1 ) - (b+1);		for ( i = 1; i <= n; i ++ ){			na[i] = lower_bound ( b+1, b+bl+1, na[i] ) - b;			change ( rt[i], 1, bl, na[i] );		}		for ( i = 1; i <= m; i ++ ){			int x, y;			read (x); read (y);			int fx = ff (x), fy = ff (y);			if ( gs[fx] > gs[fy] ) swap ( x, y );			faa[fx] = fy; gs[fy] += gs[fx];			fa[x][0] = y; dep[x] = dep[y]+1;			dfs1 ( x, y );			ins ( x, y ); ins ( y, x );		}		char c;		int lastans = 0;		while ( t -- ){			c = getchar ();			for ( ; c > ‘Z‘ || c < ‘A‘; c = getchar () );			if ( c == ‘Q‘ ){				int x, y;				read (x); read (y); read (k);				x ^= lastans; y ^= lastans; k ^= lastans;				int lca = getlca ( x, y );				lastans = getrank ( rt[x], rt[y], rt[fa[lca][0]], lca, 1, bl, k );				printf ( "%d\n", lastans );			}			else {				int x, y;				read (x); read (y);				x ^= lastans; y ^= lastans;				int fx = ff (x), fy = ff (y);				if ( gs[fx] > gs[fy] ) swap ( x, y );				faa[fx] = fy; gs[fy] += gs[fx];				fa[x][0] = y; dep[x] = dep[y]+1;				dfs1 ( x, y );				ins ( x, y ); ins ( y, x );			}		}		break;	}	return 0;}

  

bzoj3123: [Sdoi2013]森林