【UVALive】5031 Graph and Queries treap实现名次树

传送门：【UVALive】5031 Graph and Queries

题目分析：第一道treap~yeah

代码如下：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std ;

#define REP( i , a , b ) for ( int i = a ; i < b ; ++ i )
#define FOR( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REV( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define CLR( a , x ) memset ( a , x , sizeof a )

typedef long long LL ;

const int MAXN = 20005 ;
const int MAXL = 60005 ;
const int MAXC = 500005 ;

struct Node {
	Node *ch[2] ;
	int r ;
	int v ;
	int s ;
	
	Node ( int v = 0 ) : v ( v ) {
		ch[0] = ch[1] = NULL ;
		r = rand () ;
		s = 1 ;
	}
	
	int cmp ( int x ) {
		return x == v ? -1 : ( x < v ? 0 : 1 ) ;
	}
	
	void maintain () {
		s = 1 ;
		if ( ch[0] != NULL )
			s += ch[0] -> s ;
		if ( ch[1] != NULL )
			s += ch[1] -> s ;
	}
} ;

struct Line {
	int u , v ;
	void input () {
		scanf ( "%d%d" , &u , &v ) ;
	}
} ;

struct Command {
	char type ;
	int x , v ;
	Command () {}
	Command ( char type , int x , int v ) : type ( type ) , x ( x ) , v ( v ) {}
} ;

Node *root[MAXN] ;
Line line[MAXL] ;
Command command[MAXC] ;

int weight[MAXN] ;
int n , m , q ;
int p[MAXN] ;
int move[MAXL] ;
int query_cnt ;
LL query_tot ;

void rotate ( Node *&o , int d ) {
	Node *k = o -> ch[d ^ 1] ;
	o -> ch[d ^ 1] = k -> ch[d] ;
	k -> ch[d] = o ;
	o -> maintain () ;
	k -> maintain () ;
	o = k ;
}

void insert ( Node *&o , int x ) {
	if ( o == NULL ) {
		o = new Node ( x ) ;
	} else {
		int d = x < o -> v ? 0 : 1 ;
		insert ( o -> ch[d] , x ) ;
		if ( o -> ch[d] -> r > o -> r )
			rotate ( o , d ^ 1 ) ;
	}
	o -> maintain () ;
}

void remove ( Node *&o , int x ) {
	int d = o -> cmp ( x ) ;
	if ( d == -1 ) {
		Node *u = o ;
		if ( o -> ch[0] != NULL && o -> ch[1] != NULL ) {
			int d2 = o -> ch[0] -> r > o -> ch[1] -> r ? 1 : 0 ;
			rotate ( o , d2 ) ;
			remove ( o -> ch[d2] , x ) ;
		} else {
			if ( o -> ch[0] == NULL )
				o = o -> ch[1] ;
			else
				o = o -> ch[0] ;
			delete u ;
		}
	} else
		remove ( o -> ch[d] , x ) ;
	if ( o != NULL )
		o -> maintain () ;
}

void remove_tree ( Node *&o ) {
	if ( o -> ch[0] != NULL )
		remove_tree ( o -> ch[0] ) ;
	if ( o -> ch[1] != NULL )
		remove_tree ( o -> ch[1] ) ;
	delete o ;
	o = NULL ;
}

int find ( int x ) {
	return p[x] == x ? x : ( p[x] = find ( p[x] ) ) ;
}

void merge ( Node *&src , Node *&des ) {
	if ( src -> ch[0] != NULL )
		merge ( src -> ch[0] , des ) ;
	if ( src -> ch[1] != NULL )
		merge ( src -> ch[1] , des ) ;
	insert ( des , src -> v ) ;
	delete src ;
	src = NULL ;
}

void add_edge ( int i ) {
	int x = find ( line[i].u ) ;
	int y = find ( line[i].v ) ;
	if ( x != y ) {
		if ( root[x] -> s < root[y] -> s ) {
			p[x] = y ;
			merge ( root[x] , root[y] ) ;
		} else {
			p[y] = x ;
			merge ( root[y] , root[x] ) ;
		}
	}
}

void modify ( int x , int v ) {
	int o = find ( x ) ;
	remove ( root[o] , weight[x] ) ;
	insert ( root[o] , v ) ;
	weight[x] = v ;
}

int kth ( Node *o , int k ) {
	if ( o == NULL || k <= 0 || k > o -> s )
		return 0 ;
	int s = o -> ch[1] == NULL ? 0 : o -> ch[1] -> s ;
	if ( s + 1 == k )
		return o -> v ;
	else {
		if ( s >= k )
			return kth ( o -> ch[1] , k ) ;
		else
			return kth ( o -> ch[0] , k - s - 1 ) ;
	}
}

void query ( int x , int k ) {
	x = find ( x ) ;
	++ query_cnt ;
	query_tot += kth ( root[x] , k ) ;
}

void init () {
	query_cnt = 0 ;
	query_tot = 0 ;
	CLR ( move , 0 ) ;
}

void build () {
	FOR ( i , 1 , n )
		scanf ( "%d" , &weight[i] ) ;
	FOR ( i , 1 , m )
		line[i].input () ;
	for ( q = 0 ; ; ++ q ) {
		char type ;
		int x , v , next_weight ;
		scanf ( " %c" , &type ) ;
		if ( type == 'E' )
			break ;
		scanf ( "%d" , &x ) ;
		if ( type == 'D' )
			move[x] = 1 ;
		if ( type == 'Q' )
			scanf ( "%d" , &v ) ;
		if ( type == 'C' ) {
			scanf ( "%d" , &next_weight ) ;
			v = weight[x] ;
			weight[x] = next_weight ;
		}
		command[q] = Command ( type , x , v ) ;
	}
	FOR ( i , 1 , n ) {
		p[i] = i ;
		if ( root[i] != NULL )
			remove_tree ( root[i] ) ;
		root[i] = new Node ( weight[i] ) ;
	}
	FOR ( i , 1 , m )
		if ( !move[i] )
			add_edge ( i ) ;
}

void solve () {
	init () ;
	build () ;
	REV ( i , q - 1 , 0 ) {
		if ( command[i].type == 'D' )
			add_edge ( command[i].x ) ;
		if ( command[i].type == 'Q' )
			query ( command[i].x , command[i].v ) ;
		if ( command[i].type == 'C' )
			modify ( command[i].x , command[i].v ) ;
	}
	printf ( "%.6f\n" , ( double ) query_tot / query_cnt ) ;
}

int main () {
	int cas = 0 ;
	while ( ~scanf ( "%d%d" , &n , &m ) && ( n || m ) ) {
		printf ( "Case %d: " , ++ cas ) ;
		solve () ;
	}
	return 0 ;
}