lib/Documentation/docs-sonyckson/Fenwick_Trees.cpp

   1 #include <string>
   2 #include <iostream>
   3 #include <cstdio>
   4 using namespace std;
   5
   6 int FT[1<<20];
   7 int MX =  1 << 20;
   8
   9 void update(int ind, int val){
  10         while ( ind <= MX ){
  11                 FT[ind]+= val;
  12                 ind += (ind&-ind);
  13         }
  14 }
  15 int query(int ind ){
  16         int res = 0;
  17         while( ind ){
  18                 res += FT[ind];
  19                 ind -= (ind&-ind);
  20         }
  21         return res;
  22 }
  23 int get(int val, int b, int e){
  24         while( b + 1 < e ){
  25                 int med = ( b + e ) / 2 ;
  26                 if( query(med) >= val ) e = med;
  27                 else b = med;
  28         }
  29         return e;
  30 }
  31 int main(){
  32         int i,j,k;int casos; cin >> casos;
  33         for(int h = 0 ; h < casos; h ++ ){
  34                 int N; cin >> N;
  35                 int arr[1000010];
  36                 memset(FT, 0, sizeof(FT));
  37 //              printf("ACA TAAAA\n");
  38                 for(i=1;i<=N;i++){
  39                         update(i, 1);
  40                 }
  41 //              printf("ACA TAAAA\n");
  42
  43                 int cant = N;
  44                 int place = N;
  45                 for(i=0;i<N;i++){
  46 //                      for(j=1;j<=N;j++) printf("%i ", query(j));printf("\n");
  47                         place = ( place + i ) % cant;
  48                         cant--;
  49                         int ind = get(place+1,0, N+1);
  50                         update(ind,-1);
  51                         arr[ind] = i+1;
  52                 }
  53                 cout << "Case #" << h+1 << ":";
  54                 int Q; cin >> Q;
  55                 for(i=0;i<Q;i++){
  56                         cin >> k;
  57                         cout << " " << arr[k];
  58                 }
  59                 cout << endl;
  60         }return 0;
  61 }