「TJOI2019」甲苯先生的滚榜

问题分析

参照数据范围，我们需要一个能够在\(O(n\log n)\)复杂度内维护有序数列的数据结构。那么平衡树是很好的选择。参考程序中使用带旋Treap。
参考程序

#pragma GCC optimize( 3 )

#include <cstdio>

#include <ctime>

#include <algorithm>

namespace Treap {

	struct member {

		int Number, Time;

		bool operator > ( const member Other ) const {

			return Number < Other.Number || Number == Other.Number && Time > Other.Time;

		};

		bool operator == ( const member Other ) const {

			return Number == Other.Number && Time == Other.Time;

		};

		bool operator < ( const member Other ) const {

			return Number > Other.Number || Number == Other.Number && Time < Other.Time;

		}

	};

	struct node {

		int Random, Size, Cnt;

		member Value;

		node *LeftChild, *RightChild;

	};

	void Collect( node *A ) {

		A->Size = A->Cnt + ( ( A->LeftChild != NULL ) ? A->LeftChild->Size : 0 ) + ( ( A->RightChild != NULL ) ? A->RightChild->Size : 0 );

		return;

	}

	node *LeftRotate( node *A ) {

		node *B = A->RightChild; A->RightChild = B->LeftChild; B->LeftChild = A; Collect( A ); Collect( B ); return B;

	}

	node *RightRotate( node *A ) {

		node *B = A->LeftChild; A->LeftChild = B->RightChild; B->RightChild = A; Collect( A ); Collect( B ); return B;

	}

	node *Insert( node *Rt, member x ) {

		if( Rt == NULL ) {

			Rt = new node;

			Rt->Random = rand() % 1000000000; Rt->Value = x; Rt->Size = 1; Rt->Cnt = 1; Rt->LeftChild = Rt->RightChild = NULL;

			return Rt;

		}

		++( Rt->Size );

		if( Rt->Value == x ) { ++( Rt->Cnt ); return Rt; }

		if( Rt->Value < x ) {

			Rt->RightChild = Insert( Rt->RightChild, x ); if( Rt->RightChild->Random < Rt->Random ) Rt = LeftRotate( Rt );

		} else {

			Rt->LeftChild = Insert( Rt->LeftChild, x ); if( Rt->LeftChild->Random < Rt->Random ) Rt = RightRotate( Rt );

		}

		return Rt;

	}

	node *Del( node *Rt, member x ) {

		if( Rt == NULL ) { printf( "No such number called %d\n", x ); return Rt; }

		if( Rt->Value == x ) {

			if( Rt->Cnt > 1 ) { --( Rt->Cnt ); --( Rt->Size ); return Rt; }

			if( Rt->LeftChild == NULL ) { node *T = Rt->RightChild; delete Rt; return T; }

			if( Rt->RightChild == NULL ) { node *T = Rt->LeftChild; delete Rt; return T; }

			if( Rt->LeftChild->Random <= Rt->RightChild->Random ) {

				Rt = RightRotate( Rt ); --( Rt->Size ); Rt->RightChild = Del( Rt->RightChild, x ); return Rt;

			} else {

				Rt = LeftRotate( Rt ); --( Rt->Size ); Rt->LeftChild = Del( Rt->LeftChild, x ); return Rt;

			}

			return Rt;

		}

		--( Rt->Size );

		if( Rt->Value < x ) { Rt->RightChild = Del( Rt->RightChild, x ); return Rt; }

		else { Rt->LeftChild = Del( Rt->LeftChild, x ); return Rt; }

		return Rt;

	}

	int QueryR( node *Rt, member x ) {

		int Ans = 0;

		for( ; Rt != NULL; ) {

			if( Rt->Value == x ) return Ans + ( ( Rt->LeftChild != NULL ) ? Rt->LeftChild->Size : 0 ) + 1;

			if( Rt->Value < x ) {

				Ans += ( ( Rt->LeftChild != NULL ) ? Rt->LeftChild->Size : 0 ) + Rt->Cnt;

				Rt = Rt->RightChild;

			} else Rt = Rt->LeftChild;

		}

		return Ans + 1;

	}

	member QueryN( node *Rt, int x ) {

		for( ; Rt != NULL; ) {

			int Rc = 0; if( Rt->LeftChild != NULL ) Rc = Rt->LeftChild->Size;

			if( x > Rc && x <= Rc + Rt->Cnt ) return Rt->Value;

			if( x <= Rc ) Rt = Rt->LeftChild; else { x -= Rc + Rt->Cnt; Rt = Rt->RightChild; }

		}

		printf( "QueryNumber Failed.\n" );

		return ( member ){ -1, -1 };

	}

	member pre( node *Rt, member x ) {

		member Ans = x;

		for( ; Rt != NULL; ) if( Rt->Value < x ) { Ans = Rt->Value; Rt = Rt->RightChild; } else Rt = Rt -> LeftChild;

		if( Ans == x ) printf( "Query Pre Failed.\n" );

		return Ans;

	}

	member suc( node *Rt, member x ) {

		member Ans = x;

		for( ; Rt != NULL; ) if( Rt->Value > x ) { Ans = Rt->Value; Rt = Rt->LeftChild; } else Rt = Rt -> RightChild;

		if( Ans == x ) printf( "Query Suc Failed.\n" );

		return Ans;

	}

	struct treap {

		node *Root;

		void clear() { delete [] Root; Root = NULL; srand( time( NULL ) ); return; }

		void insert( member x ) { Root = Insert( Root, x ); return; }

		void Delete( member x ) { Root = Del( Root, x ); return; }

		int QueryRank( member x ) { return QueryR( Root, x ); }

		member QueryNumber( int x ) { return QueryN( Root, x ); }

		member Pre( member x ) { return pre( Root, x ); }

		member Suc( member x ) { return suc( Root, x ); }

	};

} //Treap

Treap::treap Tree;

namespace UI {

	typedef unsigned int ui ;

	ui randNum( ui& seed , ui last , const ui m){

    	seed = seed * 17 + last ; return seed % m + 1;

	}

	ui seed, last = 7;

	void InSeed() { scanf( "%llu", &seed ); return; }

} //UI

const int Maxm = 100010;

Treap::member Rec[ Maxm ];

void MAIN() {

	Tree.clear();

	int n, m; scanf( "%d%d", &m, &n ); UI::InSeed();

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

		Tree.insert( ( Treap::member ){ 0, 0 } );

		Rec[ i ] = ( Treap::member ){ 0, 0 };

	}

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

		int x = UI::randNum( UI::seed, UI::last, m );

		int y = UI::randNum( UI::seed, UI::last, m );

		Tree.Delete( Rec[ x ] );

		++Rec[ x ].Number;

		Rec[ x ].Time += y;

		Tree.insert( Rec[ x ] );

		UI::last = Tree.QueryRank( Rec[ x ] ) - 1;

		printf( "%llu\n", UI::last );

	}

	return;

}

int main() {

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

	for( ; TestCases--; ) MAIN();

	return 0;

}
巴特西

「TJOI2019」甲苯先生的滚榜

问题分析

参考程序

最新文章

热门文章
