首页 > 代码库 > 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]森林
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。