萌新求问空间复杂度

#include <bits/stdc++.h>
#define ll long long
using namespace std; const int N = 1e5 + 5, V = 1e9; int n, a[N], pre[N];
template<class T> void read(T &x) {
    x = 0; T f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -1;
    for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - 48; x *= f;
}
template<class T> void write(T x) {
    if (x > 9) write(x / 10); putchar(x % 10 + 48);
}
template<class T> void print(T x, char ed = '\n') {
    if (x < 0) putchar('-'), x = -x; write(x), putchar(ed);
}
struct SegmentTree {
    int rt, sum[N * 16], ls[N * 16], rs[N * 16], cnt;
    SegmentTree() { 
        memset(ls, 0, sizeof ls); memset(rs, 0, sizeof rs);
        memset(sum, rt = cnt = 0, sizeof sum);
    }
    void upd(int &x, int l, int r, int k, int v) {
        if (!x) x = ++cnt; if (l == r) return void(sum[x] += v); 
        int mid = (l + r) >>  1;
        if (k <= mid) upd(ls[x], l, mid, k, v); else upd(rs[x], mid + 1, r, k, v);
        sum[x] = sum[ls[x]] + sum[rs[x]];
    }
    int qry(int x, int l, int r, int ql, int qr) {
        if (!x) return 0; if (ql <= l && r <= qr) return sum[x]; 
        int mid = (l + r) >> 1, ret = 0;
        if (ql <= mid) ret = qry(ls[x], l, mid, ql, qr);
        if (qr > mid) ret = ret + qry(rs[x], mid + 1, r, ql, qr); return ret; 
    }
    void clr(int x, int l, int r, int k) {
        if (!x) return; sum[x] = 0; if (l == r) return; int mid = (l + r) >> 1;
        if (k <= mid) clr(ls[x], l, mid, k); else clr(rs[x], mid + 1, r, k);
    }
} T1, T2;
ll F(int l, int r) {
    if (l == r) return a[l] == 1; int mid = (l + r) >> 1; ll ret = 0;
    for (int i = mid + 1; i <= r; ++i) {
        pre[i] = max(pre[i - 1], a[i]); T2.upd(T2.rt, 0, V, pre[i] / a[i], 1);
    }
    for (int i = mid, j = mid + 1, mx = 0; i >= l; --i) {
        mx = max(mx, a[i]);
        for (; j <= r && pre[j] <= mx; ++j) 
            T1.upd(T1.rt, 0, V, a[j], 1), T2.upd(T2.rt, 0, V, pre[j] / a[j], -1);
        ret += T1.qry(T1.rt, 0, V, 0, mx / a[i]) + T2.qry(T2.rt, 0, V, a[i], V);
    }
    for (int i = mid + 1; i <= r; ++i) 
        T1.clr(T1.rt, 0, V, a[i]), T2.clr(T2.rt, 0, V, pre[i] / a[i]);
    for (int i = mid + 1; i <= r; ++i) pre[i] = 0;
    return ret + F(l, mid) + F(mid + 1, r);
}
signed main() { 
    read(n); for (int i = 1; i <= n; ++i) read(a[i]); return print(F(1, n)), 0; 
}