Light OJ 1081 / 2D Sparse Table

/**

    2D range queries - Sparse table
    Author :: Umnik

**/


/***
 created: 2023-01-05-02.09.28
***/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename U> using ordered_set=tree<U, null_type,less<U>,rb_tree_tag,tree_order_statistics_node_update>;
#define ll long long
#define all(we) we.begin(),we.end()
#define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
#define nl '\n'

const int INF = (int)1e9;
const int LOG = 11;
const int N = 1010;
int p2[N];
vector<vector<int>> sparse[LOG];

int getMax(int x, int y, int d)
{
    int k = p2[d];
    int s = d - (1 << k);
    return max(max(sparse[k][x][y], sparse[k][x + s][y]), max(sparse[k][x][y + s], sparse[k][x + s][y + s]));
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);


    for (int i = 2; i < N; i++)
    {
        p2[i] = p2[i / 2] + 1;
    }

    test
    {
        ll n,m,i,j,k,l;

        cin>>n>>m;

        for (k = 0; k < LOG; k++)
        {
            sparse[k] = vector<vector<int>>(n, vector<int>(n, 0));
        }
        for (i = 0; i < n; i++)
        {
            for (j = 0; j < n; j++)
            {
                cin>>sparse[0][i][j];
            }
        }
        for (k = 0; k < LOG - 1; k++)
        {
            for (i = 0; i + (1 << (k + 1)) <= n; i++)
            {
                for (j = 0; j + (1 << (k + 1)) <= n; j++)
                {
                    sparse[k + 1][i][j] = max(max(sparse[k][i][j], sparse[k][i + (1 << k)][j]), max(sparse[k][i][j + (1 << k)], sparse[k][i + (1 << k)][j + (1 << k)]));
                }
            }
        }

        cout<<"Case "<<cs<<":"<<nl;

        while(m--)
        {
            cin>>i>>j>>k;
            i--,j--;
            cout<<getMax(i,j,k)<<nl;
        }

    }
    return 0;
}