关于权值线段树动态开点

一开始我用的是结构体指针的做法，50分,后面十个点MLE

Link

在第十一个样例中，下载数据后，我发现我的线段树开了6052166个节点(代码中的cnt)

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e9+5;
int n,a;
long long ans=0;
struct edge{
    edge *l,*r;
    int sum;
    edge(){
        sum=0,l=NULL,r=NULL;
    }
    void upd_sum(){
        sum=0;
        sum+=(l==NULL?0:l->sum);
        sum+=(r==NULL?0:r->sum);
        return ;
    }
};
edge *rt=NULL;int cnt=0;
struct node{

    void update(edge *&now,int l,int r,int pos){
        if(!now)now=new edge(),cnt++;
        if(l>r)return;
        if(l==r){
            if(l==pos)
                now->sum++;
            return ;
        }
        int mid=(l+r)/2;
        if(pos<=mid)update(now->l,l,mid,pos);
        else update(now->r,mid+1,r,pos);
        now->upd_sum();
        return ;
    }
    int check(edge *&now,int l,int r,int x,int y){
        if(!now)return 0;
        if(l>r)return 0;
        if(r<x||y<l)return 0;
        if(x<=l&&r<=y)return now->sum;
        int mid=(l+r)/2;
        return check(now->l,l,mid,x,y)+check(now->r,mid+1,r,x,y);
    }

}T;
signed main(){
//  freopen("P1908_11.in","r",stdin);
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&a);
        ans+=T.check(rt,1,1e9,a+1,1e9);
        printf("%d %d\n",i,cnt);
//      cout<<ans<<endl;
        T.update(rt,1,1e9,a);
    }
    cout<<ans<<endl;
    return 0;
}

之后我改成了用数组代替指针的写法，然后AC了

Link

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e9+5,maxm=6*1e7+5;
int n,a,f[maxm]={0},L[maxm]={0},R[maxm]={0};
long long ans=0;
int rt=0;
int cnt=0;
struct node{
    void update(int &now,int l,int r,int pos){
        if(now==0)now=++cnt,f[now]=0,L[now]=0,R[now]=0;
        if(l>r)return;
        if(l==r){
            if(l==pos)
                f[now]++;
            return ;
        }
        int mid=(l+r)/2;
        if(pos<=mid)update(L[now],l,mid,pos);
        else update(R[now],mid+1,r,pos);
        f[now]=0;
        if(L[now]!=0)f[now]+=f[L[now]];
        if(R[now]!=0)f[now]+=f[R[now]];
        return ;
    }
    int check(int &now,int l,int r,int x,int y){
        if(now==0)return 0;
        if(l>r)return 0;
        if(r<x||y<l)return 0;
        if(x<=l&&r<=y)return f[now];
        int mid=(l+r)/2;
        return check(L[now],l,mid,x,y)+check(R[now],mid+1,r,x,y);
    }

}T;
signed main(){
//  freopen("P1908_11.in","r",stdin);
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&a);
        ans+=T.check(rt,1,1e9,a+1,1e9);
//      printf("%d %d\n",i,cnt);
//      cout<<i<<" "<<cnt<<endl;
//      cout<<ans<<endl;
        T.update(rt,1,1e9,a);
    }
    cout<<ans<<endl;
    return 0;
}

这一次却过了，想问一下是什么原因导致的数组空间溢出。