「杂烩」精灵魔法（P1908逆序对弱化版）

题面：

题目描述

\(Tristan\)解决了英灵殿的守卫安排后，便到达了静谧的精灵领地——\(Alfheim\) 。由于$ Midgard$ 处在$ Alfheim\(和冥界\) Hel$ 的中间，精灵族领地尚未受到冥界恶灵的侵入。族长$ Galanodel \(为了帮助米德加尔特抵御外敌，对邪恶亡灵军团使用了高等魔法，从而使得亡灵军团每个士兵的行进速度变得不一致，从而打乱冥王\)Hel$安排的最佳阵型。

由于这个军团离\(Midgard\)还很远，因此在抵达$ Midgard$ 之前，对于$ A,B$ 两个亡灵，若$A \(的初始位置在\) B\(后面且\)A \(的速度比 快，\)A \(就会冲到\)B \(的前面去。现在\)Galanodel$ 想知道，会有多少对亡灵之间出现反超现象？

输入格式

第一行一个整数$ n$，表示排成一队的邪恶亡灵军团有多少人。

第二行\(n\)个整数\(a[i]\)，表示邪恶亡灵们在数轴上的初始坐标。数据保证这些坐标全部不同。亡灵军团向数轴正方向前进。

第三行\(n\)个整数 \(v[i]\)，表示邪恶亡灵们的行进速度。

输出格式

一行一个正整数\(k\)，表示「反超」的个数。

样例

样例输入

3

1 2 3

2 1 3

样例输出

1

数据范围与提示

$ n<= 100000$

所有数据的绝对值均不超过\(maxlongint\)。

解法一：朴素的暴力（50pts）

一看就让我们求排序后的逆序对，\(O(n^2)\)搞它

代码：

/*#!/bin/sh

dir=$GEDIT_CURRENT_DOCUMENT_DIR

name=$GEDIT_CURRENT_DOCUMENT_NAME

pre=${name%.*}

g++ -O2 $dir/$name -o $pre -g -Wall -std=c++11

if test $? -eq 0; then

    gnome-terminal -x bash -c "time $dir/$pre;echo;read;"

fi*/

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cmath>

#include<queue>

typedef long long ll;

using namespace std;

const int maxn=1e5+5,INF=0x3f3f3f3f;

inline int read(){

	int s=0,w=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}

	while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();

	return s*w;

}

int n;

ll ans,minn,maxx;

struct Node{

	ll d,v;

}a[maxn];

bool cmp(Node A,Node B){return A.d<B.d;}

int main(){

	//freopen("a.in","r",stdin);

	n=read();

	for(int i=1;i<=n;i++)cin>>a[i].d;

	for(int i=1;i<=n;i++)cin>>a[i].v;

	sort(a+1,a+1+n,cmp);

	for(int i=1;i<=n;i++){

		for(int j=i+1;j<=n;j++){

			if(a[i].v>a[j].v)ans++;

		}

	}

	cout<<ans;

	return 0;

}

解法2：智障的set（40pts）

先介绍个函数：\(algorithm\)库里的\(distance\)函数能够轻易的帮我们把迭代器转成下标处理，用到set上就十分合适

利用set自动排序的功能，可以轻易处理逆序对，将位置从大到小\(sort\)一遍，找新序列的正序对就行了（正序是逆序对，倒序不就是正序对么）

如果新元素比队尾元素大，说明前面所有元素都能于它构成正序对，相反，就可以利用\(lowerbound\)函数找到第一个大于等于它的位置，恰好是它能组成的正序对个数

但是由于set时间效率极低，还没暴力跑的快，用这个练习练习STL就行了

代码：

/*#!/bin/sh

dir=$GEDIT_CURRENT_DOCUMENT_DIR

name=$GEDIT_CURRENT_DOCUMENT_NAME

pre=${name%.*}

g++ -O2 $dir/$name -o $pre -g -Wall -std=c++11

if test $? -eq 0; then

    gnome-terminal -x bash -c "time $dir/$pre;echo;read;"

fi*/

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cmath>

#include<set>

typedef long long ll;

using namespace std;

const int maxn=1e5+5,INF=0x3f3f3f3f;

inline int read(){

	int s=0,w=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}

	while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();

	return s*w;

}

int n,f[maxn];

ll ans;

struct Node{

	ll d,v;

}a[maxn];

multiset<int> s;

bool cmp(Node A,Node B){return A.d>B.d;}

