[Spoj] ASCDFIB – Ascending Fibonacci Numbers

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : ASCDFIB – Ascending Fibonacci Numbers
Source            : Spoj
Category          : Data Structure
Algorithm         : Wavelet Tree
Verdict           : Accepted

#include "bits/stdc++.h"  
   
using namespace std;  
   
#define ll         long long  
   
static const int maxn = 1100000 + 5;  
static const int mod = 1e5;  
   
struct wavelet_tree  
{  
      #define vi          vector <int>  
      #define pb          push_back  
   
      int lo, hi;  
      wavelet_tree *l, *r;  
      vi b;  
      wavelet_tree(int *from, int *to, int x, int y)  
      {  
            lo = x;  
            hi = y;  
            if (lo == hi || from >= to) return;  
            int mid = (lo + hi) >> 1;  
            auto f = [mid](int x)  
            {  
                  return x <= mid;  
            };  
            b.reserve(to - from + 1);  
            b.pb(0);  
            for (auto it = from; it != to; it++)  
            {  
                  b.pb(b.back() + f(*it));  
            }  
            auto pivot = stable_partition(from, to, f);  
            l = new wavelet_tree(from, pivot, lo, mid);  
            r = new wavelet_tree(pivot, to, mid + 1, hi);  
      }  
      // kth smallest element in [l, r]  --- 1 indexed  
 int kth(int l, int r, int k)  
      {  
            if (l > r) return 0;  
            if (lo == hi) return lo;  
            int lb = b[l-1];  
            int rb = b[r];  
            int inLeft = rb - lb;  
            if (k <= inLeft) return this->l->kth(lb + 1, rb, k);  
            else return this->r->kth(l - lb, r - rb, k - inLeft);  
    }  
    ~wavelet_tree()  
    {  
        delete l;  
        delete r;  
    }  
};  
   
int fibo[maxn], temp[maxn];  
   
inline void fibonacci_series()  
{  
      fibo[1] = 0; temp[1] = fibo[1];  
      fibo[2] = 1; temp[2] = fibo[2];  
      for (int i = 3; i < maxn; i++)  
      {  
            fibo[i] = fibo[i-1] + fibo[i-2];  
            if (fibo[i] >= mod) fibo[i] -= mod;  
            temp[i] = fibo[i];  
      }  
}  
   
int main()  
{  
      fibonacci_series();  
      wavelet_tree *T;  
      T = new wavelet_tree(temp+1, temp+maxn+1, 0, 100000+1);  
      int tc;  
      scanf("%d", &tc);  
      for (int tcase = 1; tcase <= tc; tcase++)  
      {  
            int A, B;  
            scanf("%d %d", &A, &B);  
            int maxlen = min(100, B + 1);  
            printf("Case %d: ", tcase);  
            for (int i = 1; i <= maxlen; i++)  
            {  
                  int kth = T->kth(A, A+B, i);  
                  printf("%d", kth);  
                  if (i == maxlen) puts("");  
                  else printf(" ");  
            }  
      }  
}