TlE#4

TLE是什么原因呀？

写的是整体二分 复杂度应该是O(nloglogn)吧

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#define ls (x << 1)
#define rs (x << 1 | 1)
#define mid ((l + r) >> 1)
using namespace std;
typedef long long ll;
ll read()
{
    char c = 0;
    ll o = 1, x = 0;
    while (c < '0' or '9' < c)
    {
        if (c == '-')
            o = -o;
        c = getchar();
    }
    while ('0' <= c and c <= '9')
    {
        x *= 10;
        x += c - '0';
        c = getchar();
    }
    return x * o;
}
void write(ll x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    ll sck[20], sctop = 0;
    do
    {
        sck[sctop++] = x % 10;
        x /= 10;
    } while (x);
    for (ll i = sctop - 1; i >= 0; --i)
        putchar(sck[i] + '0');
    puts("");
}
ll const maxn = 1e5 + 7, maxt = 2e6 + 7;
ll ln[maxn << 2], mn[maxn << 2], rn[maxn << 2], mmax, rmax;
void push_up(ll x, ll l, ll r)
{
    if (mn[ls] == mid - l + 1)
        ln[x] = mn[ls] + ln[rs];
    else
        ln[x] = ln[ls];
    if (mn[rs] == r - mid)
        rn[x] = mn[rs] + rn[ls];
    else
        rn[x] = rn[rs];
    mn[x] = max(max(mn[ls], mn[rs]), rn[ls] + ln[rs]);
}
void mod(ll x, ll l, ll r, ll k, ll val)
{
    if (k < l or r < k)
        return;
    if (l == r)
    {
        ln[x] = mn[x] = rn[x] = val;
        return;
    }
    mod(ls, l, mid, k, val);
    mod(rs, mid + 1, r, k, val);
    push_up(x, l, r);
}
void qry(ll x, ll l, ll r, ll L, ll R)
{
    if (R < l or r < L)
        return;
    if (L <= l and r <= R)
    {
        mmax = max(mmax, mn[x]);
        mmax = max(mmax, rmax + ln[x]);
        if (mn[x] == r - l + 1)
            rmax += mn[x];
        else
            rmax = rn[x];
        return;
    }
    qry(ls, l, mid, L, R);
    qry(rs, mid + 1, r, L, R);
}
ll n, m;
ll ans[maxn];
struct num
{
    ll x, v;
} a[maxn];
struct qq
{
    ll l, r, k, p;
} q[maxn];
bool cmp(num a, num b)
{
    return a.v < b.v;
}
ll T[maxt];
void deal(ll l, ll r, ll ql, ll qr, ll tot)
{
    // prllf("%d %d %d %d\n", l, r, ql, qr);
    if (ql > qr or l > r)
        return;
    for (ll i = mid; i <= n; ++i)
        mod(1, 1, n, a[i].x, 1);
    ll *u = new ll[maxn];
    ll ut = 0;
    ll *v = new ll[maxn];
    ll vt = 0;
    for (ll i = ql; i <= qr; ++i)
    {
        ll j = T[i];
        mmax = rmax = 0;
        qry(1, 1, n, q[j].l, q[j].r);
        // write(mmax);
        if (mmax >= q[j].k)
        {
            ans[q[j].p] = a[mid].v;
            u[++ut] = j;
        }
        else
            v[++vt] = j;
    }
    for (ll i = mid; i <= n; ++i)
        mod(1, 1, n, a[i].x, 0);
    ll fl = tot + 1, fr = tot;
    for (ll i = 1; i <= vt; ++i)
        T[++fr] = v[i];
    ll sl = fr + 1, sr = fr;
    for (ll i = 1; i <= ut; ++i)
        T[++sr] = u[i];
    // prllf("%d %d %d %d\n", fl, fr, sl, sr);
    delete[] u;
    delete[] v;
    deal(l, mid - 1, fl, fr, sr);
    deal(mid + 1, r, sl, sr, sr);
}
int main()
{
    n = read();
    for (ll i = 1; i <= n; ++i)
    {
        a[i].v = read();
        a[i].x = i;
    }
    sort(a + 1, a + n + 1, cmp);
    m = read();
    for (ll i = 1; i <= m; ++i)
    {
        q[i].l = read();
        q[i].r = read();
        q[i].k = read();
        q[i].p = i;
        T[i] = i;
    }
    deal(1, n, 1, m, m);
    for (ll i = 1; i <= m; ++i)
        write(ans[i]);
    return 0;
}
/*
 */