编译信息

编译失败

Nothing is compiled: OUTPUT exceeds.

看不懂啥意思好像和空间有关，难道是编译时间太久了？

maxn = 7.5e5 就会报CE

maxn = 7.5e4 就不会

最大的数组st表21n int，sgt 10n long long，应该不会炸空间啊，但为何把动态开点线段树换掉就可过

#include<bits/stdc++.h>
#define ll long long
#define F(i, l, r) for(int i = l; i <= r; ++i)
#define UF(i, l, r) for(int i = r; i >= l; --i)
#define inf 0x3f3f3f3f
#define inff 0x3f3f3f3f3f3f3f3f
#define pii pair<int,int>
using namespace std;
const int maxn = 7.5e5 + 100;
int N, Q;
ll h[maxn] = {0};
ll ans[maxn];
struct ST{
    #define gett(x, y) (h[(x)] >= h[(y)] ? (x) : (y))
    int n, c[maxn][21];
    void init(int n1){
        n = n1; F(i, 1, n) c[i][0] = i;
        F(k, 1, __lg(n)) F(i, 1, n-(1<<k)+1)
            c[i][k] = gett(c[i][k-1], c[i + (1<<(k-1))][k-1]);
    }
    int ask(int l, int r){
        int k = __lg(r-l+1);
        return gett(c[l][k], c[r-(1<<k)+1][k]);
    }
}st;
vector<pair<int, pii>> qv[maxn];

int son[maxn][2] = {0};
int buildtr(){
    stack<int> sta;
    F(i, 1, N){
        int u = 0;
        while(!sta.empty() && h[i] > h[sta.top()])
            son[sta.top()][1] = u, u = sta.top(), sta.pop();
        son[i][0] = u;
        sta.push(i);
    }
    int u = 0;
    while(!sta.empty())
        son[sta.top()][1] = u, u = sta.top(), sta.pop();
    return u;
}

struct SegTree{
    int rt = 0, tot = 1;
    struct Node{ int lc = 0, rc = 0; ll val = 0, lz1 = 0, lz2 = 0; } tr[maxn*2];
    #define lc(id) tr[id].lc
    #define rc(id) tr[id].rc
    void pushup(int id){;}
    void pushdown(int id, int l, int r){
        if(id == 0) return;
        if(tr[id].lz1 == 0){
            if(l == r)
                tr[id].val += tr[id].lz2;
            else
                tr[lc(id)].lz2 += tr[id].lz2,
                tr[rc(id)].lz2 += tr[id].lz2;
            tr[id].lz2 = 0; return;
        }
        if(l == r){
            tr[id].val = tr[id].lz1 + tr[id].lz2;
            tr[id].lz1 = tr[id].lz2 = 0; return;
        }
        if(lc(id) == 0) lc(id) = ++tot;
        if(rc(id) == 0) rc(id) = ++tot;
        tr[lc(id)].lz1 = tr[rc(id)].lz1 = tr[id].lz1;
        int mid = (l + r) >> 1;
        tr[lc(id)].lz2 = tr[id].lz2;
        tr[rc(id)].lz2 = tr[id].lz2 + (mid-l+1) * tr[id].lz1;
        tr[id].lz1 = tr[id].lz2 = 0;
    }
    ll ask(int id, int l, int r, int qw){
        if(id == 0) return 0;
        pushdown(id, l, r);
        if(l == qw && qw == r) return tr[id].val;
        int mid = (l + r) >> 1;
        if(qw <= mid) return ask(lc(id), l, mid, qw);
        else return ask(rc(id), mid+1, r, qw);
    }
    void add(int& id, int l, int r, int ql, int qr, ll qv1, int qv2){
        if(id == 0) id = ++tot;
        pushdown(id, l, r);
        if(ql <= l && r <= qr){
            tr[id].lz1 = qv1; tr[id].lz2 = qv2 + (l-ql) * qv1;
            return;
        }
        int mid = (l + r) >> 1;
        if(ql <= mid) add(lc(id), l, mid, ql, qr, qv1, qv2);
        if(mid+1 <= qr) add(rc(id), mid+1, r, ql, qr, qv1, qv2);
    }
    int EFfind1(int l, int r, ll a1, ll d, bool flag){
        int l1 = l, r1 = r;
        l--, r++;
        while(l + 1 < r){
            int mid = (l + r) >> 1;
            ll amid = flag ? a1 + (mid-l1) * d : a1 + (r1-mid) * d;
            if(amid < ask(rt, 1, N, mid)) flag ? l = mid : r = mid;
            else flag ? r = mid : l = mid;
        }
        return flag ? l : r;
    }
}sgt1, sgt2;
#define addf(ql, qr, qv1, qv2) sgt1.add(sgt1.rt, 1, N, (ql), (qr), (qv2), (qv1))
#define addg(ql, qr, qv1, qv2) sgt2.add(sgt2.rt, 1, N, (ql), (qr), (qv2), (qv1))
#define f1(x) sgt1.ask(sgt1.rt, 1, N, (x))
#define g2(x) sgt2.ask(sgt2.rt, 1, N, (x))
void dfs(int u, int l, int r){
    if(u == 0) return;
    dfs(son[u][0], l, u-1); dfs(son[u][1], u+1, r);
    for(auto it : qv[u]){
        int id = it.first, ql = it.second.first, qr = it.second.second;
        ans[id] = min(g2(ql) + (qr-u+1) * h[u], f1(qr) + (u+1-ql) * h[u]);
    }
    ll fl = l <= u-1 ? f1(u-1) : 0;
    addf(u, u, fl+h[u], 0);
    if(u+1 <= r){
        addf(u+1, r, h[u]*(u-l+1), 0);
        int r1 = sgt1.EFfind1(u+1, r, 2*h[u]+fl, h[u], 1);
        if(u+1 <= r1) addf(u+1, r1, h[u]+fl, h[u]);
    }
    ll gr = u+1 <= r ? g2(u+1) : 0;
    addg(u, u, gr+h[u], 0);
    if(l <= u-1){
        addg(l, u-1, h[u]*(r-u+1), 0);
        int l1 = sgt2.EFfind1(l, u-1, 2*h[u]+gr, h[u], 0);
        if(l1 <= u-1) addg(l1, u-1, (u-l1+2)*h[u]+gr, -h[u]);
    }
}
int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> N >> Q;
    F(i, 1, N) cin >> h[i];
    st.init(N);
    F(i, 1, Q){
        int l, r; cin >> l >> r; l++, r++;
        qv[st.ask(l, r)].push_back({i, {l, r}});
    }
    dfs(buildtr(), 1, N);
    F(i, 1, Q) cout << ans[i] << '\n';
    return 0;
}