C++(g++ 7.5.0) 解法, 执行用时: 66ms, 内存消耗: 2740K, 提交时间: 2022-08-23 00:49:08

#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int N=1e5+5;
struct node{
	int pos,x;
}num[N];
int n1,n2,n,m,flag;
int binary_index_tree[N];
int lowbit(int x){
	return x&-x;
}
void add(int x,int y){
	for(int i=x;i<=n;i+=lowbit(i))
		binary_index_tree[i]+=y;
}
int query(int x){
	int res=0;
	for(int i=x;i>=1;i-=lowbit(i))
		res+=binary_index_tree[i];
	return res;
}
bool cmp(node A,node B){
	return A.x>B.x;
}
signed main(){
    cin>>n1>>n2;
    n=n1+n2+1;
    flag=n1+1;
    for(int i=n1;i>=1;--i){
    	cin>>num[i].x;
    	num[i].pos=i;
    	add(i,1);
	}
	for(int i=n1+2;i<=n;++i){
		cin>>num[i].x;
		num[i].pos=i;
		add(i,1);
	}
	num[flag].pos=flag;
	sort(num+1,num+n+1,cmp);
	long long ans=0;
	for(int i=1;i<n;++i){
		add(num[i].pos,-1);
		if(flag<num[i].pos)
			ans+=query(num[i].pos)-query(flag);
		else
			ans+=query(flag)-query(num[i].pos);
		flag=num[i].pos;
	}
	printf("%lld",ans);
}

C++11(clang++ 3.9) 解法, 执行用时: 35ms, 内存消耗: 2412K, 提交时间: 2020-04-04 19:11:39

#include<bits/stdc++.h>
using namespace std;
#define p(i) cout<<i<<' ';
int c[100020];
int n;
void add(int p,int v)
{
	for(;p<=n;p+=p&(-p))
	c[p]+=v;
}
int ask(int p)
{
	static int ans;
	ans=0;
	for(;p;p-=p&(-p))
	ans+=c[p];
	return ans;
}
struct node
{
	int p,v;
	bool operator < (const node c) const
	{
		return c.v>v;
	}
}a[100020];
int main()
{
	int p,qwe;
	long long ans=0;
	scanf("%d%d",&p,&qwe);
	n=p+qwe;
	for(int i=1;i<=p;i++)
	scanf("%d",&a[i].v),a[i].p=p-i+1;
	for(int i=1;i<=qwe;i++)
	scanf("%d",&a[i+p].v),a[i+p].p=i+p;
	for(int i=1;i<=n;i++)
	add(i,1);
	sort(a+1,a+n+1);
	qwe=n;
	do
	{
		if(a[qwe].p<=p)
		{
			ans+=ask(p)-ask(a[qwe].p);
			add(a[qwe].p,-1);
			p=a[qwe].p;
		}
		else
		{
			ans+=ask(a[qwe].p-1)-ask(p);
			add(a[qwe].p,-1);
			p=a[qwe].p-1;
		}
	}while(--qwe);
	printf("%lld\n",ans);
}