484E - Sign on Fence - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

#define N 100000
#define L (1 << 17)

struct node
{
    uint32_t longest_prefix, longest_suffix, longest_subarray;
};

size_t n, k;
uint32_t h[N], p[N], Q[N][4];
node tree[2 * L];

node merge_nodes(node const &x, node const &y, size_t xlen, size_t ylen)
{
    node z;
    z.longest_subarray = max(x.longest_subarray, max(y.longest_subarray, x.longest_suffix + y.longest_prefix));
    z.longest_prefix = x.longest_prefix;
    if (z.longest_prefix == xlen)
        z.longest_prefix += y.longest_prefix;
    z.longest_suffix = y.longest_suffix;
    if (z.longest_suffix == ylen)
        z.longest_suffix += x.longest_suffix;
    return z;
}

void update(size_t i, uint32_t x)
{
    i += L;
    tree[i].longest_prefix = tree[i].longest_suffix = tree[i].longest_subarray = x;
    size_t l = 1;
    while (i >>= 1)
        tree[i] = merge_nodes(tree[2 * i], tree[2 * i + 1], l, l), l <<= 1;
}

uint32_t largest_conseq_set(size_t i, size_t j)
{
    i += L, j += L;
    node x = {0, 0, 0}, y = {0, 0, 0};
    size_t xlen = 0, ylen = 0, l = 1;

    while (i <= j)
    {
        if (i & 1)
            x = merge_nodes(x, tree[i++], xlen, l), xlen += l;
        if (!(j & 1))
            y = merge_nodes(tree[j--], y, l, ylen), ylen += l;
        i >>= 1;
        j >>= 1;
        l <<= 1;
    }

    return merge_nodes(x, y, xlen, ylen).longest_subarray;
}

void dnc(vector<size_t> const &queries, uint32_t a, uint32_t b)
{
    if (a == b)
    {
        for (size_t const &i : queries)
            Q[i][3] = max(Q[i][3], h[p[a]]);
        return;
    }
    uint32_t const mid = (a + b + 1) / 2;
    while (k && k - 1 >= mid)
        update(p[--k], 1);
    while (k < n && k < mid)
        update(p[k++], 0);

    vector<size_t> left_queries, right_queries;
    for (size_t const &i : queries)
        if (largest_conseq_set(Q[i][0], Q[i][1]) < Q[i][2])
            left_queries.push_back(i);
        else
            right_queries.push_back(i), Q[i][3] = max(Q[i][3], h[p[mid]]);
    dnc(left_queries, a, mid - 1);
    dnc(right_queries, mid, b);
}

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

    cin >> n;
    for (size_t i = 0; i < n; ++i)
        cin >> h[i];
    iota(p, p + n, 0);
    sort(p, p + n, [](auto const &a, auto const &b)
         { return h[a] < h[b]; });
    k = n;

    size_t q;
    cin >> q;
    for (size_t i = 0; i < q; ++i)
        cin >> Q[i][0] >> Q[i][1] >> Q[i][2], --Q[i][0], --Q[i][1];
    vector<size_t> all_queries(q);
    iota(all_queries.begin(), all_queries.end(), 0);
    dnc(all_queries, 0, n - 1);
    for (size_t i = 0; i < q; ++i)
        cout << Q[i][3] << '\n';
}