一开始我用的是结构体指针的做法，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;
}

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