int main(){

//	freopen("a.in","r",stdin);

	n=read();

	for(int i=0;i<n;i++)cin>>a[i].d;

	for(int i=0;i<n;i++)cin>>a[i].v;

	sort(a,a+n,cmp);

	s.insert(a[0].v);

	f[0]=0;

	for(int i=1;i<n;i++){

		int len=s.size();

		if(a[i].v>=*s.rbegin()){//注意，set的end()是假的，只能这样求队尾元素

			f[i]=len,s.insert(a[i].v);

		}else{

		//	cout<<(lower_bound(ve.begin(),ve.end(),a[i].v),a[i].v)<<endl;

			f[i]=distance(s.begin(),s.lower_bound(a[i].v));//distance将迭代器转下标

			s.insert(a[i].v);

		}

		//for(int i=0;i<n;i++)cout<<ve[i]<<" ";

		//cout<<endl;

	}

	for(int i=0;i<n;i++)ans+=f[i];

	cout<<ans;

	return 0;

}

解法3：vector模拟set（100pts）

众所周知，$$vector功能强大，轻易就能排个序，效率比set还高不少，但是终究过不了加强版的P1908

代码：

/*#!/bin/sh

dir=$GEDIT_CURRENT_DOCUMENT_DIR

name=$GEDIT_CURRENT_DOCUMENT_NAME

pre=${name%.*}

g++ -O2 $dir/$name -o $pre -g -Wall -std=c++11

if test $? -eq 0; then

    gnome-terminal -x bash -c "time $dir/$pre;echo;read;"

fi*/

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cmath>

#include<vector>

typedef long long ll;

using namespace std;

const int maxn=1e5+5,INF=0x3f3f3f3f;

inline int read(){

	int s=0,w=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}

	while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();

	return s*w;

}

int n,f[maxn];

ll ans;

struct Node{

	ll d,v;

}a[maxn];

vector<int> ve;

bool cmp(Node A,Node B){return A.d>B.d;}

int main(){

//	freopen("a.in","r",stdin);

	n=read();

	for(int i=0;i<n;i++)cin>>a[i].d;

	for(int i=0;i<n;i++)cin>>a[i].v;//狗比vector只能从0开始存

	sort(a,a+n,cmp);

	ve.push_back(a[0].v);

	f[0]=0;

	for(int i=1;i<n;i++){

		int len=ve.size();

		if(a[i].v>=ve.back()){

			f[i]=len,ve.push_back(a[i].v);

		}else{

		//	cout<<(lower_bound(ve.begin(),ve.end(),a[i].v),a[i].v)<<endl;

			f[i]=lower_bound(ve.begin(),ve.end(),a[i].v)-ve.begin();//注意写法，考试就在这被卡住了

			ve.insert(lower_bound(ve.begin(),ve.end(),a[i].v),a[i].v);//假装排序

		}

		//for(int i=0;i<n;i++)cout<<ve[i]<<" ";

		//cout<<endl;

	}

	for(int i=0;i<n;i++)ans+=f[i];

	cout<<ans;

	return 0;

}

解法4：树状数组（100pts）

对结构体\(a[i]\)排序，按位置从小到大的顺序排，利用辅助数组b记录排序后的位置，将位置插入树状数组，咨询一下后缀和即可

代码：

/*#!/bin/sh

dir=$GEDIT_CURRENT_DOCUMENT_DIR

name=$GEDIT_CURRENT_DOCUMENT_NAME

pre=${name%.*}

g++ -O2 $dir/$name -o $pre -g -Wall -std=c++11

if test $? -eq 0; then

    gnome-terminal -x bash -c "time $dir/$pre;echo;read;"

fi*/

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cmath>

#include<set>

typedef long long ll;

using namespace std;

const int maxn=1e5+5,INF=0x3f3f3f3f;

inline int read(){

	int s=0,w=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}

	while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();

	return s*w;

}

int n,f[maxn];

ll ans,b[maxn],c[maxn];

struct Node{

	ll d,v;

}a[maxn];

bool cmp(Node A,Node B){return A.d<B.d;}

ll Lowbit(ll x){return x&-x;}

void update(ll x){

	while(x<=n){

		c[x]++;

		x+=Lowbit(x);

	}

}

ll query(ll x){

	ll sum=0;

	while(x){

		sum+=c[x];

		x-=Lowbit(x);

	}

	return sum;

}

int main(){

	//freopen("a.in","r",stdin);

	n=read();

	for(int i=1;i<=n;i++)cin>>a[i].d;

	for(int i=1;i<=n;i++)cin>>a[i].v,b[i]=a[i].v;

	sort(a+1,a+n+1,cmp);

	sort(b+1,b+1+n);

	for(int i=1;i<=n;i++)a[i].v=lower_bound(b+1,b+1+n,a[i].v)-b;

	for(int i=n;i>=1;i--){

		ans+=query(a[i].v-1);update(a[i].v);

	}

	cout<<ans;

	return 0;

}

解法5：归并排序（100pts）

这就不用写了吧，归并能处理逆序对（貌似也只有这个用途）