2drmq.cpp

#pragma region
#include <bits/stdc++.h>
using namespace std;
// Common Type shorteners and int128
using ll = long long; using ull = unsigned long long; using ld = long double;
using pii = pair<int, int>; using pll = pair<ll, ll>;
template <typename T> using vec = vector<T>;
template <typename K, typename V> using umap = unordered_map<K, V>; template <typename K> using uset = unordered_set<K>;
using vi = vec<int>; using vl = vec<ll>; using vpi = vec<pii>; using vpl = vec<pll>;
#ifdef __SIZEOF_INT128__
using int128 = __int128_t; using uint128 = __uint128_t;
#endif
template<typename I> string intStr(I x) { string ret; while (x > 0) { ret += (x % 10) + '0'; x /= 10; } reverse(ret.begin(), ret.end()); return ret; } // Int to string
// Shorthand Macros
#define INF 0x3f3f3f3f
#define LLINF 0x3f3f3f3f3f3f3f3f
#define mpr make_pair
#define pb push_back
#define popcount __builtin_popcount
#define clz __builtin_clz
#define ctz __builtin_ctz
// Shorthand Function Macros
#define sz(x) ((int)((x).size()))
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for (__typeof(a) i = a; i < b; i++)
#define reprev(i, a, b) for (__typeof(a) i = a; i > b; i--)
#define repi(a, b) rep(i, a, b)
#define repj(a, b) rep(j, a, b)
#define repk(a, b) rep(k, a, b)
#define Cmplt(type) bool operator<(const type &o) const
#define Cmpgt(type) bool operator>(const type &o) const
#define Cmpfn(name, type) bool name(const type &a, const type &b)
#define Inop(type) istream& operator>>(istream& in, type &o)
#define Outop(type) ostream& operator<<(ostream& out, type o)
#define Pow2(x) (1LL << (x))
#define scn(type, ...) type __VA_ARGS__; scan(__VA_ARGS__) // scn -> Short for SCan New
// Shorthand Functions
template<typename T> inline void maxa(T& st, T v) { st = max(st, v); }
template<typename T> inline void mina(T& st, T v) { st = min(st, v); }
inline void setprec(ostream& out, int prec) { out << setprecision(prec) << fixed; }
// Out operators and printing for arrays and vectors
template <typename T> ostream& operator<<(ostream& out,vector<T> iter){out<<"[";for(auto t:iter){out<<t<<", ";}out<<"]";return out;}
template <typename T> string arrayStr(T *arr,int sz){string ret = "[";for(int i=0;i<sz;i++){ret+=to_string(arr[i])+", "; } return ret + "]";}
template <typename T> void printArray(T *arr,int sz){for(int i=0;i<sz;i++){cout<<arr[i]<<" "; } cout<<"\n";}
// I/O Operations
inline void scan(){}
template<typename F, typename... R> inline void scan(F &f,R&... r){cin>>f;scan(r...);}
template <typename F> inline void println(F t){cout<<t<<'\n';}
template<typename F, typename... R> inline void println(F f,R... r){cout<<f<<" ";println(r...);}
inline void print(){}
template<typename F, typename... R> inline void print(F f,R... r){cout<<f;print(r...);}
// Debugging
#define db(x) cout << (#x) << ": " << x << ", "
#define dblb(s) cout << "[" << s << "] "
#define dbbin(x, n) cout << (#x) << ": " << bitset<n>(x) << ", "
#define dbarr(x, n) cout << (#x) << ": " << arrayStr((x), (n)) << ", "
#define dbln cout << endl;
#pragma endregion

struct p {
    int i, j, v;
    Cmplt(p) { return v < o.v; }
};

const int MN = 1001, LG = 10;
int n, m;
vec<p> small;

struct spt {
    int tb[LG][MN];
    void init(vi &v) {
        copy(all(v), tb[0]);
        repi(1, LG) {
            int jmp = 1 << (i - 1), end = n - jmp;
            repj(1, end + 1)
                tb[i][j] = min(tb[i - 1][j], tb[i - 1][j + jmp]);
        }
    }
    int Q(int l, int r) {
        int bit = 31 - clz(r - l + 1);
        return min(tb[bit][l], tb[bit][r - (1 << bit) + 1]);
    }
};

spt tb[LG][MN];
vi aux[LG][MN];

void init(vec<vi> a) {
    n = a.size();

    repi(1, n + 1) {
        aux[0][i].pb(-1);
        aux[0][i].insert(aux[0][i].end(), all(a[i - 1]));

        tb[0][i].init(aux[0][i]);
        // db(i); db(aux[0][i]); dbln;
    }
    repi(1, LG) {
        int jmp = 1 << (i - 1), end = n - jmp;
        repj(1, end + 1) {
            // db(i); db(j); db(aux[i-1][j]); db(aux[i-1][j+jmp]); dbln;
            aux[i][j].pb(-1);
            if (aux[i - 1][j].size() != (size_t)(n + 1) || aux[i - 1][j + jmp].size() != (size_t)(n + 1))
                continue;
            
            repk(1, n + 1)
                aux[i][j].pb(min(aux[i - 1][j][k], aux[i - 1][j + jmp][k]));
                
            tb[i][j].init(aux[i][j]);
            // db(i); db(j); db(aux[i][j]); dbln;
        }
    }
}

int query(int a, int b, int c, int d) {
    a++; b++; c++; d++;
    
    int bit = 31 - clz(b - a + 1);
    return min(tb[bit][a].Q(c, d), tb[bit][b - (1 << bit) + 1].Q(c, d));
}

#ifdef LOCAL
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    init({{1, 2}, {3, 4}});
    db(query(0, 1, 0, 1)); dbln;
    db(query(1, 1, 0, 1)); dbln;
    db(query(0, 0, 1, 1)); dbln;

    return 0;
}
#endif