hdu5249

这个是去年astar的题~

标准做法主席树，然而渣渣并不会（我确实叫zhazha。。。），

所以，他先离线，离散化，然后树状数组+二分水过了。。。。

离线的目的主要是为了离散化，剩下的就和用一个树状数组维护一个数之前有多少个数比他小差不多~~

二分答案+树状数组求和判断即可，注意二分何时终止~~（复杂度O(nlognlogn)）

  1 #include <bits/stdc++.h>
  2 
  3 using namespace std;
  4 const int maxn = 10000 + 100;
  5 int n, a[maxn], input[maxn], c[maxn];
  6 char str[maxn][20];
  7 
  8 int flag[maxn];
  9 
 10 map<int, int> mp;
 11 
 12 inline int lowbit(int x){
 13   return x & (-x);
 14 }
 15 
 16 int sum(int x){
 17   int ret = 0;
 18   while(x > 0){
 19     ret += c[x];
 20     x -= lowbit(x);
 21   }
 22   return ret;
 23 }
 24 
 25 void add(int x, int d){
 26   while(x <= n){
 27     c[x] += d;
 28     x += lowbit(x);
 29   }
 30 }
 31 
 32 void solve(int p){
 33   int left = 0, right = n+1;
 34 
 35   while(left+1<right){
 36     int mid = (left + right)/2;
 37     int sum1 = sum(mid);
 38     //cout << "mid: " << mid << "  sum: " << sum1 << endl;
 39 
 40     if( sum1 > p ){
 41       right = mid;
 42     }else if( sum1 < p ){
 43       left = mid;
 44     }else{
 45       if(flag[mid] == 1){
 46         printf("%d
", a[mid]);
 47         return;
 48       }else{
 49         right = mid;
 50       }
 51     }
 52   }
 53 }
 54 
 55 queue<int> q;
 56 
 57 int main(void){
 58   int cas = 1;
 59   while(scanf("%d", &n) != EOF){
 60     int len = 0, num;
 61     for(int i = 0; i < n; ++i){
 62       scanf("%s", str[i]);
 63       if(str[i][0] == 'i'){
 64         scanf("%d", &num);
 65         input[++len] = num;
 66         a[len] = num;
 67       }
 68     }
 69 
 70     //离散化
 71     sort(a+1, a+len+1);
 72     mp.clear();
 73     for( int i = 1; i <= len; ++i ){
 74       mp[a[i]] = i;
 75     }
 76 
 77     memset(c, 0, sizeof(c));
 78     memset(flag, 0, sizeof(flag));
 79 
 80     while(!q.empty())
 81         q.pop();
 82 
 83     printf("Case #%d:
", cas++);
 84     int sz = 0, cnt = 0;
 85     for( int i = 0; i < n; ++i ){
 86       if( str[i][0] == 'i' ){
 87         num = input[++cnt];
 88         q.push(num);
 89         sz++;
 90         num = mp[num];
 91         add(num, 1);
 92         flag[num] = 1;
 93       }else if( str[i][0] == 'q' ){
 94         int p = sz/2+1;
 95         //cout << "p: " << p << endl;
 96         solve(p);
 97       }else{
 98         sz--;
 99         num = q.front();
100         q.pop();
101         num = mp[num];
102         add(num, -1);
103         flag[num] = 0;
104       }
105     }
106   }
107 
108   return 0;
109 }
110 
111 /**
112 11
113 in 32
114 in 16
115 in 87
116 out
117 in 96
118 in 34
119 query
120 out
121 out
122 in 3687
123 query
124 */

View Code