https://www.hackerearth.com/problem/algorithm/research-on-numbers-1

research_on_number.cc

#include <bits/stdc++.h>
#ifdef __mr__
    #include "prettyprint.hpp"
#else
    #define endl                    '\n'
#endif
#define len(x)                      (uint)(x).size()
#define int                         int32_t
#define uint                        uint32_t
#define ulong                       uint64_t
#define long                        int64_t
#define t_max(x)                    numeric_limits<x>::max()
#define t_min(x)                    numeric_limits<x>::min()
using namespace std;
const ulong mod = 1000000007ul;

// problem: https://www.hackerearth.com/problem/algorithm/research-on-numbers-1

template<class etype, class etypearr>
class rangeminimumquery {
private:
    etypearr& arr;
    uint n;
    uint* logt;
    uint** sparset;
public:
    rangeminimumquery(etypearr& arri, uint ni) : arr(arri), n(ni) {
        // Generate Log Table
        logt = new uint[n + 1];
        logt[1] = logt[0] = 0;
        for (uint x = 2; x < n + 1; ++x)
            logt[x] = logt[x >> 1] + 1;
        // Generate Sparse Table
        sparset = new uint*[n];
        for (uint x = 0; x < n; ++x) {
            sparset[x] = new uint[logt[n] + 1];
            sparset[x][0] = x;
        }
        for (int x = n - 1; x > -1; --x) {
            for (int y = 1; y < logt[n - x] + 1; ++y) {
                if (arr[sparset[x][y - 1]] < arr[sparset[x + (1 << (y - 1))][y - 1]])
                    sparset[x][y] = sparset[x][y - 1];
                else
                    sparset[x][y] = sparset[x + (1 << (y - 1))][y - 1];
            }
        }
    }
    etype query(uint i, uint j) {
        uint k = logt[j - i];
        if (arr[sparset[i][k]] < arr[sparset[j - (1 << k)][k]])
            return sparset[i][k];
        else
            return sparset[j - (1 << k)][k];
    }
    etype query_value(uint i, uint j) {
        uint k = logt[j - i];
        return min(
            arr[sparset[i][k]],
            arr[sparset[j - (1 << k)][k]]);
    }
    ~rangeminimumquery() {
        delete[] logt;
        for (int x = 0; x < n; ++x)
            delete[] sparset[x];
        delete[] sparset;
    }
};


int main(int argc, char const *argv[]) {
    #ifndef __mr__
        ios::sync_with_stdio(0);cin.tie(0);
    #endif
    ulong mod = 1000000007;
    int testcases;
    cin >> testcases;
    while(testcases--) {
        int q, k;
        cin >> q >> k;
        vector<ulong> b(k);
        vector<ulong> c(k);
        int n = 1000000;
        vector<ulong> arr(n);
        for (uint i = 0; i < k; ++i) {
            cin >> b[i];
        }
        for (uint i = 0; i < k; ++i) {
            cin >> c[i];
        }
        for (uint i = 0; i < k; ++i) {
            arr[i] = b[i];
        }
        for (uint x = k; x < n; ++x) {
            for (uint y = 0; y < k; ++y) {
                arr[x] += arr[x - y - 1] * c[y];
            }
            arr[x] %= 1000000007;
        }
        rangeminimumquery<ulong, vector<ulong>> rmq(arr, n);
        for (uint i = 0; i < q; ++i) {
            int l, r;
            cin >> l >> r;
            --l;
            vector<pair<int, int>> univ;
            univ.push_back({l, r});
            for (uint j = 0; j < 100; ++j) {
                pair<int, int> mipos = {-1, -1};
                for (uint ind = 0; ind < len(univ); ++ind) {
                    if (mipos.first == -1 || arr[mipos.first] > arr[rmq.query(univ[ind].first, univ[ind].second)]) {
                        mipos = {rmq.query(univ[ind].first, univ[ind].second), ind};
                    }
                }
                if (mipos.first == -1) {
                    break;
                }
                cout << arr[mipos.first] << ' ';
                auto split = univ[mipos.second];
                univ.erase(univ.begin() + mipos.second);
                if (mipos.first > split.first) {
                    univ.push_back({split.first, mipos.first});
                }
                if (mipos.first + 1 < split.second) {
                    univ.push_back({mipos.first + 1, split.second});
                }
            }
            cout << endl;
        }
    }
    return 0;
}

