蒟蒻求助25分TLE
  • 板块P1908 逆序对
  • 楼主Mine_KingCattleya
  • 当前回复6
  • 已保存回复6
  • 发布时间2020/9/3 20:05
  • 上次更新2023/11/5 13:46:43
查看原帖
蒟蒻求助25分TLE
195331
Mine_KingCattleya楼主2020/9/3 20:05

只有钱5个点AC,其他全都TLE/kk
求大佬帮忙debug

#include<cstdio>
using namespace std;
int n;
long long ans;
struct tree
{
	int tot;
	int ls[1000005],rs[1000005];
	int l[1000005],r[1000005];
	int w[1000005];
	int build(int ll,int rr)
	{
		tot++;
		w[tot]=0;
		ls[tot]=rs[tot]=0;
		l[tot]=ll,r[tot]=rr;
		return tot;
	}
	void change(int k,int x)
	{
		if(l[k]==r[k])
		{
			w[k]++;
			return ;
		}
		int mid=(l[k]+r[k])/2;
		if(x<=mid)
		{
			if(ls[k]==0) ls[k]=build(l[k],mid);
			change(ls[k],x);
		}
		else
		{
			if(rs[k]==0) rs[k]=build(mid+1,r[k]);
			change(rs[k],x);
		}
		w[k]=w[ls[k]]+w[rs[k]];
		return ;
	}
	int ask(int k,int x)
	{
		if(l[k]==r[k]) return w[k];
		int mid=(l[k]+r[k])/2,res=0;
		if(x<=mid)
			if(ls[k]!=0) res+=ask(ls[k],x);
		if(rs[k]!=0) res+=ask(rs[k],x);
		return res;
	}
}tr;
int main()
{
	scanf("%d",&n);
	tr.build(0,1000000000);
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		ans+=tr.ask(1,x+1);
		tr.change(1,x);
	}
	printf("%lld\n",ans);
	return 0;
}

2020/9/3 20:05
加载中...