首页 > 代码库 > Uva - 1513 Moive collection ( 模拟栈 + 树状数组基本操作 )
Uva - 1513 Moive collection ( 模拟栈 + 树状数组基本操作 )
Uva - 1513 Moive collection ( 模拟栈 + 树状数组基本操作 )
题意：
一个书架，原来所有的书都是按顺序摆好的，书的编号从1开始到n
操作: 取出一本书，统计在这本书之前有多少本书，统计完之后，将这本书放在书架的第一位。
如： 1 2 3 4 5
取4 4 1 2 3 5 （取之前，有3本书在4前面，取完后，将4放在栈顶）
取4 4 1 2 3 5 （取之前，有0本书在4前面，取完后，将4放在栈顶）
取2 2 4 1 3 5 （取之前，有2本书在2前面，取完后，将2放在栈顶）
分析:
模拟一个栈，，用hash维护一下每本书应该在的位置。
数组开2倍的maxn
/* ***********************************************ID : whiteblock63LANG : G++PROG : Uva - 1513 Moive collectionDATE : 2014-10-08 20:53:44************************************************ */#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define CLR( a, b ) memset( a, b, sizeof(a) )using namespace std;#define MAXN 200005int bit[MAXN];int hash[MAXN];void scan( int &x ){ char c; while( c = getchar(), c < ‘0‘ || c > ‘9‘ ); x = c - ‘0‘; while( c = getchar(), c >= ‘0‘ && c <= ‘9‘ ) x = x*10 + c - ‘0‘;}void out( int x ){ if( x > 9 ) out( x/10 ); putchar( x%10 + ‘0‘ );}inline int lowbit( int x ){ return x & -x;}void add( int x, int val ){ while( x <= MAXN ) { bit[x] += val; x += lowbit( x ); }}int sum( int x ){ int ret = 0; while( x > 0 ) { ret += bit[x]; x -= lowbit( x ); } return ret;}void Orz(){ int t, n, m, x ; scan( t ); while( t-- ) { scan( n ), scan( m ); CLR( bit, 0 ); CLR( hash, 0 ); for( int i = 1; i <= n; ++i ) { hash[i] = i + 100000; add( hash[i], 1 ); } for( int i = 0; i < m; ++i ) { scan( x ); int ans = sum( hash[x]-1 ); add( hash[x], -1 ); hash[x] = 100000 - i; add( hash[x], 1 ); if( i != 0 ) { putchar( ‘ ‘ ); out( ans ); } else out( ans ); } putchar( ‘\n‘ ); }}int main(){ Orz(); return 0;}
Uva - 1513 Moive collection ( 模拟栈 + 树状数组基本操作 )
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。