蒟蒻求助,11点后面全部RE
查看原帖
蒟蒻求助,11点后面全部RE
212541
weiyangchen楼主2021/8/2 10:53
#include<bits/stdc++.h>
#define lson i<<1
#define rson i<<1|1
#define M 40005
using namespace std;
inline int read()
{
	char chr=getchar();
	int f=1,ans=0;
	while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();}
	while(isdigit(chr)){ans=ans*10;ans+=chr-'0';chr=getchar();}
	return ans*f;
}
int n;
struct Node
{
	int l,r,v;
}t[M<<2];
int a[M],b[M];
void push_up(int i)
{
	t[i].v=t[lson].v+t[rson].v;
}
void build(int i,int l,int r)
{
	t[i].l=l;
	t[i].r=r;
	t[i].v=0;
	if(l==r)
	{
		return;
	}
	int mid=t[i].l+t[i].r>>1;
	build(i<<1,l,mid);
	build(i<<1|1,mid+1,r);
}
void updata(int i,int x)
{
	if(t[i].l==t[i].r)
	{
		++t[i].v;
		return;
	}
	int mid=t[i].l+t[i].r>>1;
	if(x<=mid)
	updata(lson,x);
	else
	updata(rson,x);
	push_up(i);
}
int query(int i,int l,int r)
{
	if(l<=t[i].l&&t[i].r<=r)
	return t[i].v;
	int mid=t[i].l+t[i].r>>1;
	int x=0;
	if(l<=mid)
	x+=query(lson,l,r);
	if(mid<r)
	x+=query(rson,l,r);
	return x;
}
int main()
{
	n=read();
	int ans=0;
	build(1,1,M);
	for(int i=1;i<=n;++i)
	a[i]=read(),b[i]=a[i];
	sort(b+1,b+n+1);
	int len=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<=n;++i)
	{
		int pos=lower_bound(b+1,b+n+1,a[i])-b;
		a[i]=pos;
	}
	for(int i=1;i<=n;++i)
	{
		int x=a[i];
		ans+=query(1,x+1,M);
		updata(1,x);
	}
	printf("%d",ans);
	return 0;
}

我该怎么办?

2021/8/2 10:53
加载中...