AC代码

#include <bits/stdc++.h>
using namespace std;
const long long N=5e5+10;
long long n,cn=1,ans;
struct node{
	long long sum,num;
}a[N];
struct node1{
	long long cnt,l,r;
}tree[4*N];
bool cmp(node a,node b){
	return a.sum<b.sum;
}
bool cmp1(node a,node b){
	return a.num<b.num;
}
void update(long long id){
	tree[id].cnt=tree[tree[id].l].cnt+tree[tree[id].r].cnt;
}
void build(long long id,long long l,long long r){
	if(l==r) return;
	long long mid=(l+r)/2;
	tree[id].l=++cn; 
	tree[id].r=++cn;
	build(tree[id].l,l,mid);
	build(tree[id].r,mid+1,r);
}
void insit(long long id,long long l,long long r,long long x){
	if(l==r){
		tree[id].cnt++;
		return;
	}
	long long mid=(l+r)/2;
	if(mid>=x) insit(tree[id].l,l,mid,x);
	else insit(tree[id].r,mid+1,r,x);
	update(id);
}
long long find(long long id,long long l,long long r,long long x,long long y){
	if(l==x&&r==y) return tree[id].cnt;
	long long mid=(l+r)/2;
	if(y<=mid) return find(tree[id].l,l,mid,x,y);
	else{
		if(x>mid) return find(tree[id].r,mid+1,r,x,y);
		else return (find(tree[id].l,l,mid,x,mid)+find(tree[id].r,mid+1,r,mid+1,y));
	}
}
int main(){
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
	cin>>n;
	for(long long i=1;i<=n;i++){
		cin>>a[i].sum;
		a[i].num=i;
	}
	stable_sort(a+1,a+n+1,cmp);
	long long r=1;
	a[1].sum=r;
	for(long long i=2;i<=n;i++){
		if(a[i].sum==a[i-1].sum) a[i].sum=r;
		else a[i].sum=++r;
	}
	sort(a+1,a+n+1,cmp1);
	build(1,1,n);
	for(long long i=1;i<=n;i++){
		if(a[i].sum<n)
			ans+=find(1,1,n,a[i].sum+1,n);
		insit(1,1,n,a[i].sum);
	}
	cout<<ans;
	return 0;
}

为什么将stable_sort改为sort后40pts

离散化时已判重