擦 这题 绝逼 坑人 + 一波N折。。。。
我一开始 用了最简单 最sb的 一维hash数组 来做 我看时间2000ms最大数才10W 还以为能过的 ...果断tle了
然后 就觉得应该用更高效的数据结构来做了
我去问下了下porker 他一开始和我提了下 splay 不会啊=-=
然后 说 树状数组 + 查询的时候 用二分 也可以做到
我就去往 这个方向去想了--------TM的被自己思维定势了... tree[x]把它固定成X有几个了... 然后就一直没做出来
后来 参考了传送
最TM坑的是 我用cin cout一直TLE明明已经写了cin.sync..............
然后改成scanf printf 看A了之后 再改回来 再交 又TLE了
卧槽...
1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 5 const int size = 100010; 6 int tree[size];// tree[x] 即 小于等于x的数有几个 7 8 int lowbit( int x ) 9 { 10 return x & -x; 11 } 12 13 void update( int x , int var ) 14 { 15 while( x<size ) 16 { 17 tree[x] += var; 18 x += lowbit(x); 19 } 20 } 21 22 int getNum( int x ) 23 { 24 int cnt = 0; 25 while( x ) 26 { 27 cnt += tree[x]; 28 x -= lowbit(x); 29 } 30 return cnt; 31 } 32 33 int find( int x , int k ) 34 { 35 int l = x+1 , r = size-5 , ans = size , mid; 36 int temp = getNum(x); 37 int val; 38 while( l<r ) 39 { 40 mid = l + (r-l)/2; 41 val = getNum(mid) - temp; 42 if( val<k ) 43 { 44 l = mid+1; 45 } 46 else 47 { 48 r = mid; 49 if( ans > mid ) 50 ans = mid; 51 } 52 } 53 return ans; 54 } 55 56 int main() 57 { 58 cin.sync_with_stdio(false); 59 int n , num , m ,ans , k; 60 while( cin >> n ) 61 { 62 memset( tree , 0 , sizeof(tree) ); 63 while( n-- ) 64 { 65 //scanf("%d",&m); 66 cin >> m; 67 if( !m ) 68 { 69 //scanf("%d",&num); 70 cin >> num; 71 update( num , 1 ); 72 } 73 else if( m==1 ) 74 { 75 //scanf("%d",&num); 76 cin >> num; 77 if( getNum(num) - getNum(num-1) == 0 ) 78 { 79 //printf("No Elment!\n"); 80 cout << "No Elment!" << endl; 81 } 82 else 83 { 84 update( num , -1 ); 85 } 86 } 87 else 88 { 89 //scanf("%d %d",&num,&k); 90 cin >> num >> k; 91 ans = find( num , k ); 92 if( ans == size ) 93 //printf("Not Find!\n"); 94 cout << "Not Find!" << endl; 95 else 96 //printf("%d\n",ans); 97 cout << ans << endl; 98 } 99 } 100 } 101 return 0; 102 }
1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 5 const int size = 100010; 6 int hash[size]; 7 8 int main() 9 { 10 cin.sync_with_stdio(false); 11 int m , k , num , maxNum , cnt , choice; 12 bool flag; 13 while( cin >> m ) 14 { 15 maxNum = 0; 16 memset( hash , 0 , sizeof(hash) ); 17 while( m-- ) 18 { 19 cin >> choice; 20 if( !choice ) 21 { 22 cin >> num; 23 hash[num] ++; 24 if( maxNum < num ) 25 maxNum = num; 26 } 27 else if( choice == 1 ) 28 { 29 cin >> num; 30 if( hash[num] ) 31 { 32 hash[num] --; 33 } 34 else 35 { 36 cout << "No Elment!" << endl; 37 } 38 } 39 else 40 { 41 flag = false; 42 cnt = 0; 43 cin >> num >> k; 44 for( int i = num+1 ; i<=maxNum ; i++ ) 45 { 46 if( hash[i] ) 47 { 48 cnt += hash[i]; 49 if( cnt>=k ) 50 { 51 cout << i << endl; 52 flag = true; 53 break; 54 } 55 } 56 } 57 if( !flag ) 58 cout << "Not Find!" << endl; 59 } 60 } 61 } 62 return 0; 63 }
hdu--2852--树状数组,布布扣,bubuko.com
原文：http://www.cnblogs.com/radical/p/3901531.html
