80分大样例错了求助
查看原帖
80分大样例错了求助
130104
loris楼主2021/8/3 16:13
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll MM=1000005,mod=99999997;
ll n,c[MM],ans,t[MM];
struct A
{
	ll n,id;
}a[MM];
struct B
{
	ll n,id;
}b[MM];
bool cmp1(A x,A y)
{
	return x.n<y.n;
}
bool cmp2(B x,B y)
{
	return x.n<y.n;
}
ll lowbit(int x)
{
	return x&(-x); 
}
ll add(int x)
{
	while(x<=n)
	{
		t[x]++;
		t[x]%=mod;
		x+=lowbit(x);
	}
}
ll get(int x)
{
	ll ret=0;
	while(x>0)
	{
		ret+=t[x];
		ret%=mod; 
		x-=lowbit(x); 
	}
	return ret;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i].n,a[i].id=i;
	for(int i=1;i<=n;i++)
		cin>>b[i].n,b[i].id=i;
	sort(a+1,a+n+1,cmp1);
	sort(b+1,b+n+1,cmp2);
	for(int i=1;i<=n;i++)
		c[a[i].id]=b[i].id;
	///求c的逆序对
	for(int i=1;i<=n;i++)
	{
		add(c[i]);
		ans+=(i-get(c[i]))%mod;
	}
	cout<<ans; 
	return 0;
}
2021/8/3 16:13
加载中...