research_on_number.py

#!/usr/bin/env python2.7
# coding: utf-8
from sys import stdin
from operator import itemgetter

def generateLogTable(n):
    """
    ::args::
        n ⟶ size of the log table
    ::returns::
        log base 2 table
    ::note::
        using logtable is efficient for large
          number of queries than using math.log approximation.
        math.log easily takes 8 - 20 iteration for each query.
    """
    logt = [0, 0]
    for x in xrange(2, n):
        logt.append(logt[x >> 1] + 1)
    return logt

class rangeMinimumQuery(object):
    """
    rangeMinimumQuery using sparse table approach
    Complexity:
        preprocessing step => O(nlogn)
        query step => O(1)
    """
    def __init__(self, arr):
        self.arr = arr
        n = len(arr)
        self.logt = generateLogTable(n + 1)
        self.rmq = self.generateSparseTable(n, self.logt)

    def __getitem__(self, slx):
        """
        ::args::
            slx ⟶ slice object denoting the range
        ::returns::
            min(arr[i: j])
        """
        i, j, _ = slx.indices(len(self.arr))
        k = self.logt[j - i]
        if self.arr[self.rmq[i][k]] < self.arr[self.rmq[j - (1 << k)][k]]:
            return self.rmq[i][k]
        else:
            return self.rmq[j - (1 << k)][k]

    def query(self, i, j):
        """
        ::args::
            i ⟶ starting index of the range
            j ⟶ ending index of the range (excluded)
        ::returns::
            position of min(arr[i: j])
        """
        k = self.logt[j - i]
        return min(
            self.arr[self.rmq[i][k]],
            self.arr[self.rmq[j - (1 << k)][k]])

    def generateSparseTable(self, n, logt):
        rmq = [[0]*(1 + logt[n]) for _ in xrange(n)]
        for x in xrange(n):
            rmq[x][0] = x
        for x in xrange(n - 1, -1, -1):
            for y in xrange(1, logt[n - x] + 1):
                if self.arr[rmq[x][y - 1]] < self.arr[rmq[x + (1 << (y - 1))][y - 1]]:
                    rmq[x][y] = rmq[x][y - 1]
                else:
                    rmq[x][y] = rmq[x + (1 << (y - 1))][y - 1]
        return rmq


def blah(query, rmq, arr):
    univ = [query]
    answer = []
    for _ in xrange(100):
        mipos = (-1, -1)
        for i, (x, y) in enumerate(univ):
            if mipos[0] == -1 or arr[mipos[0]] > arr[rmq[x: y]]:
                mipos = (rmq[x: y], i)
        if mipos[0] == -1:
            break
        answer.append(arr[mipos[0]])
        split = univ.pop(mipos[1])
        if mipos[0] > split[0]:
            univ.append((split[0], mipos[0]))
        if mipos[0] + 1 < split[1]:
            univ.append((mipos[0] + 1, split[1]))
    return answer



def main():
    mod = 1000000007
    nextint = iter(map(int, stdin.read().split())).next
    for _ in xrange(nextint()):
        q, k = nextint(), nextint()
        b = [nextint() for _ in xrange(k)]
        c = [nextint() for _ in xrange(k)]
        queries = [(nextint() - 1, nextint()) for _ in xrange(q)]
        n = max(max(queries, key=itemgetter(1))[1], k)
        arr = b + ([0] * (n - k))
        for x in xrange(k, n):
            for y in xrange(k):
                arr[x] += c[y] * arr[x - y - 1]
            arr[x] %= mod
        rmq = rangeMinimumQuery(arr)
        out = []
        for qu in queries:
            out.append(' '.join(map(str, blah(qu, rmq, arr))))
            # out.append(' '.join(map(str, sorted(arr[qu[0]: qu[1]])[:100])))
        print '\n'.join(out)

main()