[NOIP2013]火柴排队

共三行，第一行包含一个整数 n ，表示每盒中火柴的数目。
第二行有 n 个整数，每两个整数之间用一个空格隔开，表示第一列火柴的高度。
第三行有 n 个整数，每两个整数之间用一个空格隔开，表示第二列火柴的高度。

C++14(g++5.4) 解法, 执行用时: 110ms, 内存消耗: 7160K, 提交时间: 2019-11-23 14:24:50

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+10;
const int mode=99999997;
typedef long long ll;
struct no
{
	ll num;
	int id;
}a[maxn],b[maxn],q[maxn];
bool cmp(no aa,no bb)
{
	 return aa.num<bb.num;
}
int n;
ll sum[maxn];
int lowbit(int x)
{
	 return x&(-x);
}
void add(int x)
{
	while(x<=n)
	{
		 sum[x]++;
		 x+=lowbit(x);
	}
}
int get(int x)
{
	 int ans=0;
	 while(x)
	 {
	 	 ans+=sum[x];
	 	 x-=lowbit(x);
	 }
	 //cout<<ans<<endl;
	 return ans;
}
int main()
{

cin>>n;
for(int i=1;i<=n;i++)
{
	 cin>>a[i].num;
	 a[i].id=i;
}
for(int i=1;i<=n;i++)
{
	 cin>>b[i].num;
	 b[i].id=i;
}
sort(a+1,a+1+n,cmp);
sort(b+1,b+1+n,cmp);
for(int i=1;i<=n;i++)  q[a[i].id].num=b[i].id;
ll ans=0;
for(int i=n;i;i--)
{
	   ans+=get(q[i].num)%mode;
	   ans=ans%mode;
	   add(q[i].num);
}
cout<<ans<<endl;
return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 37ms, 内存消耗: 2788K, 提交时间: 2019-09-19 15:44:09

#include<bits/stdc++.h>
using namespace std;
const int NN=1e5+4,P=99999997;
int n,a[NN],b[NN],c[NN];
int lower(int x)
{
	return x&(-x);
}
void add(int x)
{
	while(x)
	{
		c[x]++;
		x-=lower(x);
	}
}
int get(int x)
{
	int sum=0;
	while(x<=n)
	{
		sum+=c[x];
		x+=lower(x);
	}
	return sum;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		a[x]=i;
	}
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		b[i]=a[x];
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		ans=(ans+get(b[i]+1))%P;
		add(b[i]);
	}
	printf("%d",ans);
	return 0;
}

详情