我个人习惯以链表建立线段树，线段树的子节点、父节点之间通过指针连接。

在本题目中，我的代码被疑似卡常限制在了 40 分。我通过与题解代码对比，认为我的代码空间复杂度并没有过大的问题。

我想知道代码 MLE 是否与我的线段树写法有关，还是说我可以在其它地方极限省空间卡过这题？

递交记录

代码：

// #pragma GCC optimize(2) // 开启O2优化
#include<bits/stdc++.h>
using namespace std;
#define N 500010
#define INF 0x3f3f3f3f // 无穷大
#define ll unsigned int
#define ull unsigned long long
#define pii pair<int,int>
#define func function<void()>
#define lowbit(x) (x & -x)
//constexpr ll mod = (1ll<<32);
int n,m,ta,tb,tc,td;
int a[N],b[N],c[N];// 表示要赋值的值
int f[N],g[N],h[N];
int pza[N],pzu[N],pzc[N];// put_zero 即放置 0 的位置
inline void minmz(int &x,const int &y){x = min(x,y);}
inline void maxmz(int &x,const int &y){x = max(x,y);}
// ds 部分
namespace segment_tree{
    struct node{
        int lq,rq;
        ll p;// 系数
        ll lazy = 0;// 懒人标记
        ll sum = 0;// 总和
        node *lson = nullptr,*rson = nullptr;
    }pp[N<<1],*ptr;
    node *root;
    void build(node *idx,const int &lq,const int &rq){
        node &now = *idx;
        now.lq = lq,now.rq = rq;
        if(lq == rq){
            now.p = b[lq];
            return;
        }
        int mid = lq + (rq - lq >> 1);
        now.lson = ptr++,now.rson = ptr++;
        build(now.lson,lq,mid),build(now.rson,mid+1,rq);
        now.p = (now.lson->p) + (now.rson->p);
    }
    inline void push_down(node *idx){
        node &now = *idx;
        if(now.lq == now.rq)return;
        node &lson = *now.lson,&rson = *now.rson;
        lson.sum += lson.p * now.lazy,rson.sum += rson.p * now.lazy;
        lson.lazy += now.lazy,rson.lazy += now.lazy;
        now.lazy = 0;
    }
    void update(node *idx,const int &lq,const int &rq,const ll &k){
        node &now = *idx;
        if(lq <= now.lq && now.rq <= rq){
            now.lazy += k;
            now.sum += now.p * k;
            return;
        }
        if(lq > now.rq || now.lq > rq)return;// 不行
        push_down(idx);
        update(now.lson,lq,rq,k),update(now.rson,lq,rq,k);
        now.sum = now.lson->sum + now.rson->sum;
    }
    ll query(node *idx,const int &lq,const int &rq){
        node &now = *idx;
        if(lq <= now.lq && now.rq <= rq){
            return now.sum;
        }
        if(lq > now.rq || now.lq > rq)return 0;// 不行
        push_down(idx);
        return query(now.lson,lq,rq) + query(now.rson,lq,rq);
    }
}
using namespace segment_tree;
namespace binary_indexed_tree{
    struct BIT{
        ll b[N],c[N];
        BIT(){
            memset(b,0,sizeof(b)),memset(c,0,sizeof(c));

        }
        // single add
        inline void siadd(int x,const ll &k){
            ll tmp = x;
            for(;x <= n;x += lowbit(x))b[x] += k,c[x] += tmp*k;
        }
        // single query
        inline ll siquery(int x){
            ll tmp = x;
            ll res = 0;
            for(;x;x ^= lowbit(x))res += (tmp+1)*b[x] - c[x];
            return res;
        }
        inline void add(const int &lq,const int &rq,const ll &k){siadd(lq,k),siadd(rq+1,-k);}
        inline ll query(const int &lq,const int &rq){return siquery(rq) - siquery(lq - 1);}
    }t2,t3,t4;
}
using namespace binary_indexed_tree;
ll ans;// 答案

// 输入函数
void input(){
    ptr = pp + 1;
    root = pp;
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;++i)a[i] = b[i] = c[i] = n;
    for(int i = 1;i <= m;++i){
        scanf("%d%d%d%d",&ta,&tb,&tc,&td);
        minmz(a[ta],n - td),minmz(b[tb],n - td),minmz(c[tc],n - td);
        maxmz(pza[ta],tb),maxmz(pzu[tc],ta),maxmz(pzc[tc],tb);
    }
    // 前缀和
    for(int i = n - 1;i >= 1;--i){
        minmz(a[i],a[i+1]),minmz(b[i],b[i+1]),minmz(c[i],c[i+1]);
        maxmz(pza[i],pza[i+1]),maxmz(pzu[i],pzu[i+1]),maxmz(pzc[i],pzc[i+1]);
    }
    pzu[0] = n,g[0] = 1;
    build(root,1,n);
    // 维护
    for(int i = 1,p1 = 1,p2 = 1,p3 = 1;i <= n;++i){
        // 找到 b[p1] > a[i] 的指针
        while(p1 <= n && b[p1] <= a[i])++p1;
        while(p2 <= n && a[p2] <= c[i])++p2;
        while(p3 <= n && b[p3] <= c[i])++p3;
        f[i] = p1,g[i] = p2,h[i] = p3;
    }
}

// 处理函数
void solve(){
    // 枚举 c 的位置
    for(int i = 1;i <= n;++i){
        // j 枚举 a 的位置
        for(int j = pzu[i-1];j > pzu[i];--j){
            // 将 b 置入
            int lq = pza[j] + 1,rq = max(lq - 1,f[j] - 1);// 在三维的一坨中谁小选谁
            update(root,lq,rq,1);
            // 剩余部分扔进 t2
            t2.add(rq+1,n,a[j]);
            if(j < g[i - 1])t3.add(lq,n,a[j]);
            else t4.add(lq,n,1);
        }
        // 处理不被 c 覆盖掉的，j 中枚举 a
        for(int j = g[i-1];j < g[i];++j){
            int lq = pza[j] + 1;
            if(j > pzu[i])t3.add(lq,n,a[j]),t4.add(lq,n,-1);
        }
        // 必然被 b 覆盖住的区间
        int lq = pzc[i] + 1,rq = max(h[i] - 1,lq - 1);
        ans += query(root,lq,rq) + t2.query(lq,rq) + t3.query(rq + 1,n) + t4.query(rq + 1,n) * c[i];

//        printf("%lld %lld %lld %lld\n",query(root,lq,rq),t2.query(lq,rq),t3.query(rq + 1,n),t4.query(rq + 1,n));
//        printf("ans = %lld\n",ans);
    }
}

// 输出函数
void output(){
    printf("%lld",ans);
}

// 主函数
int main(int argc,char* argv[]){
	input();
	solve();
	output();
	return 0;
}